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

Timestamp:

07/30/13 09:44:39 (11 years ago)

Author:

pharms

Message:

• improved performance of task instance trie generation by using different symbol management strategies while creating the trie. This performance improvement is significant and allows to detect tasks now in a much faster manner.

File:

• trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRule.java (modified) (26 diffs)

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.util.HashMap;
+import java.util.HashSet;
 import java.util.Iterator;
 import java.util.LinkedList;
 import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.logging.Level;
 
 import de.ugoe.cs.autoquest.tasktrees.taskequality.TaskEquality;
@@ -32 +37 @@
 import de.ugoe.cs.autoquest.usageprofiles.TrieProcessor;
 import de.ugoe.cs.util.StopWatch;
+import de.ugoe.cs.util.console.Console;
 
 /**
@@ -59 +65 @@
     /**
      * <p>
-     * the task comparator to be used for comparing tasks
+     * the task comparator to be used for comparing tasks for preparation
      * </p>
      */
-    private TaskComparator taskComparator;
-
+    private TaskHandlingStrategy preparationTaskHandlingStrategy;
+    
+    /**
+     * <p>
+     * the task comparator to be used for comparing tasks during iteration detection an trie
+     * generation
+     * </p>
+     */
+    private TaskHandlingStrategy identityTaskHandlingStrategy;;
+    
     /**
      * <p>
@@ -77 +91 @@
         this.taskBuilder = taskBuilder;
         
-        this.taskComparator = new TaskComparator(minimalTaskEquality);
+        this.preparationTaskHandlingStrategy = new TaskHandlingStrategy(minimalTaskEquality);
+        this.identityTaskHandlingStrategy = new TaskHandlingStrategy(TaskEquality.IDENTICAL);
     }
 
@@ -139 +154 @@
      */
     private void harmonizeEventTaskInstancesModel(RuleApplicationData appData) {
-        System.out.print("harmonizing task model of event task instances");
+        Console.traceln(Level.INFO, "harmonizing task model of event task instances");
         appData.getStopWatch().start("harmonizing event tasks");
-        
-        SymbolMap<ITaskInstance, ITask> unifiedTaskMap =
-            new SymbolMap<ITaskInstance, ITask>(taskComparator);
+
+        SymbolMap<ITaskInstance, ITask> uniqueTasks =
+            preparationTaskHandlingStrategy.createSymbolMap();
+        TaskComparator comparator = preparationTaskHandlingStrategy.getTaskComparator();
         
         int unifiedTasks = 0;
-        
+        ITask task;
         List<IUserSession> sessions = appData.getSessions();
         for (IUserSession session : sessions) {
+            Console.traceln(Level.FINE, "handling session " + session);
             for (ITaskInstance taskInstance : session) {
-                ITask task = unifiedTaskMap.getValue(taskInstance);
+                task = uniqueTasks.getValue(taskInstance);
                 
                 if (task == null) {
-                    unifiedTaskMap.addSymbol(taskInstance, taskInstance.getTask());
+                    uniqueTasks.addSymbol(taskInstance, taskInstance.getTask());
                 }
                 else {
@@ -160 +177 @@
                 }
             }
-        }
-        
+            
+            comparator.clearBuffers();
+        }
         
         appData.getStopWatch().stop("harmonizing event tasks");
-        System.out.println(" --> harmonized " + unifiedTasks + " task occurrences (still " +
-                           unifiedTaskMap.size() + " different tasks)");
-        
+        Console.traceln(Level.INFO, "harmonized " + unifiedTasks + " task occurrences (still " +
+                        uniqueTasks.size() + " different tasks)");
+
         appData.getStopWatch().dumpStatistics(System.out);
+        appData.getStopWatch().reset();
     }
 
@@ -174 +193 @@
      */
     private void detectAndReplaceIterations(RuleApplicationData appData) {
-        System.out.print("detecting iterations");
+        Console.traceln(Level.FINE, "detecting iterations");
         appData.getStopWatch().start("detecting iterations");
         
         List<IUserSession> sessions = appData.getSessions();
-        int iteratedTasks = 0;
-        
-        ITask iteratedTask = null;
-        
-        do {
-            iteratedTask = searchIteratedTask(sessions);
-            
-            if (iteratedTask != null) {
-                replaceIterationsOf(iteratedTask, sessions, appData);
-                iteratedTasks++;
-            }
-        }
-        while (iteratedTask != null);
+        
+        Set<ITask> iteratedTasks = searchIteratedTasks(sessions);
+        
+        if (iteratedTasks.size() > 0) {
+            replaceIterationsOf(iteratedTasks, sessions, appData);
+        }
         
         appData.getStopWatch().stop("detecting iterations");
-        System.out.println(" --> found " + iteratedTasks + " iterated tasks");
+        Console.traceln(Level.INFO, "replaced " + iteratedTasks.size() + " iterated tasks");
     }
 
@@ -199 +211 @@
      *
      */
-    private ITask searchIteratedTask(List<IUserSession> sessions) {
+    private Set<ITask> searchIteratedTasks(List<IUserSession> sessions) {
+        Set<ITask> iteratedTasks = new HashSet<ITask>();
         for (IUserSession session : sessions) {
             for (int i = 0; i < (session.size() - 1); i++) {
-                if (taskComparator.equals(session.get(i), session.get(i + 1))) {
-                    return session.get(i).getTask();
-                }
-            }
-        }
-        
-        return null;
+                // we prepared the task instances to refer to unique tasks, if they are treated
+                // as equal. Therefore, we just compare the identity of the tasks of the task
+                // instances
+                if (session.get(i).getTask() == session.get(i + 1).getTask()) {
+                    iteratedTasks.add(session.get(i).getTask());
+                }
+            }
+        }
+        
+        return iteratedTasks;
     }
 
@@ -214 +230 @@
      *
      */
-/*    private ITask searchIteratedTask(List<IUserSession> sessions) {
-        int minNoOfRepetitions = 2;
-        int minNoOfIterationOccurrences = 1;
-        
-        Map<ITask, Integer> iterationsCounter = new HashMap<ITask, Integer>();
-        
-        for (IUserSession session : sessions) {
-            for (int i = 0; i < (session.size() - minNoOfRepetitions + 1); i++) {
-                ITask task = session.get(i).getTask();
-
-                // check if the task is iterated
-                boolean isIterated = true;
-                for (int j = i + 1; j < i + minNoOfRepetitions; j++) {
-                    if (!taskComparator.equals(task, session.get(j).getTask())) {
-                        isIterated = false;
-                        break;
-                    }
-                }
-                
-                if (isIterated) {
-                    Integer currentCounter = null;
-                    
-                    for (Map.Entry<ITask, Integer> entry : iterationsCounter.entrySet()) {
-                        if (taskComparator.equals(task, entry.getKey())) {
-                            currentCounter = entry.getValue();
-                            break;
-                        }
-                    }
-                    
-                    if (currentCounter == null) {
-                        currentCounter = 1;
-                        iterationsCounter.put(task, currentCounter);
-                    }
-                    else {
-                        currentCounter++;
-                        iterationsCounter.put(task, currentCounter);
-                    }
-                    
-                    if (currentCounter >= minNoOfIterationOccurrences) {
-                        return task;
-                    }
-                }
-            }
-        }
-        
-        return null;
-    }*/
-
-    /**
-     *
-     */
-    private void replaceIterationsOf(ITask               iteratedTask,
+    private void replaceIterationsOf(Set<ITask>          iteratedTasks,
                                      List<IUserSession>  sessions,
                                      RuleApplicationData appData)
     {
-        IIteration iteration = taskFactory.createNewIteration();
+        Map<ITask, IIteration> iterations = new HashMap<ITask, IIteration>();
+        Map<IIteration, List<ITaskInstance>> iterationInstances =
+                new HashMap<IIteration, List<ITaskInstance>>();
+            
+        for (ITask iteratedTask : iteratedTasks) {
+            IIteration iteration = taskFactory.createNewIteration();
+            iterations.put(iteratedTask, iteration);
+            iterationInstances.put(iteration, new LinkedList<ITaskInstance>());
+        }
+        
         ITaskInstance iterationInstance = null;
-        
-        List<ITaskInstance> iterationInstances = new LinkedList<ITaskInstance>();
         
         for (IUserSession session : sessions) {
             int index = 0;
             while (index < session.size()) {
-                if (taskComparator.equals(iteratedTask, session.get(index).getTask())) {
-                    if (iterationInstance == null) {
+                // we prepared the task instances to refer to unique tasks, if they are treated
+                // as equal. Therefore, we just compare the identity of the tasks of the task
+                // instances
+                ITask currentTask = session.get(index).getTask();
+                IIteration iteration = iterations.get(currentTask);
+                if (iteration != null) {
+                    if ((iterationInstance == null) || (iterationInstance.getTask() != iteration))
+                    {
                         iterationInstance = taskFactory.createNewTaskInstance(iteration);
-                        iterationInstances.add(iterationInstance);
+                        iterationInstances.get(iteration).add(iterationInstance);
                         taskBuilder.addTaskInstance(session, index, iterationInstance);
                         index++;
@@ -297 +275 @@
         }
         
-        harmonizeIterationInstancesModel(iteration, iterationInstances);
+        for (Map.Entry<IIteration, List<ITaskInstance>> entry : iterationInstances.entrySet()) {
+            harmonizeIterationInstancesModel(entry.getKey(), entry.getValue());
+        }
     }
 
@@ -307 +287 @@
     {
         List<ITask> iteratedTaskVariants = new LinkedList<ITask>();
+        TaskComparator comparator = preparationTaskHandlingStrategy.getTaskComparator();
         
         // merge the lexically different variants of iterated task to a unique list 
@@ -315 +296 @@
                 boolean found = false;
                 for (ITask taskVariant : iteratedTaskVariants) {
-                    if (taskComparator.areLexicallyEqual(taskVariant, candidate)) {
+                    if (comparator.areLexicallyEqual(taskVariant, candidate)) {
                         taskBuilder.setTask(executionVariant, taskVariant);
                         found = true;
@@ -359 +340 @@
      */
     private void detectAndReplaceTasks(RuleApplicationData appData) {
-        System.out.println("detecting and replacing tasks");
+        Console.traceln(Level.FINE, "detecting and replacing tasks");
         appData.getStopWatch().start("detecting tasks");
         
@@ -370 +351 @@
         
         appData.getStopWatch().stop("replacing tasks");
-        System.out.println("detected and replaced " + appData.getLastFoundTasks().size() + " tasks");
+        Console.traceln(Level.INFO, "detected and replaced " + appData.getLastFoundTasks().size() +
+                        " tasks occuring " + appData.getLastFoundTasks().getOccurrenceCount() +
+                        "times");
     }
 
@@ -377 +360 @@
      */
     private void getSequencesOccuringMostOften(RuleApplicationData appData) {
-        System.out.println("determining most prominent tasks");
+        Console.traceln(Level.FINE, "determining most prominent tasks");
 
         Tasks tasks;
@@ -411 +394 @@
         
         appData.getStopWatch().start("testtrie");
-        Trie<ITaskInstance> trie = new Trie<ITaskInstance>(taskComparator);
+        Trie<ITaskInstance> trie = new Trie<ITaskInstance>(identityTaskComparator);
         
         for (IUserSession session : appData.getSessions()) {
@@ -433 +416 @@
                     tasksEqual = true;
                     for (int i = 0; i < task1.size(); i++) {
-                        if (!taskComparator.equals(task1.get(i).getTask(), task2.get(i).getTask()))
+                        if (!identityTaskComparator.equals(task1.get(i).getTask(), task2.get(i).getTask()))
                         {
                             tasksEqual = false;
@@ -458 +441 @@
             
             throw new IllegalArgumentException("both tries calculated different subsequences");
-        }*/
+        }
         
         /*TrieStatisticsDumper dumper = new TrieStatisticsDumper();
@@ -466 +449 @@
         appData.setLastFoundTasks(tasks);
 
-        System.out.println("found " + appData.getLastFoundTasks().size() + " tasks occurring " +
-                           appData.getLastFoundTasks().getOccurrenceCount() + " times");
+        Console.traceln(Level.FINE, "found " + appData.getLastFoundTasks().size() + " tasks " +
+                        "occurring " + appData.getLastFoundTasks().getOccurrenceCount() + " times");
     }
 
@@ -475 +458 @@
      */
     private void createNewTrie(RuleApplicationData appData) {
-        System.out.println("training trie with a maximum sequence length of " +
-                           appData.getTrainedSequenceLength());
+        Console.traceln(Level.FINER, "training trie with a maximum sequence length of " +
+                        appData.getTrainedSequenceLength());
 
         appData.getStopWatch().start("training trie");
-        appData.setLastTrie(new TaskInstanceTrie(taskComparator));
+        
+        // we prepared the task instances to refer to unique tasks, if they are treated
+        // as equal. Therefore, we just compare the identity of the tasks of the task
+        // instances
+        appData.setLastTrie(new TaskInstanceTrie(identityTaskHandlingStrategy));
     
         appData.getLastTrie().trainSessions
@@ -496 +483 @@
             (appData.getLastFoundTasks().getOccurrenceCount() > 1))
         {
-            System.out.println("replacing tasks occurrences");
+            Console.traceln(Level.FINER, "replacing tasks occurrences");
 
             for (List<ITaskInstance> task : appData.getLastFoundTasks()) {
                 ISequence sequence = taskFactory.createNewSequence();
                 
-                System.out.println("replacing " + sequence.getId() + ": " + task);
+                Console.traceln(Level.FINEST, "replacing " + sequence.getId() + ": " + task);
 
                 List<ITaskInstance> sequenceInstances =
@@ -507 +494 @@
                 
                 harmonizeSequenceInstancesModel(sequence, sequenceInstances,task.size());
-                appData.detectedAndReplacedTasks(sequenceInstances.size() > 0);
+                appData.detectedAndReplacedTasks
+                    (appData.detectedAndReplacedTasks() || (sequenceInstances.size() > 0));
 
                 if (sequenceInstances.size() < appData.getLastFoundTasks().getOccurrenceCount()) {
-                    System.out.println(sequence.getId() + ": replaced task only " +
-                                       sequenceInstances.size() + " times instead of expected " +
-                                       appData.getLastFoundTasks().getOccurrenceCount());
+                    Console.traceln(Level.FINE, sequence.getId() + ": replaced task only " +
+                                    sequenceInstances.size() + " times instead of expected " +
+                                    appData.getLastFoundTasks().getOccurrenceCount());
                 }
             }
@@ -526 +514 @@
                                                  int                 sequenceLength)
     {
+        TaskComparator comparator = preparationTaskHandlingStrategy.getTaskComparator();
         
         // ensure for each subtask that lexically different variants are preserved
@@ -537 +526 @@
                 
                 for (int i = 0; i < subTaskVariants.size(); i++) {
-                    if (taskComparator.areLexicallyEqual(subTaskVariants.get(i), candidate)) {
+                    if (comparator.areLexicallyEqual(subTaskVariants.get(i), candidate)) {
                         taskBuilder.setTask
                             (sequenceInstance.get(subTaskIndex), subTaskVariants.get(i));
@@ -624 +613 @@
             
             for (int j = 0; j < subList.size(); j++) {
-                if (!taskComparator.equals(list.get(i + j), subList.get(j))) {
+                // we prepared the task instances to refer to unique tasks, if they are treated
+                // as equal. Therefore, we just compare the identity of the tasks of the task
+                // instances
+                if (list.get(i + j).getTask() != subList.get(j).getTask()) {
                     matchFound = false;
                     break;
@@ -655 +647 @@
             
             for (int j = 0; j < subList.size(); j++) {
-                if (!taskComparator.equals(list.get(i + j), subList.get(j))) {
+                // we prepared the task instances to refer to unique tasks, if they are treated
+                // as equal. Therefore, we just compare the identity of the tasks of the task
+                // instances
+                if (list.get(i + j) != subList.get(j)) {
                     matchFound = false;
                     break;