Index: trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/utils/MostSimilarTaskDeterminer.java =================================================================== --- trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/utils/MostSimilarTaskDeterminer.java (revision 1850) +++ trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/utils/MostSimilarTaskDeterminer.java (revision 1851) @@ -15,5 +15,4 @@ package de.ugoe.cs.autoquest.tasktrees.temporalrelation.utils; -import java.util.ArrayList; import java.util.HashMap; import java.util.HashSet; @@ -25,9 +24,13 @@ import java.util.logging.Level; -import de.ugoe.cs.autoquest.tasktrees.temporalrelation.TaskInstanceComparator; +import de.ugoe.cs.autoquest.tasktrees.temporalrelation.TaskComparator; import de.ugoe.cs.autoquest.tasktrees.treeifc.DefaultTaskTraversingVisitor; +import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTaskInstance; +import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelectionInstance; import de.ugoe.cs.autoquest.tasktrees.treeifc.IStructuringTemporalRelationship; import de.ugoe.cs.autoquest.tasktrees.treeifc.ITask; import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInfo; +import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstance; +import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstanceList; import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskModel; import de.ugoe.cs.autoquest.tasktrees.treeifc.TaskMetric; @@ -61,12 +64,7 @@ /** - * default indicator for unequal tasks - */ - private static final SimilarTasks UNEQUAL_TASKS = new SimilarTasks(null, null, null, null, null); - - /** * task comparator used internally */ - private TaskInstanceComparator comparator; + private TaskComparator comparator; /** @@ -75,9 +73,12 @@ */ private Set comparisonsToSkip = new HashSet<>(); + + /** TODO comment */ + private long comparisonCounter = 0; /** * Initialize instances of this class with the task comparator to be used */ - public MostSimilarTaskDeterminer(TaskInstanceComparator comparator) { + public MostSimilarTaskDeterminer(TaskComparator comparator) { this.comparator = comparator; } @@ -95,14 +96,21 @@ */ public List getMostSimilarTasks(List tasks, ITaskModel taskModel) { - Console.println("comparing " + tasks.size() + " tasks with each other"); - - LinkedList mostSimilarTasksList = performComparisons(tasks); + Console.println("comparing " + tasks.size() + " sequences with each other"); + + LinkedList mostSimilarTasksList = performComparisons(taskModel, tasks); + + Console.println("initially found " + mostSimilarTasksList.size() + " similar sequences"); applyFilterForSmallestDiffLevel(mostSimilarTasksList); + + Console.println("only " + mostSimilarTasksList.size() + " have the smallest diff level"); + applyFilterForParents(mostSimilarTasksList); + + Console.println(mostSimilarTasksList.size() + " remain after filtering for parents"); + applyFilterForMostCoveredEvents(mostSimilarTasksList, taskModel); - Console.traceln - (Level.FINER, "calculated " + mostSimilarTasksList.size() + " most similar tasks"); + Console.println("calculated " + mostSimilarTasksList.size() + " most similar sequences"); return mostSimilarTasksList; @@ -147,4 +155,5 @@ // generated through this rule Iterator listIterator = mostSimilarTasksList.iterator(); + List similarTasksToRemove = new LinkedList(); while (listIterator.hasNext()) { @@ -161,6 +170,18 @@ TaskTreeUtils.isChild(task4, task2)) { + similarTasksToRemove.add(candidate); + break; + } + } + } + + listIterator = mostSimilarTasksList.iterator(); + + while (listIterator.hasNext()) { + SimilarTasks candidate = listIterator.next(); + + for (SimilarTasks toRemove : similarTasksToRemove) { + if (candidate == toRemove) { listIterator.remove(); - break; } } @@ -204,6 +225,6 @@ mostSimilarTasksList.clear(); - System.out.println("several comparisons for the same task exist with same diff level " + - "--> filtering for pair to be merged first"); + 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; @@ -285,13 +306,14 @@ // depth is equal. Calculate for both the similarity // based on which the merging will take place - valFirst = - SimilarTasks.getMergableLevelOfSimilarity(first, comparator).getDiffLevel(); - valSecond = - SimilarTasks.getMergableLevelOfSimilarity(second, comparator).getDiffLevel(); - - if (valSecond > valFirst) { + SimilarTasks tmp = SimilarTasks.getMergableLevelOfSimilarity(first, comparator); + valFirst = tmp != null ? tmp.getDiffLevel() : Integer.MAX_VALUE; + + tmp = SimilarTasks.getMergableLevelOfSimilarity(second, comparator); + valSecond = tmp != null ? tmp.getDiffLevel() : Integer.MAX_VALUE; + + if (valSecond < valFirst) { return second; } - else if (valSecond < valFirst) { + else if (valSecond > valFirst) { return first; } @@ -325,27 +347,95 @@ * starts several threads performing the task comparisons */ - private LinkedList performComparisons(List tasks) { + private LinkedList performComparisons(ITaskModel taskModel, List tasks) { LinkedList mostSimilarTasks = new LinkedList(); List startedRunnables = new LinkedList(); - List runnables = createRunnables(tasks, mostSimilarTasks, startedRunnables); - - // create Runnables for all buckets - int noOfParallelThreads = Math.min(2, runnables.size()); - - Console.traceln(Level.FINER, "will start " + runnables.size() + " threads"); - - // start the Threads, wait for their completion, and start the next ones if there are - // remaining + + comparisonCounter = 0; + + // groups size is minimal 100 or maximal 1000 + int groupSize = Math.max + (100, Math.min(3000, 1 + (tasks.size() / Runtime.getRuntime().availableProcessors()))); + synchronized (startedRunnables) { - while ((runnables.size() > 0) || (startedRunnables.size() > 0)) { - while ((startedRunnables.size() < noOfParallelThreads) && (runnables.size() > 0)) { - Runnable runnable = runnables.remove(0); + int start1 = 0; + int end1; + int start2; + int end2; + + do { + end1 = Math.min(start1 + groupSize, tasks.size()); + TaskTraversal[] leftHandTraversals = new TaskTraversal[end1 - start1]; + + Console.traceln(Level.FINE, "calculating left hand traversals from " + start1 + + " to " + end1); + + int index = 0; + for (int j = start1; j < end1; j++) { + leftHandTraversals[index++] = + TaskTraversal.getTraversal(tasks.get(j), null); + } + + start2 = 0; + do { + end2 = Math.min(start2 + groupSize, end1 - 1); + TaskTraversal[] rightHandTraversals = new TaskTraversal[end2 - start2]; + + if (end2 <= start1) { + Console.traceln(Level.FINE, "calculating right hand traversals from " + + start2 + " to " + end2); + + // traversals need to be created + index = 0; + for (int j = start2; j < end2; j++) { + rightHandTraversals[index++] = + TaskTraversal.getTraversal(tasks.get(j), null); + } + + } + else { + // traversals can be reused + Console.traceln(Level.FINE, "reusing traversals for right hand from " + + start2 + " to " + end2); + + rightHandTraversals = leftHandTraversals; + } + + Runnable runnable = new CompareRunnable(taskModel, leftHandTraversals, + rightHandTraversals, + mostSimilarTasks, startedRunnables); + + while (startedRunnables.size() >= + Math.max(1, Runtime.getRuntime().availableProcessors())) + { + try { + Console.traceln(Level.FINER, "waiting for next thread to finish"); + startedRunnables.wait(); + Console.traceln(Level.FINER, "thread finished"); + } + catch (InterruptedException e) { + // should not happen + Console.logException(e); + } + } + + Console.traceln(Level.FINER, "starting next thread"); startedRunnables.add(runnable); new Thread(runnable).start(); - Console.traceln(Level.FINEST, "started next thread"); - } - + Console.traceln(Level.FINER, "started next thread " + runnable); + + start2 = end2; + } + while (end2 < (end1 - 1)); + + start1 = end1; + } + while (end1 < tasks.size()); + + + while (startedRunnables.size() > 0) { try { + Console.traceln(Level.FINER, "waiting for next thread to finish"); startedRunnables.wait(); + Console.traceln(Level.FINER, "thread finished"); } catch (InterruptedException e) { @@ -353,54 +443,16 @@ Console.logException(e); } - - Console.traceln(Level.FINEST, "thread finished (" + runnables.size() + ", " + - startedRunnables.size() + ")"); - } - } - Console.traceln(Level.FINER, "all threads finished"); + } + } + + Console.traceln + (Level.FINER, "all threads finished, " + comparisonCounter + " comparisons done"); + + if (comparisonCounter != (((tasks.size() - 1) * tasks.size()) / 2)) { + throw new RuntimeException(comparisonCounter + " " + + (((tasks.size() - 1) * tasks.size()) / 2)); + } return mostSimilarTasks; - } - - /** - * creates runnables for comparing tasks by subdiving the input set of comparisons into - * several subsets where each is compared in a corresponding runnable. The subsets are - * at most 150000 comparisons large. - */ - private List createRunnables(List tasks, - LinkedList mostSimilarTasksList, - List startedRunnables) - { - // subdivide comparisons into buckets to be spread to different threads - int noOfComparisons = 0; - int noOfScheduledComparisons = 0; - List bucketIndexes = new ArrayList(); - - bucketIndexes.add(0); - - for (int i = 0; i < tasks.size(); i++) { - noOfComparisons += i; - - if ((noOfComparisons - noOfScheduledComparisons) > 150000) { - bucketIndexes.add(i); - noOfScheduledComparisons = noOfComparisons; - } - } - - bucketIndexes.add(tasks.size()); - - Console.traceln(Level.FINER, "scheduling " + noOfComparisons + " comparisons"); - - List runnables = new LinkedList(); - - for (int i = 1; i < bucketIndexes.size(); i++) { - CompareRunnable runnable = new CompareRunnable - (tasks, bucketIndexes.get(i - 1), bucketIndexes.get(i), mostSimilarTasksList, - startedRunnables); - - runnables.add(runnable); - } - - return runnables; } @@ -468,12 +520,12 @@ /** */ - private List taskList; + private ITaskModel taskModel; /** */ - private int startIndex; + private TaskTraversal[] leftHandTraversals; /** */ - private int endIndex; - + private TaskTraversal[] rightHandTraversals; + /** */ private List mostSimilarTasksList; @@ -485,13 +537,13 @@ * */ - public CompareRunnable(List taskList, - int startIndex, - int endIndex, - List mostSimilarTasksList, - List unfinishedRunnables) + public CompareRunnable(ITaskModel taskModel, + TaskTraversal[] leftHandTraversals, + TaskTraversal[] rightHandTraversals, + List mostSimilarTasksList, + List unfinishedRunnables) { - this.taskList = taskList; - this.startIndex = startIndex; - this.endIndex = endIndex; + this.taskModel = taskModel; + this.leftHandTraversals = leftHandTraversals; + this.rightHandTraversals = rightHandTraversals; this.mostSimilarTasksList = mostSimilarTasksList; this.unfinishedRunnables = unfinishedRunnables; @@ -503,41 +555,71 @@ @Override public void run() { - int noOfComparisons = 0; - - for (int i = startIndex; i < endIndex; i++) { - noOfComparisons += i; - } - - System.out.println("performing " + noOfComparisons + " comparisons"); - - SimilarTasks mostSimilarTasks = UNEQUAL_TASKS; + SimilarTasks mostSimilarTasks = SimilarTasks.UNEQUAL_TASKS; + int mostSimilarDiffLevel = MAX_DIFF_LEVEL; List allMostSimilarTasks = new LinkedList(); - - for (int i = startIndex + 1; i < endIndex; i++) { - /*if (appData.isSelfCreatedTask(taskList.get(i))) { - continue; - }*/ - - for (int j = startIndex; j < i; j++) { - /*if (appData.isSelfCreatedTask(taskList.get(j))) { - continue; - }*/ + int counter = 0; + + LEFT_HAND_TRAVERSAL: + for (int i = 0; i < leftHandTraversals.length; i++) { + + ITask leftHandTask = leftHandTraversals[i].getTask(); + + RIGHT_HAND_TRAVERSAL: + for (int j = 0; j < rightHandTraversals.length; j++) { + + ITask rightHandTask = rightHandTraversals[j].getTask(); - if (isComparisonToSkip(taskList.get(i), taskList.get(j))) { - continue; - } - - SimilarTasks similarTasks = SimilarTasks.compareTasks - (taskList.get(i), taskList.get(j), comparator); - - if (similarTasks.isInBetweenDifference()) { - if (similarTasks.getDiffLevel() < mostSimilarTasks.getDiffLevel()) { - mostSimilarTasks = similarTasks; - allMostSimilarTasks.clear(); - allMostSimilarTasks.add(similarTasks); + try { + if (leftHandTask == rightHandTask) { + continue LEFT_HAND_TRAVERSAL; } - else if (similarTasks.getDiffLevel() == mostSimilarTasks.getDiffLevel()) { - allMostSimilarTasks.add(similarTasks); + + counter++; + + if (isComparisonToSkip(leftHandTask, rightHandTask)) { + continue RIGHT_HAND_TRAVERSAL; } + + if (!isBasicallySimilar(leftHandTraversals[i], rightHandTraversals[j])) { + continue RIGHT_HAND_TRAVERSAL; + } + + SimilarTasks similarTasks1 = SimilarTasks.compareTraversals + (leftHandTraversals[i], rightHandTraversals[j], comparator); + + SimilarTasks similarTasks2 = SimilarTasks.compareTraversals + (rightHandTraversals[j], leftHandTraversals[i], comparator); + + if ((similarTasks1.getDiffLevel() <= mostSimilarDiffLevel) || + (similarTasks2.getDiffLevel() <= mostSimilarDiffLevel)) + { + SimilarTasks similarTasks = + getSimilarTasksToPrefer(similarTasks1, similarTasks2); + + if (similarTasks.isInBetweenDifference()) { + if (similarTasks.getDiffLevel() < mostSimilarDiffLevel) { + mostSimilarTasks = similarTasks; + mostSimilarDiffLevel = mostSimilarTasks.getDiffLevel(); + allMostSimilarTasks.clear(); + allMostSimilarTasks.add(similarTasks); + } + else if (similarTasks.getDiffLevel() == mostSimilarDiffLevel) { + allMostSimilarTasks.add(similarTasks); + } + } + } + } + catch (Exception e) { + e.printStackTrace(); + + SimilarTasks similarTasks1 = SimilarTasks.compareTraversals + (leftHandTraversals[i], rightHandTraversals[j], comparator); + + SimilarTasks similarTasks2 = SimilarTasks.compareTraversals + (rightHandTraversals[j], leftHandTraversals[i], comparator); + + similarTasks1.dump(System.err); + + similarTasks2.dump(System.err); } } @@ -546,6 +628,6 @@ synchronized (unfinishedRunnables) { mostSimilarTasksList.addAll(allMostSimilarTasks); - - //System.out.println("notifying finish"); + comparisonCounter += counter; + for (int i = 0; i < unfinishedRunnables.size(); i++) { if (unfinishedRunnables.get(i) == this) { @@ -557,4 +639,209 @@ } + /** + * + */ + private boolean isBasicallySimilar(TaskTraversal traversal1, TaskTraversal traversal2) { + int length1 = traversal1.size(); + int length2 = traversal2.size(); + int maxLength = Math.max(length1, length2); + int lengthDiff = 100 * Math.abs(length1 - length2) / maxLength; + + if (lengthDiff > MAX_DIFF_LEVEL) { + return false; + } + else { + return true; + } + } + + /** + *

+ * TODO: comment + *

+ * + * @param similarTasks1 + * @param similarTasks2 + * @return + */ + private SimilarTasks getSimilarTasksToPrefer(SimilarTasks similarTasks1, + SimilarTasks similarTasks2) + { + if (similarTasks2.getDiffLevel() > similarTasks1.getDiffLevel()) { + return similarTasks2; + } + else if (similarTasks1.getDiffLevel() > similarTasks2.getDiffLevel()) { + return similarTasks1; + } + else if (similarTasks1.getDiffLevel() == similarTasks2.getDiffLevel()) { + ITask first = similarTasks1.getLeftHandSide(); + ITask second = similarTasks2.getLeftHandSide(); + + long valFirst = getTaskMetric(first, TaskMetric.EVENT_COVERAGE); + long valSecond = getTaskMetric(second, TaskMetric.EVENT_COVERAGE); + + if (valSecond > valFirst) { + return similarTasks2; + } + else if (valSecond < valFirst) { + return similarTasks1; + } + + // no of covered events is equal, try to distinguish by count + + valFirst = getTaskMetric(first, TaskMetric.COUNT); + valSecond = getTaskMetric(second, TaskMetric.COUNT); + + if (valSecond > valFirst) { + return similarTasks2; + } + else if (valSecond < valFirst) { + return similarTasks1; + } + + // count is equal, try to distinguish by depth + + valFirst = getTaskMetric(first, TaskMetric.DEPTH); + valSecond = getTaskMetric(second, TaskMetric.DEPTH); + + if (valSecond < valFirst) { + return similarTasks2; + } + else if (valSecond > valFirst) { + return similarTasks1; + } + + // no of covered events is equal, try to distinguish by count + + valFirst = cumulateTaskMetric(first, TaskMetric.COUNT); + valSecond = cumulateTaskMetric(second, TaskMetric.COUNT); + + if (valSecond > valFirst) { + return similarTasks2; + } + else if (valSecond < valFirst) { + return similarTasks1; + } + + // depth is equal. Calculate for both the similarity + // based on which the merging will take place + SimilarTasks tmp = + SimilarTasks.getMergableLevelOfSimilarity(similarTasks1, comparator); + + valFirst = tmp != null ? tmp.getDiffLevel() : Integer.MAX_VALUE; + + tmp = SimilarTasks.getMergableLevelOfSimilarity(similarTasks2, comparator); + valSecond = tmp != null ? tmp.getDiffLevel() : Integer.MAX_VALUE; + + if (valSecond < valFirst) { + return similarTasks2; + } + else if (valSecond > valFirst) { + return similarTasks1; + } + + valFirst = getFirstTimestamp(first); + valSecond = getFirstTimestamp(second); + + if (valSecond > valFirst) { + return similarTasks1; + } + else if (valSecond < valFirst) { + return similarTasks2; + } + + similarTasks1.dump(System.out); + similarTasks2.dump(System.out); + + throw new RuntimeException + ("several tasks are similar so that it is undecidable which to merge first"); + } + + return null; + } + + /** + *

+ * TODO: comment + *

+ * + * @param first + * @param eventCoverage + * @param taskModel2 + * @return + */ + private int getTaskMetric(ITask task, TaskMetric metric) { + ITaskInfo info = taskModel.getTaskInfo(task); + return info.getMeasureValue(metric); + } + + /** + * convenience method to get the cumulative value of a task metric + */ + private int cumulateTaskMetric(ITask task, + final TaskMetric metric) + { + final int[] value = new int[1]; + value[0] = 0; + + DefaultTaskTraversingVisitor visitor = new DefaultTaskTraversingVisitor() { + @Override + public void visit(IStructuringTemporalRelationship relationship) { + value[0] += taskModel.getTaskInfo(relationship).getMeasureValue(metric); + super.visit(relationship); + } + }; + + task.accept(visitor); + + return value[0]; + } + + /** + *

+ * TODO: comment + *

+ * + * @param first + * @return + */ + private long getFirstTimestamp(ITask task) { + long timestamp = Long.MAX_VALUE; + + for (ITaskInstance instance : task.getInstances()) { + ITaskInstance eventTaskInstance = instance; + + do { + if (eventTaskInstance instanceof ITaskInstanceList) { + eventTaskInstance = ((ITaskInstanceList) eventTaskInstance).get(0); + } + else if (eventTaskInstance instanceof ISelectionInstance) { + eventTaskInstance = ((ISelectionInstance) eventTaskInstance).getChild(); + } + } + while (!(eventTaskInstance instanceof IEventTaskInstance)); + + if (eventTaskInstance != null) { + long newTimestamp = + ((IEventTaskInstance) eventTaskInstance).getEvent().getTimestamp(); + + if (timestamp > newTimestamp) { + timestamp = newTimestamp; + } + } + } + + return timestamp; + } + + /* (non-Javadoc) + * @see java.lang.Object#toString() + */ + @Override + public String toString() { + return "CompareThread(" + leftHandTraversals.length + ", " + + rightHandTraversals.length + ")"; + } + } }