Index: /branches/autoquest-core-tasktrees-alignment/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/Match.java =================================================================== --- /branches/autoquest-core-tasktrees-alignment/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/Match.java (revision 1741) +++ /branches/autoquest-core-tasktrees-alignment/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/Match.java (revision 1742) @@ -13,5 +13,5 @@ * The Class Match. */ -public class Match implements Comparable,Serializable { +public class Match implements Cloneable,Comparable,Serializable { /** The Constant serialVersionUID. */ @@ -133,7 +133,7 @@ /** - * Ocurrence id sum. Used for comparing and sorting matches + * Occurrence id sum. Used for comparing and sorting matches * - * @return th + * @return the sum of all occurrence ids. */ public int ocurrenceIDSum() { @@ -168,4 +168,6 @@ } + + /** * Size. Index: /branches/autoquest-core-tasktrees-alignment/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/RuleUtils.java =================================================================== --- /branches/autoquest-core-tasktrees-alignment/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/RuleUtils.java (revision 1741) +++ /branches/autoquest-core-tasktrees-alignment/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/RuleUtils.java (revision 1742) @@ -59,5 +59,5 @@ * @return the replacement for the range */ - static ISequenceInstance createNewSubSequenceInRange( + static synchronized ISequenceInstance createNewSubSequenceInRange( ITaskInstanceList parent, int startIndex, int endIndex, ISequence model, ITaskFactory taskFactory, ITaskBuilder taskBuilder) { Index: /branches/autoquest-core-tasktrees-alignment/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRuleAlignment.java =================================================================== --- /branches/autoquest-core-tasktrees-alignment/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRuleAlignment.java (revision 1741) +++ /branches/autoquest-core-tasktrees-alignment/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRuleAlignment.java (revision 1742) @@ -74,5 +74,4 @@ public class SequenceForTaskDetectionRuleAlignment implements ISessionScopeRule { - /** The n threads. */ public static int nThreads = Runtime.getRuntime().availableProcessors() - 1; @@ -158,10 +157,11 @@ detectAndReplaceIterations(appData); appData.getStopWatch().start("task replacement"); - //Just does anything if the substitution matrix is created with the option to do so + // Just does anything if the substitution matrix is created with the + // option to do so appData.updateSubstitutionMatrix(); detectAndReplaceTasks(appData); // appData.getStopWatch().stop("task replacement"); appData.getStopWatch().stop("whole loop"); - //appData.getStopWatch().dumpStatistics(System.out); + // appData.getStopWatch().dumpStatistics(System.out); appData.getStopWatch().reset(); @@ -179,5 +179,5 @@ RuleApplicationStatus.FINISHED); } - //new TaskTreeValidator().validate(appData.getSessions()); + // new TaskTreeValidator().validate(appData.getSessions()); return appData.getResult(); } @@ -257,5 +257,11 @@ Console.traceln(Level.FINE, "Found " + appData.getMatchseqs().size() + " results"); - + + //Nothing found, we can end here + if(appData.getMatchseqs().size()==0) { + appData.detectedAndReplacedTasks=false; + return; + } + // Searching each match in all other sessions, counting its occurences searchMatchesInAllSessions(appData); @@ -268,21 +274,18 @@ public int compare(Match m1, Match m2) { int cmp = m2.occurenceCount() - m1.occurenceCount(); - if(cmp != 0) { + if (cmp != 0) { return cmp; - } - else { - cmp = m2.size()-m1.size(); - if(cmp != 0) { + } else { + cmp = m2.size() - m1.size(); + if (cmp != 0) { return cmp; - } - else { - //This should rarely happen - cmp = m2.ocurrenceIDSum()-m1.ocurrenceIDSum(); - if(cmp !=0) { + } else { + // This should rarely happen + cmp = m2.ocurrenceIDSum() - m1.ocurrenceIDSum(); + if (cmp != 0) { return cmp; - } - else { - cmp = m2.taskIdSum()-m1.taskIdSum(); - + } else { + cmp = m2.taskIdSum() - m1.taskIdSum(); + return cmp; } @@ -291,10 +294,10 @@ } }; - + Collections.sort(appData.getMatchseqs(), comparator); appData.getStopWatch().stop("detecting tasks"); - - - // Replace matches in the sessions + + Console.traceln(Level.INFO, "Preparing replacments"); + prepareReplacements(appData); Console.traceln(Level.INFO, "Replacing matches in sessions"); appData.getStopWatch().start("replacing tasks"); @@ -303,26 +306,25 @@ } - - //TODO: DEBUG METHOD + // TODO: DEBUG METHOD @SuppressWarnings("unused") private void printMatches(RuleApplicationData appData) { LinkedList matchseqs = appData.getMatchseqs(); - if(iteration>1) { - System.out.println("PRINTING MATCHES"); - for (Iterator it = matchseqs.iterator(); it.hasNext();) { - Match m = it.next(); - m.getFirstSequence().printSequence(); - m.getSecondSequence().printSequence(); - for(Iterator jt = m.getOccurences().iterator();jt.hasNext();) { - MatchOccurrence mo = jt.next(); - System.out.print(mo.getSequenceId() + " "); - } - System.out.println(); - System.out.println(); - } - } - } - - + if (iteration > 1) { + System.out.println("PRINTING MATCHES"); + for (Iterator it = matchseqs.iterator(); it.hasNext();) { + Match m = it.next(); + m.getFirstSequence().printSequence(); + m.getSecondSequence().printSequence(); + for (Iterator jt = m.getOccurences() + .iterator(); jt.hasNext();) { + MatchOccurrence mo = jt.next(); + System.out.print(mo.getSequenceId() + " "); + } + System.out.println(); + System.out.println(); + } + } + } + /** *

@@ -557,10 +559,10 @@ i++; } - if ((i == (first.length - 1)) && selectionfound) { - taskBuilder.addChild(subsequence1, appData - .getNumber2Task().get(first[i])); - taskBuilder.addChild(subsequence2, appData - .getNumber2Task().get(second[i])); - } + if ((i == (first.length - 1)) && selectionfound) { + taskBuilder.addChild(subsequence1, appData + .getNumber2Task().get(first[i])); + taskBuilder.addChild(subsequence2, appData + .getNumber2Task().get(second[i])); + } } } else { @@ -659,11 +661,12 @@ private void prepareReplacements(RuleApplicationData appData) { appData.initializeQueues(appData.getSessions().size()); - final int matchSeqSize = appData.getMatchseqs().size(); - int count = 0; - for (Iterator it = appData.getMatchseqs().iterator(); it.hasNext();) { + + for (Iterator it = appData.getMatchseqs().iterator(); it + .hasNext();) { Match m = it.next(); - for(Iterator jt=m.getOccurences().iterator();jt.hasNext();) { + for (Iterator jt = m.getOccurences().iterator(); jt + .hasNext();) { MatchOccurrence mo = jt.next(); - + Match emptyMatch = null; try { @@ -675,9 +678,7 @@ appData.getPlannedReplacements()[mo.getSequenceId()].add(m); } - count++; - - } - } - + } + } + /** * Replace matches. @@ -687,92 +688,36 @@ */ private void replaceMatches(RuleApplicationData appData) { - appData.setReplacedOccurences(new HashMap>()); - - final int matchSeqSize = appData.getMatchseqs().size(); - int count = 0; - for (int i = 0; i < matchSeqSize; i++) { - count++; - // Every pattern consists of 2 sequences, therefore the minimum - // occurrences here is 2. - // We just need the sequences also occurring in other sequences - // as well - RuleUtils.printProgressPercentage("Replacement progress", count, matchSeqSize); - if (appData.getMatchseqs().get(i).occurenceCount() > 2) { - - final ISequence task = matchAsSequence(appData, appData - .getMatchseqs().get(i)); - invalidOccurence: for (final Iterator it = appData - .getMatchseqs().get(i).getOccurences().iterator(); it - .hasNext();) { - final MatchOccurrence oc = it.next(); - - // Check if nothing has been replaced in the sequence we - // want to replace now - if (appData.getReplacedOccurrences() - .get(oc.getSequenceId()) == null) { - appData.getReplacedOccurrences().put( - oc.getSequenceId(), - new LinkedList()); - } else { - // check if we have any replaced occurence with - // indexes - // smaller than ours. If so, we need to adjust - // our start - // and endpoints - // of the replacement. - // Also do a check if we have replaced this - // specific - // MatchOccurence in this sequence already. Jump - // to the - // next occurence if this is the case. - // This is no more neccessary once the matches - // are - // harmonized. - - for (final Iterator jt = appData - .getReplacedOccurrences() - .get(oc.getSequenceId()).iterator(); jt - .hasNext();) { - final MatchOccurrence tmpOC = jt.next(); - - if ((oc.getStartindex() >= tmpOC.getStartindex()) - && (oc.getStartindex() <= tmpOC - .getEndindex())) { - continue invalidOccurence; - } - if (oc.getEndindex() >= tmpOC.getStartindex()) { - continue invalidOccurence; - - } else if (oc.getStartindex() > tmpOC.getEndindex()) { - final int diff = tmpOC.getEndindex() - - tmpOC.getStartindex(); - // Just to be sure. - if (diff > 0) { - oc.setStartindex((oc.getStartindex() - diff) + 1); - oc.setEndindex((oc.getEndindex() - diff) + 1); - } else { - Console.traceln(Level.WARNING, - "End index of a Match before start. This should never happen"); - } - } - } - } - appData.detectedAndReplacedTasks = true; - final ISequenceInstance sequenceInstances = RuleUtils - .createNewSubSequenceInRange(appData.getSessions() - .get(oc.getSequenceId()), oc - .getStartindex(), oc.getEndindex(), task, - taskFactory, taskBuilder); - oc.setEndindex((oc.getStartindex() + sequenceInstances - .size()) - RuleUtils.missedOptionals); - - // Adjust the length of the match regarding to the - // length of - // instance. (OptionalInstances may be shorter) - - appData.getReplacedOccurrences().get(oc.getSequenceId()) - .add(oc); - } - } + + final int numberSeqSize = appData.getNumberSequences().size(); + Console.traceln(Level.INFO, "replacing matches with " + nThreads + " threads"); + int newThreads = nThreads; + if (numberSeqSize < nThreads) { + newThreads = numberSeqSize; + } + final int interval = numberSeqSize / newThreads; + int rest = numberSeqSize % newThreads; + final ExecutorService executor = Executors.newFixedThreadPool(nThreads); + for (int i = 0; i <= (numberSeqSize - interval); i += interval) { + int offset = 0; + if (rest != 0) { + offset = 1; + rest--; + } + final int from = i; + final int to = i + interval + offset - 1; + Console.traceln(Level.FINE, + "Match replaceing: Creating thread with matches from " + from + + " to " + to); + // search each match in every other sequence + final ParallelMatchReplacer replacer = new ParallelMatchReplacer( + appData, from, to); + executor.execute(replacer); + i += offset; + } + executor.shutdown(); + try { + executor.awaitTermination(2, TimeUnit.HOURS); + } catch (final InterruptedException e) { + e.printStackTrace(); } } @@ -833,12 +778,14 @@ rest--; } - + final int from = i; - final int to = i + interval+offset-1; - Console.traceln(Level.FINER, "Aligning: Creating thread for sessions " + from + " till " + to); + final int to = i + interval + offset - 1; + Console.traceln(Level.FINER, + "Aligning: Creating thread for sessions " + from + " till " + + to); final ParallelPairwiseAligner aligner = new ParallelPairwiseAligner( appData, from, to); executor.execute(aligner); - i+=offset; + i += offset; } executor.shutdown(); @@ -850,7 +797,4 @@ } - - - /** * Search matches in all sessions. @@ -860,10 +804,9 @@ */ private void searchMatchesInAllSessions(RuleApplicationData appData) { - + // Prepare parallel search of matchseqs final int matchSeqSize = appData.getMatchseqs().size(); - Console.traceln(Level.INFO, - "searching for patterns ("+ matchSeqSize+") occuring most with " + nThreads - + " threads"); + Console.traceln(Level.INFO, "searching for patterns (" + matchSeqSize + + ") occuring most with " + nThreads + " threads"); int newThreads = nThreads; if (matchSeqSize < nThreads) { @@ -874,5 +817,5 @@ final ExecutorService executor = Executors.newFixedThreadPool(nThreads); Console.traceln(Level.FINER, "Interval: " + interval + " Rest: " + rest); - for (int i = 0; i <= (matchSeqSize-interval); i += interval) { + for (int i = 0; i <= (matchSeqSize - interval); i += interval) { int offset = 0; if (rest != 0) { @@ -881,12 +824,13 @@ } final int from = i; - final int to = i + interval + offset-1; - Console.traceln(Level.FINE, "Match finding: Creating thread with matches from " - + from + " to " + to); + final int to = i + interval + offset - 1; + Console.traceln(Level.FINE, + "Match finding: Creating thread with matches from " + from + + " to " + to); // search each match in every other sequence final ParallelMatchOcurrencesFinder finder = new ParallelMatchOcurrencesFinder( appData, from, to); executor.execute(finder); - i+=offset; + i += offset; } executor.shutdown(); @@ -939,4 +883,5 @@ this.to = to; } + /* * (non-Javadoc) @@ -947,5 +892,5 @@ public void run() { int count = 0; - final int size = to - from; + final int size = to + 1 - from; for (int i = from; i <= to; i++) { @@ -981,6 +926,4 @@ } } - - /** @@ -1022,5 +965,5 @@ public void run() { int count = 0; - final int size = to - from; + final int size = to +1 - from; for (int i = from; i <= to; i++) { @@ -1044,5 +987,112 @@ } } - + + /** + * The Class ParallelPairwiseAligner. + */ + private class ParallelMatchReplacer implements Runnable { + + /** The app data. */ + private final RuleApplicationData appData; + + /** The from. */ + private final int from; + + /** The to. */ + private final int to; + + /** + * Instantiates a new parallel pairwise aligner. + * + * @param appData + * the app data + * @param from + * the from + * @param to + * the to + */ + ParallelMatchReplacer(RuleApplicationData appData, int from, int to) { + this.appData = appData; + this.from = from; + this.to = to; + } + + /* + * (non-Javadoc) + * + * @see java.lang.Runnable#run() + */ + @Override + public void run() { + for (int i = from; i <= to; i++) { + + /* + * HashMap for keeping track in which sequence which replacement has + * been performed. Neccessary for updating the indices of other + * occurrences accordingly + */ + LinkedList replacedOccurrences = new LinkedList(); + invalidOccurence: while (!appData.getPlannedReplacements()[i] + .isEmpty()) { + + Match m = appData.getPlannedReplacements()[i].remove(); + // Occurrences list has just one child + MatchOccurrence oc = m.getOccurences().getFirst(); + // check if we have any replaced occurrence with + // indexes + // smaller than ours. If so, we need to adjust + // our start and end points of the replacement. + // Also do a check if we have replaced this + // specific MatchOccurence in this sequence already. + // Jump to the next occurrence if this is the case. + // This is no more necessary once the matches + // are harmonized. + + for (final Iterator jt = replacedOccurrences + .iterator(); jt.hasNext();) { + final MatchOccurrence tmpOC = jt.next(); + + if ((oc.getStartindex() >= tmpOC.getStartindex()) + && (oc.getStartindex() <= tmpOC.getEndindex())) { + continue invalidOccurence; + } + if (oc.getEndindex() >= tmpOC.getStartindex()) { + continue invalidOccurence; + + } else if (oc.getStartindex() > tmpOC.getEndindex()) { + final int diff = tmpOC.getEndindex() + - tmpOC.getStartindex(); + // Just to be sure. + if (diff > 0) { + oc.setStartindex((oc.getStartindex() - diff) + 1); + oc.setEndindex((oc.getEndindex() - diff) + 1); + } else { + Console.traceln(Level.WARNING, + "End index of a Match before start. This should never happen"); + } + } + } + synchronized (appData) { + appData.detectedAndReplacedTasks = true; + } + final ISequence task = matchAsSequence(appData, m); + final ISequenceInstance sequenceInstances = RuleUtils + .createNewSubSequenceInRange(appData.getSessions() + .get(oc.getSequenceId()), oc + .getStartindex(), oc.getEndindex(), task, + taskFactory, taskBuilder); + + // Adjust the length of the match regarding to the + // length of + // instance. (OptionalInstances may be shorter) + oc.setEndindex((oc.getStartindex() + sequenceInstances + .size()) - RuleUtils.missedOptionals); + + replacedOccurrences.add(oc); + } + } + } + } + /** * The Class RuleApplicationData. @@ -1072,13 +1122,5 @@ private final ObjectDistanceSubstitionMatrix submat; - /** - * HashMap for keeping track in which sequence which replacement has - * been performed. Neccessary for updating the indices of other - * occurrences accordingly - */ - private HashMap> replacedOccurences; - - private Queue[] plannedReplacements; - + private PriorityQueue[] plannedReplacements; /** The list of all found matches */ @@ -1105,6 +1147,4 @@ /** Stop Watch to measure performance */ private final StopWatch stopWatch; - - /** @@ -1125,8 +1165,8 @@ this.detectedAndReplacedTasks = true; } - + private void initializeQueues(int size) { - plannedReplacements = new Queue[size]; - for(int i=0;i(); } @@ -1137,8 +1177,4 @@ } - public void setPlannedReplacements(Queue[] plannedReplacements) { - this.plannedReplacements = plannedReplacements; - } - /** * Detected and replaced tasks. @@ -1151,7 +1187,7 @@ /** - * Gets the matchseqs. - * - * @return the matchseqs + * Gets the match sequences. + * + * @return the match sequences */ public LinkedList getMatchseqs() { @@ -1187,13 +1223,4 @@ /** - * Gets the replaced occurrences. - * - * @return the replaced occurences - */ - public HashMap> getReplacedOccurrences() { - return replacedOccurences; - } - - /** * Gets the result. * @@ -1223,7 +1250,7 @@ /** - * Gets the submat. - * - * @return the submat + * Gets the substitution matrix. + * + * @return the substitution matrix */ private ObjectDistanceSubstitionMatrix getSubmat() { @@ -1244,5 +1271,6 @@ * * @param task - * can be called when new tasks are created to keep track of all newly created tasks + * can be called when new tasks are created to keep track of + * all newly created tasks */ private void newTaskCreated(ITask task) { @@ -1270,15 +1298,4 @@ /** - * Sets the replaced occurences. - * - * @param replacedOccurences - * the replaced occurences - */ - public void setReplacedOccurences( - HashMap> replacedOccurences) { - this.replacedOccurences = replacedOccurences; - } - - /** * Update substitution matrix. */ @@ -1290,5 +1307,3 @@ } - - }