Changeset 1981

Timestamp:

06/30/15 10:22:55 (9 years ago)

Author:

pharms

Message:

• corrected filter for most covered events to decide which task pair to merge first
• merging of identical sequences can be done in any order --> adapted selection of pair to merge first to handle identical sequences based on their smallest id
• merging only most prominent tasks (except identical tasks) --> otherwise too many mergings of noise
• new maximum diff level is 25

File:

• trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/utils/MostSimilarTaskDeterminer.java (modified) (13 diffs)

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

@@ -15 +15 @@
 package de.ugoe.cs.autoquest.tasktrees.temporalrelation.utils;
 
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
 import java.util.HashMap;
 import java.util.HashSet;
@@ -58 +61 @@
 
     /**
-     * If this similarity level is exceeded, two tasks are not considered similar anymore. 33 means
-     * that at most 33% of the elements of both task traversals are not the same.
-     */
-    private static int MAX_DIFF_LEVEL = 33;
+     * If this similarity level is exceeded, two tasks are not considered similar anymore. 25 means
+     * that at most 25% of the elements of both task traversals are not the same.
+     */
+    private static int MAX_DIFF_LEVEL = 25;
     
     /**
@@ -144 +147 @@
             }
             
-            Console.println("smallest diff level is " + smallestDiffLevel);
+            Console.println("smallest diff level is " + smallestDiffLevel + " (max is " +
+                            MAX_DIFF_LEVEL + ")");
         }
         else {
@@ -200 +204 @@
      */
     private void applyFilterForMostCoveredEvents(LinkedList<SimilarTasks> mostSimilarTasksList,
-                                                 ITaskModel               taskModel)
+                                                 final ITaskModel         taskModel)
     {
-        for (SimilarTasks similarTasks : mostSimilarTasksList) {
-            System.out.println(similarTasks.getLeftHandSide() + "  " + similarTasks.getRightHandSide());
-        }
-        
-        // check, if several remaining similar tasks refer to the same task
-        Map<ITask, LinkedList<SimilarTasks>> referredTasks =
-            new HashMap<ITask, LinkedList<SimilarTasks>>();
-        
-        for (SimilarTasks similarTasks : mostSimilarTasksList) {
-            ensureMapping(similarTasks.getLeftHandSide(), similarTasks, referredTasks);
-            ensureMapping(similarTasks.getRightHandSide(), similarTasks, referredTasks);
-        }
-        
-        // remove all entries of tasks occurring only once
-        List<ITask> tasksOccuringOnce = new LinkedList<ITask>();
-
-        for (Map.Entry<ITask, LinkedList<SimilarTasks>> entry : referredTasks.entrySet()) {
-            if (entry.getValue().size() <= 1) {
-                tasksOccuringOnce.add(entry.getKey());
-            }
-        }
-
-        for (ITask taskToRemove : tasksOccuringOnce) {
-            referredTasks.remove(taskToRemove);
-        }
-
-        // if there are remaining tasks occurring several times, try to extract one similar tasks
-        // object, that should be merged first
-
-        if (referredTasks.size() > 0) {
-            mostSimilarTasksList.clear();
-
-            Console.traceln(Level.FINEST, "several comparisons for the same task exist with " +
-                            "same diff level --> filtering for pair to be merged first");
-
-            SimilarTasks firstToMerge = null;
-
-            for (LinkedList<SimilarTasks> pairs : referredTasks.values()) {
-                for (SimilarTasks current : pairs) {
-                    if (firstToMerge == null) {
-                        firstToMerge = current;
+        List<SimilarTasks> sortedList = new ArrayList<>(mostSimilarTasksList);
+
+        // sort the list of similar tasks based on which to merge first
+        Collections.sort(sortedList, new Comparator<SimilarTasks>() {
+            @Override
+            public int compare(SimilarTasks first, SimilarTasks second) {
+                SimilarTasks toMergeFirst = getFirstToMerge(first, second, taskModel);
+
+                if (toMergeFirst == first) {
+                    return -1;
+                }
+                else if (toMergeFirst == null) {
+                    return 0;
+                }
+                else {
+                    return 1;
+                }
+            }
+        });
+
+        // the first in the ordered list is the first to merge, except there are several
+        // firsts in the lists for which it can not be decided which to merge first
+
+        // now remove all subsequent pairs also referring tasks referred by first pairs
+        Set<ITask> referredTasks = new HashSet<>();
+        
+        int index = 0;
+        while (index < sortedList.size()) {
+            SimilarTasks pair = sortedList.get(index);
+            
+            if (referredTasks.contains(pair.getLeftHandSide()) ||
+                referredTasks.contains(pair.getRightHandSide()))
+            {
+                // we found a pair that refers to a task already referred by a preceding pair.
+                // The pair can be removed, if the previous pair referring to the same task also
+                // is to be merged first.
+                for (int i = 0; i < index; i++) {
+                    SimilarTasks previousPair = sortedList.get(i);
+                    if ((previousPair.getLeftHandSide() == pair.getLeftHandSide()) ||
+                        (previousPair.getLeftHandSide() == pair.getRightHandSide()) ||
+                        (previousPair.getRightHandSide() == pair.getLeftHandSide()) ||
+                        (previousPair.getRightHandSide() == pair.getRightHandSide()))
+                    {
+                        if (getFirstToMerge(previousPair, pair, taskModel) == null) {
+                            for (SimilarTasks tmp : sortedList) {
+                                tmp.dump(System.out);
+                            }
+
+                            throw new RuntimeException("several tasks are similar so that it is " +
+                                                       "undecidable which to merge first");
+                        }
                     }
-                    else if (firstToMerge != current) {
-                        firstToMerge = getFirstToMerge(firstToMerge, current, taskModel);
-                    }
-                }
-            }
-            
-            if (firstToMerge != null) {
-                mostSimilarTasksList.add(firstToMerge);
-            }
-        }
-        
+                }
+                
+                sortedList.remove(index);
+            }
+            else {
+                referredTasks.add(pair.getLeftHandSide());
+                referredTasks.add(pair.getRightHandSide());
+                index++;
+            }
+        }
+        
+        // now the list is sorted and contains at most one pair for each task referred multiple
+        // times
+        mostSimilarTasksList.clear();
+        mostSimilarTasksList.addAll(sortedList);
     }
 
@@ -327 +345 @@
             return first;
         }
-
-        first.dump(System.out);
-        second.dump(System.out);
-
-        throw new RuntimeException
-            ("several tasks are similar so that it is undecidable which to merge first");
-    }
-
-    /**
-     *
-     */
-    private void ensureMapping(ITask                                task,
-                               SimilarTasks                         similarTasks,
-                               Map<ITask, LinkedList<SimilarTasks>> map)
-    {
-        LinkedList<SimilarTasks> value = map.get(task);
-        
-        if (value == null) {
-            value = new LinkedList<SimilarTasks>();
-            map.put(task, value);
-        }
-        
-        value.add(similarTasks);
-    }
-
+        
+        // it may be the case that both tasks are event identical. For example, if through a
+        // merge formerly different children became the same. In this case, merging can be
+        // done in any order. Hence, just return any of the given to be merged first. To ensure
+        // to not define a circle of three tasks to be merged, decide using the ids of the
+        // identical tasks.
+        if ((first.getDiffLevel() == 0) && (second.getDiffLevel() == 0)) {
+            ITask taskWithSmallestId = first.getLeftHandSide();
+            SimilarTasks pairToReturn = first;
+            
+            if (taskWithSmallestId.getId() > first.getRightHandSide().getId()) {
+                taskWithSmallestId = first.getRightHandSide();
+            }
+            
+            if (taskWithSmallestId.getId() > second.getLeftHandSide().getId()) {
+                taskWithSmallestId = second.getLeftHandSide();
+                pairToReturn = second;
+            }
+            
+            if (taskWithSmallestId.getId() > second.getRightHandSide().getId()) {
+                taskWithSmallestId = second.getRightHandSide();
+                pairToReturn = second;
+            }
+            
+            return pairToReturn;
+        }
+        
+        return null;
+    }
 
     /**
@@ -357 +379 @@
      */
     private LinkedList<SimilarTasks> performComparisons(ITaskModel taskModel, List<ITask> tasks) {
+        Set<ITask> mostProminentTasks = getMostProminentTasks(taskModel, tasks);
         LinkedList<SimilarTasks> mostSimilarTasks = new LinkedList<SimilarTasks>();
         List<Runnable> startedRunnables = new LinkedList<Runnable>();
@@ -412 +435 @@
                     Runnable runnable = new CompareRunnable(taskModel, leftHandTraversals,
                                                             rightHandTraversals,
+                                                            mostProminentTasks,
                                                             mostSimilarTasks, startedRunnables);
                     
@@ -468 +492 @@
 
     /**
+     *
+     */
+    private Set<ITask> getMostProminentTasks(ITaskModel model, List<ITask> tasks) {
+        Map<Integer, List<ITask>> sortedTasks = new HashMap<>();
+
+        int maxCoverage = 0;
+
+        for (ITask task : tasks) {
+            int coveredEvents = model.getTaskInfo(task).getMeasureValue(TaskMetric.EVENT_COVERAGE);
+
+            List<ITask> tasksWithSameCoverage = sortedTasks.get(coveredEvents);
+
+            if (tasksWithSameCoverage == null) {
+                tasksWithSameCoverage = new LinkedList<>();
+                sortedTasks.put(coveredEvents, tasksWithSameCoverage);
+            }
+
+            tasksWithSameCoverage.add(task);
+
+            maxCoverage = Math.max(maxCoverage, coveredEvents);
+        }
+
+        Set<ITask> result = new HashSet<>();
+
+        for (int i = maxCoverage; i > 0; i--) {
+            List<ITask> tasksWithSameCoverage = sortedTasks.get(i);
+
+            if (tasksWithSameCoverage != null) {
+                result.addAll(tasksWithSameCoverage);
+
+                if (result.size() * 5 >= tasks.size()) {
+                    break;
+                }
+            }
+        }
+
+        return result;
+    }
+
+    /**
      * convenience method to get the value of a task metric
      */
@@ -539 +603 @@
         
         /** */
+        private Set<ITask> mostProminentTasks;
+        
+        /** */
         private List<SimilarTasks> mostSimilarTasksList;
 
@@ -550 +617 @@
                                TaskTraversal[]    leftHandTraversals,
                                TaskTraversal[]    rightHandTraversals,
+                               Set<ITask>         mostProminentTasks,
                                List<SimilarTasks> mostSimilarTasksList,
                                List<Runnable>     unfinishedRunnables)
@@ -556 +624 @@
             this.leftHandTraversals = leftHandTraversals;
             this.rightHandTraversals = rightHandTraversals;
+            this.mostProminentTasks = mostProminentTasks;
             this.mostSimilarTasksList = mostSimilarTasksList;
             this.unfinishedRunnables = unfinishedRunnables;
@@ -585 +654 @@
                             continue LEFT_HAND_TRAVERSAL;
                         }
-
+                        
                         counter++;
 
@@ -598 +667 @@
                         effectiveComparisons++;
 
-                        SimilarTasks similarTasks1 = SimilarTasks.compareTraversals
+                        SimilarTasks similarTasks = SimilarTasks.compareTraversals
                             (leftHandTraversals[i], rightHandTraversals[j], comparator);
 
-                        SimilarTasks similarTasks2 = SimilarTasks.compareTraversals
-                            (rightHandTraversals[j], leftHandTraversals[i], comparator);
-
-                        if ((similarTasks1.getDiffLevel() <= mostSimilarDiffLevel) ||
-                            (similarTasks2.getDiffLevel() <= mostSimilarDiffLevel))
+                        if (similarTasks.getDiffLevel() > 0) {
+                            if (!mostProminentTasks.contains(leftHandTask) ||
+                                !mostProminentTasks.contains(rightHandTask))
+                            {
+                                // the tasks are not fully identical. Hence, we merge them only,
+                                // if both are most prominent ones. If they were fully identical,
+                                // they may have changed through merging initially different
+                                // children which may have become the same. In that case, they
+                                // must be merged even if they are not most prominent.
+                                continue RIGHT_HAND_TRAVERSAL;
+                            }
+
+                            SimilarTasks similarTasks2 = SimilarTasks.compareTraversals
+                                (rightHandTraversals[j], leftHandTraversals[i], comparator);
+                            
+                            if ((similarTasks.getDiffLevel() <= mostSimilarDiffLevel) ||
+                                (similarTasks2.getDiffLevel() <= mostSimilarDiffLevel)) {
+                                
+                                similarTasks = getSimilarTasksToPrefer(similarTasks, similarTasks2);
+                            }
+                        }
+                        
+                        if (similarTasks.isInBetweenDifference() ||
+                            (similarTasks.getPatch().getDeltas().size() == 0))
                         {
-                            SimilarTasks similarTasks =
-                                getSimilarTasksToPrefer(similarTasks1, similarTasks2);
-
-                            if (similarTasks.isInBetweenDifference() ||
-                                (similarTasks.getPatch().getDeltas().size() == 0))
-                            {
-                                if (similarTasks.getDiffLevel() < mostSimilarDiffLevel) {
-                                    mostSimilarTasks = similarTasks;
-                                    mostSimilarDiffLevel = mostSimilarTasks.getDiffLevel();
-                                    allMostSimilarTasks.clear();
-                                    allMostSimilarTasks.add(similarTasks);
-                                }
-                                else if (similarTasks.getDiffLevel() == mostSimilarDiffLevel) {
-                                    allMostSimilarTasks.add(similarTasks);
-                                }
+                            if (similarTasks.getDiffLevel() < mostSimilarDiffLevel) {
+                                mostSimilarTasks = similarTasks;
+                                mostSimilarDiffLevel = mostSimilarTasks.getDiffLevel();
+                                allMostSimilarTasks.clear();
+                                allMostSimilarTasks.add(similarTasks);
+                            }
+                            else if (similarTasks.getDiffLevel() == mostSimilarDiffLevel) {
+                                allMostSimilarTasks.add(similarTasks);
                             }
                         }