Changeset 1256

Timestamp:

07/24/13 07:45:47 (11 years ago)

Author:

pharms

Message:

• performance improvement for task tree generation

Location:

trunk

Files:

• autoquest-core-tasktrees-test/src/test/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/TaskInstanceTrieTest.java (added)
• autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRule.java (modified) (12 diffs)
• autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/TaskComparator.java (added)
• autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/TaskInstanceTrie.java (added)

trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRule.java

@@ -15 +15 @@
 package de.ugoe.cs.autoquest.tasktrees.temporalrelation;
 
-import java.io.IOException;
-import java.io.ObjectInputStream;
-import java.util.HashMap;
 import java.util.Iterator;
 import java.util.LinkedList;
@@ -23 +20 @@
 
 import de.ugoe.cs.autoquest.tasktrees.taskequality.TaskEquality;
-import de.ugoe.cs.autoquest.tasktrees.taskequality.TaskEqualityRuleManager;
-import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTask;
 import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration;
 import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection;
@@ -34 +29 @@
 import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstanceList;
 import de.ugoe.cs.autoquest.tasktrees.treeifc.IUserSession;
-import de.ugoe.cs.autoquest.usageprofiles.SymbolComparator;
-import de.ugoe.cs.autoquest.usageprofiles.Trie;
+import de.ugoe.cs.autoquest.usageprofiles.SymbolMap;
 import de.ugoe.cs.autoquest.usageprofiles.TrieProcessor;
 import de.ugoe.cs.util.StopWatch;
@@ -102 +96 @@
 
         // this is the real rule application. Loop while something is replaced.
+        harmonizeEventTaskInstancesModel(appData);
         do {
             System.out.println();
@@ -134 +129 @@
         
         return appData.getResult();
+    }
+
+    /**
+     * <p>
+     * TODO: comment
+     * </p>
+     *
+     * @param appData
+     */
+    private void harmonizeEventTaskInstancesModel(RuleApplicationData appData) {
+        System.out.print("harmonizing task model of event task instances");
+        appData.getStopWatch().start("harmonizing event tasks");
+        
+        SymbolMap<ITaskInstance, ITask> unifiedTaskMap =
+            new SymbolMap<ITaskInstance, ITask>(taskComparator);
+        
+        int unifiedTasks = 0;
+        
+        List<IUserSession> sessions = appData.getSessions();
+        for (IUserSession session : sessions) {
+            for (ITaskInstance taskInstance : session) {
+                ITask task = unifiedTaskMap.getValue(taskInstance);
+                
+                if (task == null) {
+                    unifiedTaskMap.addSymbol(taskInstance, taskInstance.getTask());
+                }
+                else {
+                    taskBuilder.setTask(taskInstance, task);
+                    unifiedTasks++;
+                }
+            }
+        }
+        
+        
+        appData.getStopWatch().stop("harmonizing event tasks");
+        System.out.println(" --> harmonized " + unifiedTasks + " task occurrences (still " +
+                           unifiedTaskMap.size() + " different tasks)");
+        
+        appData.getStopWatch().dumpStatistics(System.out);
     }
 
@@ -373 +407 @@
         while (createNewTrie);
         
+        // create a normal trie for comparison
+        /*System.out.println("creating test trie for comparison");
+        
+        appData.getStopWatch().start("testtrie");
+        Trie<ITaskInstance> trie = new Trie<ITaskInstance>(taskComparator);
+        
+        for (IUserSession session : appData.getSessions()) {
+            trie.train(session.getExecutedTasks(), appData.getTrainedSequenceLength());
+        }
+        
+        appData.getStopWatch().stop("testtrie");
+        
+        MaxCountAndLongestTasksFinder finder = new MaxCountAndLongestTasksFinder();
+        trie.process(finder);
+
+        boolean allTasksEqual = finder.getFoundTasks().size() == tasks.size();
+        
+        allTasksEqual &= finder.getFoundTasks().occurrenceCount == tasks.occurrenceCount;
+        
+        for (List<ITaskInstance> task1 : finder.getFoundTasks()) {
+            boolean foundTask = false;
+            for (List<ITaskInstance> task2 : tasks) {
+                boolean tasksEqual = false;
+                if (task1.size() == task2.size()) {
+                    tasksEqual = true;
+                    for (int i = 0; i < task1.size(); i++) {
+                        if (!taskComparator.equals(task1.get(i).getTask(), task2.get(i).getTask()))
+                        {
+                            tasksEqual = false;
+                        }
+                    }
+                }
+                
+                if (tasksEqual) {
+                    foundTask = true;
+                    break;
+                }
+            }
+            
+            if (!foundTask) {
+                System.out.println("different is " + task1);
+                allTasksEqual = false;
+                break;
+            }
+        }
+        
+        if (!allTasksEqual) {
+            System.out.println(finder.getFoundTasks());
+            System.out.println(tasks);
+            
+            throw new IllegalArgumentException("both tries calculated different subsequences");
+        }*/
+        
+        /*TrieStatisticsDumper dumper = new TrieStatisticsDumper();
+        appData.getLastTrie().process(dumper);
+        dumper.dumpCounters();*/
+        
         appData.setLastFoundTasks(tasks);
 
@@ -388 +479 @@
 
         appData.getStopWatch().start("training trie");
-        appData.setLastTrie(new Trie<ITaskInstance>(taskComparator));
+        appData.setLastTrie(new TaskInstanceTrie(taskComparator));
     
-        List<IUserSession> sessions = appData.getSessions();
-        
-        for (IUserSession session : sessions) {
-            trainTrie(session, appData);
-        }
+        appData.getLastTrie().trainSessions
+            (appData.getSessions(), appData.getTrainedSequenceLength());
         
         appData.getStopWatch().stop("training trie");
-    }
-
-    /**
-     * @param trie
-     * @param parent
-     */
-    private void trainTrie(IUserSession session, RuleApplicationData appData) {
-        List<ITaskInstance> children = session.getExecutedTasks();
-        
-        if ((children != null) && (children.size() > 0)) {
-            appData.getLastTrie().train(children, appData.getTrainedSequenceLength());
-        }
     }
 
@@ -704 +780 @@
     }
     
+//    /**
+//     * @author Patrick Harms
+//     */
+//    private class TrieStatisticsDumper implements TrieProcessor<ITaskInstance> {
+//        
+//        /**
+//         * 
+//         */
+//        private Map<Integer, Integer> counters = new HashMap<Integer, Integer>();
+//        
+//        /* (non-Javadoc)
+//         * @see de.ugoe.cs.autoquest.usageprofiles.TrieProcessor#process(java.util.List, int)
+//         */
+//        @Override
+//        public TrieProcessor.Result process(List<ITaskInstance> subsequence, int count) {
+//            if (subsequence.size() == 1) {
+//                Integer value = counters.get(count);
+//                
+//                if (value == null) {
+//                    value = 0;
+//                }
+//                
+//                counters.put(count, value + 1);
+//                
+//                return TrieProcessor.Result.CONTINUE;
+//            }
+//            else {
+//                // ignore singular occurrences
+//                return TrieProcessor.Result.SKIP_NODE;
+//            }
+//        }
+//
+//        /**
+//         *  @return
+//         */
+//        public void dumpCounters() {
+//            int dumpedCounters = 0;
+//            
+//            int count = 1;
+//            while (dumpedCounters < counters.size()) {
+//                Integer value = counters.get(count++);
+//                if (value != null) {
+//                    System.out.println(value + " symbols occurred " + count + " times");
+//                    dumpedCounters++;
+//                }
+//            }
+//        }
+//
+//    }
+    
     /**
      * 
@@ -717 +843 @@
          * 
          */
-        private Trie<ITaskInstance> lastTrie;
+        private TaskInstanceTrie lastTrie;
         
         /**
@@ -761 +887 @@
          * @param lastTrie the lastTrie to set
          */
-        private void setLastTrie(Trie<ITaskInstance> lastTrie) {
+        private void setLastTrie(TaskInstanceTrie lastTrie) {
             this.lastTrie = lastTrie;
         }
@@ -768 +894 @@
          * @return the lastTrie
          */
-        private Trie<ITaskInstance> getLastTrie() {
+        private TaskInstanceTrie getLastTrie() {
             return lastTrie;
         }
@@ -882 +1008 @@
         }
 
-    }
-
-    /**
-     *
-     */
-    private static class TaskComparator implements SymbolComparator<ITaskInstance> {
-        
-        /**  */
-        private static final long serialVersionUID = 1L;
-
-        /** */
-        private TaskEquality minimalNodeEquality;
-
-        /** */
-        private transient Comparer comparer;
-
-        /** */
-        private transient Comparer lexicalComparer;
-
-        /** */
-        private transient HashMap<Long, Boolean> equalityBuffer = new HashMap<Long, Boolean>();
-
-        /** */
-        private transient HashMap<Long, Boolean> lexicalEqualityBuffer;
-
-        /**
-         *
-         */
-        public TaskComparator(TaskEquality minimalNodeEquality) {
-            this.minimalNodeEquality = minimalNodeEquality;
-            init();
-        }
-
         /* (non-Javadoc)
-         * @see de.ugoe.cs.autoquest.tasktrees.temporalrelation.SymbolComparator#equals(java.lang.Object, java.lang.Object)
+         * @see java.lang.Object#toString()
          */
         @Override
-        public boolean equals(ITaskInstance taskInstance1, ITaskInstance taskInstance2) {
-            return equals(taskInstance1.getTask(), taskInstance2.getTask());
-        }        
-
-        /**
-         * 
-         */
-        public boolean equals(ITask task1, ITask task2) {
-            Boolean result;
-            
-            if (task1 != task2) {
-                if ((task1 instanceof IEventTask) && (task2 instanceof IEventTask)) {
-                    long key = ((long) System.identityHashCode(task1)) << 32;
-                    key += System.identityHashCode(task2);
-                
-                    result = equalityBuffer.get(key);
-                
-                    if (result == null) {
-                        result = comparer.compare(task1, task2);
-                        equalityBuffer.put(key, result);
-                    }
-                }
-                else {
-                    result = false;
-                }
-            }
-            else {
-                result = true;
-            }
-            
-            return result;
-        }
-
-        /**
-         *
-         */
-        public boolean areLexicallyEqual(ITask task1, ITask task2) {
-            Boolean result;
-            
-            if (task1 != task2) {
-                long key = ((long) System.identityHashCode(task1)) << 32;
-                key += System.identityHashCode(task2);
-                
-                result = lexicalEqualityBuffer.get(key);
-                
-                if (result == null) {
-                    result = lexicalComparer.compare(task1, task2);
-                    lexicalEqualityBuffer.put(key, result);
-                }
-            }
-            else {
-                result = true;
-            }
-            
-            return result;
-        }
-        
-        /**
-         * 
-         */
-        private void init() {
-            if (minimalNodeEquality == TaskEquality.LEXICALLY_EQUAL) {
-                comparer = new LexicalComparer();
-            }
-            else if (minimalNodeEquality == TaskEquality.SYNTACTICALLY_EQUAL) {
-                comparer = new SyntacticalComparer();
-            }
-            else if (minimalNodeEquality == TaskEquality.SEMANTICALLY_EQUAL) {
-                comparer = new SemanticalComparer();
-            }
-            else {
-                comparer = new DefaultComparer(this.minimalNodeEquality);
-            }
-            
-            if (minimalNodeEquality == TaskEquality.LEXICALLY_EQUAL) {
-                lexicalComparer = comparer;
-                lexicalEqualityBuffer = equalityBuffer;
-            }
-            else {
-                lexicalComparer = new LexicalComparer();
-                lexicalEqualityBuffer = new HashMap<Long, Boolean>();
-            }
-        }
-        
-        /**
-         * <p>
-         * deserialize this object and reinitialize the buffers
-         * </p>
-         */
-        private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
-            in.defaultReadObject();
-            init();
-        }
-    }
-
-    /**
-     * 
-     */
-    private static interface Comparer {
-        
-        /**
-         * 
-         */
-        boolean compare(ITask task1, ITask task2);
-    }
-
-    /**
-     * 
-     */
-    private static class LexicalComparer implements Comparer {
-        
-        /**
-         * 
-         */
-        public boolean compare(ITask task1, ITask task2) {
-            return TaskEqualityRuleManager.getInstance().areLexicallyEqual(task1, task2);
-        }
-    }
-
-    /**
-     * 
-     */
-    private static class SyntacticalComparer implements Comparer {
-        
-        /**
-         * 
-         */
-        public boolean compare(ITask task1, ITask task2) {
-            return TaskEqualityRuleManager.getInstance().areSyntacticallyEqual(task1, task2);
-        }
-    }
-
-    /**
-     * 
-     */
-    private static class SemanticalComparer implements Comparer {
-        
-        /**
-         * 
-         */
-        public boolean compare(ITask task1, ITask task2) {
-            return TaskEqualityRuleManager.getInstance().areSemanticallyEqual(task1, task2);
-        }
-    }
-
-    /**
-     * 
-     */
-    private static class DefaultComparer implements Comparer {
-        
-        /**
-         * <p>
-         * the minimal task equality two identified sublists need to have to consider them as equal
-         * </p>
-         */
-        private TaskEquality minimalNodeEquality;
-        
-        /**
-         *
-         */
-        public DefaultComparer(TaskEquality minimalNodeEquality) {
-           this.minimalNodeEquality = minimalNodeEquality;
-        }
-        
-        /**
-         * 
-         */
-        public boolean compare(ITask task1, ITask task2) {
-            return TaskEqualityRuleManager.getInstance().areAtLeastEqual
-                (task1, task2, minimalNodeEquality);
-        }
+        public String toString() {
+            StringBuffer result = new StringBuffer();
+            result.append(this.occurrenceCount);
+            result.append(" occurrences:\n");
+            
+            for (List<ITaskInstance> task : sequences) {
+                result.append(task);
+                result.append("\n");
+            }
+            
+            return result.toString();
+        }
+
     }
 }