Changeset 2131 for trunk/autoquest-core-tasktrees/src/main/java/de

Timestamp:

08/24/16 10:16:04 (8 years ago)

Author:

pharms

Message:

• several performance improvements in sequence and collision detection
• added possibility to select the minimal amount of action instances a detected sequence should cover

File:

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

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

@@ -29 +29 @@
 import de.ugoe.cs.autoquest.tasktrees.taskequality.TaskEquality;
 import de.ugoe.cs.autoquest.tasktrees.temporalrelation.utils.DebuggingHelper;
+import de.ugoe.cs.autoquest.tasktrees.treeifc.DefaultTaskInstanceTraversingVisitor;
+import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTaskInstance;
 import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration;
 import de.ugoe.cs.autoquest.tasktrees.treeifc.IIterationInstance;
@@ -102 +104 @@
     /**
      * <p>
+     * the minimum number of event task instances a sequence must cover to still detect it as a
+     * representative task
+     * </p>
+     */
+    private int minimumSequenceCoverage;;
+    
+    /**
+     * <p>
      * instantiates the rule and initializes it with a task equality to be considered when
      * comparing tasks as well as a task factory and builder to be used for creating task
@@ -107 +117 @@
      * </p>
      * 
-     * @param minimalTaskEquality the task equality to be considered when comparing tasks
-     * @param taskFactory         the task factory to be used for creating substructures
-     * @param taskBuilder         the task builder to be used for creating substructures
+     * @param minimalTaskEquality     the task equality to be considered when comparing tasks
+     * @param taskFactory             the task factory to be used for creating substructures
+     * @param taskBuilder             the task builder to be used for creating substructures
+     * @param minimumSequenceCoverage the minimum number of event task instances a sequence must
+     *                                cover to still detect it as a representative task
      */
     SequenceForTaskDetectionRule(TaskEquality minimalTaskEquality,
                                  ITaskFactory taskFactory,
-                                 ITaskBuilder taskBuilder)
+                                 ITaskBuilder taskBuilder,
+                                 int          minimumSequenceCoverage)
     {
         this.taskFactory = taskFactory;
         this.taskBuilder = taskBuilder;
+        this.minimumSequenceCoverage = minimumSequenceCoverage;
         
         this.preparationTaskHandlingStrategy = new TaskHandlingStrategy(minimalTaskEquality);
@@ -468 +482 @@
             }
             
+            appData.getStopWatch().start("applying finder");
             MaxCountAndLongestSubsequencesFinder finder = new MaxCountAndLongestSubsequencesFinder();
             appData.getLastTrie().process(finder);
-        
+            appData.getStopWatch().stop("applying finder");
+        
+            appData.getStopWatch().start("remove permutations");
             subsequences = finder.getFoundSubsequences();
+            appData.getStopWatch().stop("remove permutations");
+            
+            appData.getStopWatch().start("drop unrepresentative");
+            dropUnrepresentative(subsequences, appData);
+            appData.getStopWatch().stop("drop unrepresentative");
             
             createNewTrie = false;
@@ -549 +571 @@
                         " tasks occurring " +
                         appData.getLastFoundSubsequences().getOccurrenceCount() + " times");
+    }
+
+    /**
+     * <p>
+     * TODO: comment
+     * </p>
+     *
+     * @param subsequences
+     */
+    private void dropUnrepresentative(Subsequences subsequences, RuleApplicationData appData) {
+        Map<Subsequence, List<SubsequenceLocation>> locations = getLocations(subsequences, appData);
+        
+        for (Map.Entry<Subsequence, List<SubsequenceLocation>> entry : locations.entrySet()) {
+            final int[] coveredActionInstances = new int[1];
+            for (SubsequenceLocation loc : entry.getValue()) {
+                for (int i = loc.getIndex(); i < loc.getIndex() + entry.getKey().size(); i++) {
+                    ITaskInstance taskInstance = loc.getSession().get(i);
+                    
+                    taskInstance.accept(new DefaultTaskInstanceTraversingVisitor() {
+                        @Override
+                        public void visit(IEventTaskInstance eventTaskInstance) {
+                            coveredActionInstances[0]++;
+                        }
+                    });
+                }
+            }
+            
+            if (coveredActionInstances[0] < minimumSequenceCoverage) {
+                subsequences.remove(entry.getKey());
+            }
+        }
     }
 
@@ -1102 +1155 @@
                 }
                 
+                // the remaining subsequences are interleaving the same amount of times, are
+                // used the same amount of times as successors and predecessors by all other
+                // detected interleaving subsequences, and their sum of the indexes of collisions
+                // is smallest or their collision index in all sessions is the smallest. This may
+                // happen for a subsequence aba for which there is an occurrence ababa. That is,
+                // the subsequence interleaves with itself. We can try to solve this by shortening
+                // the detected subsequence by one. Let us see, what happens.
+                /*boolean changedSubsequence = false;
+                for (InterleavingSubsequence interleaving : interleavings) {
+                    if (interleaving.getSubsequence().size() > 2) {
+                        appData.getLastFoundSubsequences().remove(interleaving.getSubsequence());
+                        List<ITask> shortenedSubsequence = new LinkedList<>();
+                        for (int i = 0; i < interleaving.getSubsequence().size() - 1; i++) {
+                            shortenedSubsequence.add(interleaving.getSubsequence().get(i));
+                        }
+                        appData.getLastFoundSubsequences().subsequences.add
+                            (new Subsequence(interleaving.getSubsequence().occurrenceCount,
+                                             shortenedSubsequence));
+                        
+                        changedSubsequence = true;
+                    }
+                }
+                
+                if (changedSubsequence) {
+                    continue;
+                }*/
+                
+                
                 // At this point, we can not decide anymore. But it should also not
                 // happen. Even if two subsequences ab and ba one of them should be
@@ -1131 +1212 @@
                                                            RuleApplicationData appData)
     {
+        appData.getStopWatch().start("determine interleavings");
         List<InterleavingSubsequence> interleavings = new LinkedList<InterleavingSubsequence>();
         List<Subsequence> potentialPredecessors = new LinkedList<Subsequence>();
         List<Subsequence> potentialSuccessors = new LinkedList<Subsequence>();
         
+        appData.getStopWatch().start("determine locations");
         Map<Subsequence, List<SubsequenceLocation>> allLocations =
             getLocations(subsequences, appData);
+        appData.getStopWatch().stop("determine locations");
         
         for (Subsequence subsequence : subsequences) {
@@ -1154 +1238 @@
             
             // subsequence is interleaving. First, determine its locations in the user sessions.
-            List<SubsequenceLocation> locations = allLocations.get(subsequence);
             
             List<Collision> precedingCollisions =
-                getPrecedingCollisions(subsequence, locations, potentialPredecessors, appData);
+                getPrecedingCollisions(subsequence, potentialPredecessors, allLocations, appData);
             
             List<Collision> succeedingCollisions =
-                getSucceedingCollisions(subsequence, locations, potentialSuccessors, appData);
+                getSucceedingCollisions(subsequence, potentialSuccessors, allLocations, appData);
             
             if ((precedingCollisions.size() <= 0) && (succeedingCollisions.size() <= 0)) {
@@ -1171 +1254 @@
         }
         
+        appData.getStopWatch().stop("determine interleavings");
         return interleavings;
     }
@@ -1219 +1303 @@
         }
         
+        /*
         LinkedList<LinkedList<Subsequence>> candidates = new LinkedList<LinkedList<Subsequence>>();
 
@@ -1266 +1351 @@
                 }
             }
+        }*/
+        
+        /*
+        for (IUserSession session : appData.getSessions()) {
+            LinkedList<Iterator<ITask>> candidateIterators = new LinkedList<>();
+            LinkedList<Subsequence> candidates = new LinkedList<>();
+
+            for (int i = 0; i < session.size(); i++) {
+                ITask currentTask = session.get(i).getTask();
+                
+                // create a list of candidates that may start here
+                for (Subsequence candidate : subsequences) {
+                    if (candidate.get(0) == currentTask) {
+                        candidates.add(candidate);
+                        candidateIterators.add(candidate.iterator());
+                    }
+                }
+                
+                // check which candidates continue/end here.
+                ListIterator<Iterator<ITask>> candidateItsIt = candidateIterators.listIterator();
+                ListIterator<Subsequence> candidatesIt = candidates.listIterator();
+                while (candidateItsIt.hasNext()) {
+                    Iterator<ITask> candidateIterator = candidateItsIt.next();
+                    Subsequence candidate = candidatesIt.next();
+                    if (candidateIterator.hasNext()) {
+                        ITask expectedTask = candidateIterator.next();
+                        if (expectedTask != currentTask) {
+                            // remove the iterator and the candidate from both lists.
+                            candidatesIt.remove();
+                            candidateItsIt.remove();
+                        }
+                        // else leave iterator as is and continue
+                    }
+                    else {
+                        // the candidate belonging to the iterator fully matched. Hence, store the
+                        // location and drop the candidate and its iterator
+                        candidatesIt.remove();
+                        candidateItsIt.remove();
+                        
+                        result.get(candidate).add
+                            (new SubsequenceLocation(session, i - candidate.size()));
+                    }
+                }
+            }
+            
+            // check, which further iterators match with the session end.
+            ListIterator<Iterator<ITask>> candidateItsIt = candidateIterators.listIterator();
+            ListIterator<Subsequence> candidatesIt = candidates.listIterator();
+            while (candidatesIt.hasNext()) {
+                Iterator<ITask> candidateIterator = candidateItsIt.next();
+                Subsequence candidate = candidatesIt.next();
+                if (!candidateIterator.hasNext()) {
+                    // the candidate belonging to the iterator fully matched. Hence, store the
+                    // location and drop the candidate and its iterator
+                    result.get(candidate).add
+                        (new SubsequenceLocation(session, session.size() - candidate.size()));
+                }
+            }
+        }*/
+        
+        for (IUserSession session : appData.getSessions()) {
+            for (Subsequence candidate : subsequences) {
+                int index = -1;
+                do {
+                    index = getSubListIndex(session, candidate, index + 1);
+                
+                    if (index > -1) {
+                        result.get(candidate).add(new SubsequenceLocation(session, index));
+                    }
+                }
+                while (index > -1);
+            }
         }
         
@@ -1274 +1431 @@
      *
      */
-    private List<Collision> getPrecedingCollisions(Subsequence               subsequence,
-                                                   List<SubsequenceLocation> locations,
-                                                   List<Subsequence>         potentialPredecessors,
-                                                   RuleApplicationData       appData)
+    private List<Collision> getPrecedingCollisions
+        (Subsequence                                 subsequence,
+         List<Subsequence>                           potentialPredecessors,
+         Map<Subsequence, List<SubsequenceLocation>> allLocations,
+         RuleApplicationData                         appData)
     {
         List<Collision> precedingCollisions = new LinkedList<Collision>();
-        int interleavingStartIndex;
-        int interleavingEndIndex;
-        
-        for (SubsequenceLocation location : locations) {
+        
+        for (SubsequenceLocation location : allLocations.get(subsequence)) {
             for (Subsequence predecessor : potentialPredecessors) {
-                // start where the interleaving would start
-                interleavingStartIndex = location.getIndex() - predecessor.size() + 1;
-                
-                if (interleavingStartIndex >= 0) {
-                    interleavingEndIndex =
-                        getSubListIndex(location.getSession(), predecessor, interleavingStartIndex);
-                
-                    if (interleavingStartIndex == interleavingEndIndex) {
+                for (SubsequenceLocation predecessorLocation : allLocations.get(predecessor)) {
+                    if ((location.getSession() == predecessorLocation.getSession()) &&
+                        (location.getIndex() - predecessor.size() + 1 == predecessorLocation.getIndex()))
+                    {
                         precedingCollisions.add(new Collision(location, subsequence, predecessor));
                     }
@@ -1305 +1457 @@
      *
      */
-    private List<Collision> getSucceedingCollisions(Subsequence               subsequence,
-                                                    List<SubsequenceLocation> locations,
-                                                    List<Subsequence>         potentialPredecessors,
-                                                    RuleApplicationData       appData)
+    private List<Collision> getSucceedingCollisions
+        (Subsequence                                 subsequence,
+         List<Subsequence>                           potentialSuccessors,
+         Map<Subsequence, List<SubsequenceLocation>> allLocations,
+         RuleApplicationData                         appData)
     {
         List<Collision> succeedingCollisions = new LinkedList<Collision>();
-        int interleavingStartIndex;
-        int interleavingEndIndex;
-
-        for (SubsequenceLocation location : locations) {
-            for (Subsequence successor : potentialPredecessors) {
-                interleavingStartIndex = location.getIndex() + subsequence.size() - 1;
-                interleavingEndIndex =
-                    getSubListIndex(location.getSession(), successor, interleavingStartIndex);
-
-                if (interleavingStartIndex == interleavingEndIndex) {
-                    succeedingCollisions.add(new Collision(location, subsequence, successor));
+
+        for (SubsequenceLocation location : allLocations.get(subsequence)) {
+            for (Subsequence successor : potentialSuccessors) {
+                for (SubsequenceLocation successorLocation : allLocations.get(successor)) {
+                    if ((location.getSession() == successorLocation.getSession()) &&
+                        (location.getIndex() + subsequence.size() - 1 == successorLocation.getIndex()))
+                    {
+                        succeedingCollisions.add(new Collision(location, subsequence, successor));
+                    }
                 }
             }
@@ -1789 +1940 @@
             
             if (this.currentCount == count) {
+                /*
+                // this is a potential performance improvement:
+                // the task is of interest. Ensure that only the longest remain
+                if ((foundSubsequences.size() > 0) &&
+                    (foundSubsequences.get(0).size() < foundTask.size()))
+                {
+                    foundSubsequences.clear(); 
+                }
+                
+                foundSubsequences.add(new Subsequence(currentCount, foundTask));*/
+                
                 // the task is of interest. Sort it into the other found tasks so that
                 // the longest come first
                 boolean added = false;
                 for (int i = 0; i < foundSubsequences.size(); i++) {
-                    if (foundSubsequences.get(i).size() < foundTask.size()) {
+                    if (foundSubsequences.get(i).size() <= foundTask.size()) {
                         foundSubsequences.add(i, new Subsequence(currentCount, foundTask));
                         added = true;
@@ -1823 +1985 @@
             // (i.e. come later in the sorted list) and that represent a subpart of the task
             
-            boolean removeI;
-            
-            for (int i = 0; i < foundSubsequences.size();) {
-                removeI = false;
-                boolean removeJ;
-                
-                for (int j = i + 1; j < foundSubsequences.size();) {
-                    removeJ = false;
+            boolean removeFirst;
+            ListIterator<Subsequence> iterator1 = foundSubsequences.listIterator();
+            
+            while (iterator1.hasNext()) {
+                removeFirst = false;
+                boolean removeSecond;
+                Subsequence longTask = iterator1.next();
+                
+                ListIterator<Subsequence> iterator2 =
+                    foundSubsequences.listIterator(iterator1.nextIndex());
+                
+                while (iterator2.hasNext()) {
+                    removeSecond = false;
+                    Subsequence shortTask = iterator2.next();
                     
-                    if (foundSubsequences.get(j).size() < foundSubsequences.get(i).size()) {
+                    if (shortTask.size() < longTask.size()) {
                         // found a task that is a potential subtask. Check for this and remove the
                         // subtask if needed
-                        Subsequence longTask = foundSubsequences.get(i);
-                        Subsequence shortTask = foundSubsequences.get(j);
                         
                         int index = getSubListIndex(longTask, shortTask, 0);
@@ -1860 +2026 @@
                                     // Console.traceln(Level.FINEST, "short: " + toPlainStr(shortTask));
                                     // Console.traceln(Level.FINEST, "long: " + toPlainStr(longTask));
-                                    removeI = true;
+                                    removeFirst = true;
                                 }
                                 else {
@@ -1866 +2032 @@
                                     // Console.traceln(Level.FINEST, "short: " + toPlainStr(shortTask));
                                     // Console.traceln(Level.FINEST, "long: " + toPlainStr(longTask));
-                                    removeJ = true;
+                                    removeSecond = true;
                                 }
                             }
@@ -1873 +2039 @@
                                 // Console.traceln(Level.FINEST, "short: " + toPlainStr(shortTask));
                                 // Console.traceln(Level.FINEST, "long: " + toPlainStr(longTask));
-                                removeJ = true;
+                                removeSecond = true;
                             }
                         }
                     }
                     
-                    if (removeJ) {
-                        foundSubsequences.remove(j);
-                    }
-                    else {
-                        j++;
-                    }
-                }
-                
-                if (removeI) {
-                    foundSubsequences.remove(i);
-                }
-                else {
-                    i++;
+                    if (removeSecond) {
+                        // unfortunately, this invalidates the first iterator. So recreate it after
+                        // the removal. As the removed element will be after the current position of
+                        // the first iterator, it is sufficient to remember its location
+                        int indexOf1 = iterator1.nextIndex() - 1;
+                        iterator2.remove();
+                        iterator1 = foundSubsequences.listIterator(indexOf1);
+                        iterator1.next();
+                    }
+                }
+                
+                if (removeFirst) {
+                    iterator1.remove();
                 }
             }