Ignore:
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:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRule.java

    r1958 r2131  
    2929import de.ugoe.cs.autoquest.tasktrees.taskequality.TaskEquality; 
    3030import de.ugoe.cs.autoquest.tasktrees.temporalrelation.utils.DebuggingHelper; 
     31import de.ugoe.cs.autoquest.tasktrees.treeifc.DefaultTaskInstanceTraversingVisitor; 
     32import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTaskInstance; 
    3133import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration; 
    3234import de.ugoe.cs.autoquest.tasktrees.treeifc.IIterationInstance; 
     
    102104    /** 
    103105     * <p> 
     106     * the minimum number of event task instances a sequence must cover to still detect it as a 
     107     * representative task 
     108     * </p> 
     109     */ 
     110    private int minimumSequenceCoverage;; 
     111     
     112    /** 
     113     * <p> 
    104114     * instantiates the rule and initializes it with a task equality to be considered when 
    105115     * comparing tasks as well as a task factory and builder to be used for creating task 
     
    107117     * </p> 
    108118     *  
    109      * @param minimalTaskEquality the task equality to be considered when comparing tasks 
    110      * @param taskFactory         the task factory to be used for creating substructures 
    111      * @param taskBuilder         the task builder to be used for creating substructures 
     119     * @param minimalTaskEquality     the task equality to be considered when comparing tasks 
     120     * @param taskFactory             the task factory to be used for creating substructures 
     121     * @param taskBuilder             the task builder to be used for creating substructures 
     122     * @param minimumSequenceCoverage the minimum number of event task instances a sequence must 
     123     *                                cover to still detect it as a representative task 
    112124     */ 
    113125    SequenceForTaskDetectionRule(TaskEquality minimalTaskEquality, 
    114126                                 ITaskFactory taskFactory, 
    115                                  ITaskBuilder taskBuilder) 
     127                                 ITaskBuilder taskBuilder, 
     128                                 int          minimumSequenceCoverage) 
    116129    { 
    117130        this.taskFactory = taskFactory; 
    118131        this.taskBuilder = taskBuilder; 
     132        this.minimumSequenceCoverage = minimumSequenceCoverage; 
    119133         
    120134        this.preparationTaskHandlingStrategy = new TaskHandlingStrategy(minimalTaskEquality); 
     
    468482            } 
    469483             
     484            appData.getStopWatch().start("applying finder"); 
    470485            MaxCountAndLongestSubsequencesFinder finder = new MaxCountAndLongestSubsequencesFinder(); 
    471486            appData.getLastTrie().process(finder); 
    472          
     487            appData.getStopWatch().stop("applying finder"); 
     488         
     489            appData.getStopWatch().start("remove permutations"); 
    473490            subsequences = finder.getFoundSubsequences(); 
     491            appData.getStopWatch().stop("remove permutations"); 
     492             
     493            appData.getStopWatch().start("drop unrepresentative"); 
     494            dropUnrepresentative(subsequences, appData); 
     495            appData.getStopWatch().stop("drop unrepresentative"); 
    474496             
    475497            createNewTrie = false; 
     
    549571                        " tasks occurring " + 
    550572                        appData.getLastFoundSubsequences().getOccurrenceCount() + " times"); 
     573    } 
     574 
     575    /** 
     576     * <p> 
     577     * TODO: comment 
     578     * </p> 
     579     * 
     580     * @param subsequences 
     581     */ 
     582    private void dropUnrepresentative(Subsequences subsequences, RuleApplicationData appData) { 
     583        Map<Subsequence, List<SubsequenceLocation>> locations = getLocations(subsequences, appData); 
     584         
     585        for (Map.Entry<Subsequence, List<SubsequenceLocation>> entry : locations.entrySet()) { 
     586            final int[] coveredActionInstances = new int[1]; 
     587            for (SubsequenceLocation loc : entry.getValue()) { 
     588                for (int i = loc.getIndex(); i < loc.getIndex() + entry.getKey().size(); i++) { 
     589                    ITaskInstance taskInstance = loc.getSession().get(i); 
     590                     
     591                    taskInstance.accept(new DefaultTaskInstanceTraversingVisitor() { 
     592                        @Override 
     593                        public void visit(IEventTaskInstance eventTaskInstance) { 
     594                            coveredActionInstances[0]++; 
     595                        } 
     596                    }); 
     597                } 
     598            } 
     599             
     600            if (coveredActionInstances[0] < minimumSequenceCoverage) { 
     601                subsequences.remove(entry.getKey()); 
     602            } 
     603        } 
    551604    } 
    552605 
     
    11021155                } 
    11031156                 
     1157                // the remaining subsequences are interleaving the same amount of times, are 
     1158                // used the same amount of times as successors and predecessors by all other 
     1159                // detected interleaving subsequences, and their sum of the indexes of collisions 
     1160                // is smallest or their collision index in all sessions is the smallest. This may 
     1161                // happen for a subsequence aba for which there is an occurrence ababa. That is, 
     1162                // the subsequence interleaves with itself. We can try to solve this by shortening 
     1163                // the detected subsequence by one. Let us see, what happens. 
     1164                /*boolean changedSubsequence = false; 
     1165                for (InterleavingSubsequence interleaving : interleavings) { 
     1166                    if (interleaving.getSubsequence().size() > 2) { 
     1167                        appData.getLastFoundSubsequences().remove(interleaving.getSubsequence()); 
     1168                        List<ITask> shortenedSubsequence = new LinkedList<>(); 
     1169                        for (int i = 0; i < interleaving.getSubsequence().size() - 1; i++) { 
     1170                            shortenedSubsequence.add(interleaving.getSubsequence().get(i)); 
     1171                        } 
     1172                        appData.getLastFoundSubsequences().subsequences.add 
     1173                            (new Subsequence(interleaving.getSubsequence().occurrenceCount, 
     1174                                             shortenedSubsequence)); 
     1175                         
     1176                        changedSubsequence = true; 
     1177                    } 
     1178                } 
     1179                 
     1180                if (changedSubsequence) { 
     1181                    continue; 
     1182                }*/ 
     1183                 
     1184                 
    11041185                // At this point, we can not decide anymore. But it should also not 
    11051186                // happen. Even if two subsequences ab and ba one of them should be 
     
    11311212                                                           RuleApplicationData appData) 
    11321213    { 
     1214        appData.getStopWatch().start("determine interleavings"); 
    11331215        List<InterleavingSubsequence> interleavings = new LinkedList<InterleavingSubsequence>(); 
    11341216        List<Subsequence> potentialPredecessors = new LinkedList<Subsequence>(); 
    11351217        List<Subsequence> potentialSuccessors = new LinkedList<Subsequence>(); 
    11361218         
     1219        appData.getStopWatch().start("determine locations"); 
    11371220        Map<Subsequence, List<SubsequenceLocation>> allLocations = 
    11381221            getLocations(subsequences, appData); 
     1222        appData.getStopWatch().stop("determine locations"); 
    11391223         
    11401224        for (Subsequence subsequence : subsequences) { 
     
    11541238             
    11551239            // subsequence is interleaving. First, determine its locations in the user sessions. 
    1156             List<SubsequenceLocation> locations = allLocations.get(subsequence); 
    11571240             
    11581241            List<Collision> precedingCollisions = 
    1159                 getPrecedingCollisions(subsequence, locations, potentialPredecessors, appData); 
     1242                getPrecedingCollisions(subsequence, potentialPredecessors, allLocations, appData); 
    11601243             
    11611244            List<Collision> succeedingCollisions = 
    1162                 getSucceedingCollisions(subsequence, locations, potentialSuccessors, appData); 
     1245                getSucceedingCollisions(subsequence, potentialSuccessors, allLocations, appData); 
    11631246             
    11641247            if ((precedingCollisions.size() <= 0) && (succeedingCollisions.size() <= 0)) { 
     
    11711254        } 
    11721255         
     1256        appData.getStopWatch().stop("determine interleavings"); 
    11731257        return interleavings; 
    11741258    } 
     
    12191303        } 
    12201304         
     1305        /* 
    12211306        LinkedList<LinkedList<Subsequence>> candidates = new LinkedList<LinkedList<Subsequence>>(); 
    12221307 
     
    12661351                } 
    12671352            } 
     1353        }*/ 
     1354         
     1355        /* 
     1356        for (IUserSession session : appData.getSessions()) { 
     1357            LinkedList<Iterator<ITask>> candidateIterators = new LinkedList<>(); 
     1358            LinkedList<Subsequence> candidates = new LinkedList<>(); 
     1359 
     1360            for (int i = 0; i < session.size(); i++) { 
     1361                ITask currentTask = session.get(i).getTask(); 
     1362                 
     1363                // create a list of candidates that may start here 
     1364                for (Subsequence candidate : subsequences) { 
     1365                    if (candidate.get(0) == currentTask) { 
     1366                        candidates.add(candidate); 
     1367                        candidateIterators.add(candidate.iterator()); 
     1368                    } 
     1369                } 
     1370                 
     1371                // check which candidates continue/end here. 
     1372                ListIterator<Iterator<ITask>> candidateItsIt = candidateIterators.listIterator(); 
     1373                ListIterator<Subsequence> candidatesIt = candidates.listIterator(); 
     1374                while (candidateItsIt.hasNext()) { 
     1375                    Iterator<ITask> candidateIterator = candidateItsIt.next(); 
     1376                    Subsequence candidate = candidatesIt.next(); 
     1377                    if (candidateIterator.hasNext()) { 
     1378                        ITask expectedTask = candidateIterator.next(); 
     1379                        if (expectedTask != currentTask) { 
     1380                            // remove the iterator and the candidate from both lists. 
     1381                            candidatesIt.remove(); 
     1382                            candidateItsIt.remove(); 
     1383                        } 
     1384                        // else leave iterator as is and continue 
     1385                    } 
     1386                    else { 
     1387                        // the candidate belonging to the iterator fully matched. Hence, store the 
     1388                        // location and drop the candidate and its iterator 
     1389                        candidatesIt.remove(); 
     1390                        candidateItsIt.remove(); 
     1391                         
     1392                        result.get(candidate).add 
     1393                            (new SubsequenceLocation(session, i - candidate.size())); 
     1394                    } 
     1395                } 
     1396            } 
     1397             
     1398            // check, which further iterators match with the session end. 
     1399            ListIterator<Iterator<ITask>> candidateItsIt = candidateIterators.listIterator(); 
     1400            ListIterator<Subsequence> candidatesIt = candidates.listIterator(); 
     1401            while (candidatesIt.hasNext()) { 
     1402                Iterator<ITask> candidateIterator = candidateItsIt.next(); 
     1403                Subsequence candidate = candidatesIt.next(); 
     1404                if (!candidateIterator.hasNext()) { 
     1405                    // the candidate belonging to the iterator fully matched. Hence, store the 
     1406                    // location and drop the candidate and its iterator 
     1407                    result.get(candidate).add 
     1408                        (new SubsequenceLocation(session, session.size() - candidate.size())); 
     1409                } 
     1410            } 
     1411        }*/ 
     1412         
     1413        for (IUserSession session : appData.getSessions()) { 
     1414            for (Subsequence candidate : subsequences) { 
     1415                int index = -1; 
     1416                do { 
     1417                    index = getSubListIndex(session, candidate, index + 1); 
     1418                 
     1419                    if (index > -1) { 
     1420                        result.get(candidate).add(new SubsequenceLocation(session, index)); 
     1421                    } 
     1422                } 
     1423                while (index > -1); 
     1424            } 
    12681425        } 
    12691426         
     
    12741431     * 
    12751432     */ 
    1276     private List<Collision> getPrecedingCollisions(Subsequence               subsequence, 
    1277                                                    List<SubsequenceLocation> locations, 
    1278                                                    List<Subsequence>         potentialPredecessors, 
    1279                                                    RuleApplicationData       appData) 
     1433    private List<Collision> getPrecedingCollisions 
     1434        (Subsequence                                 subsequence, 
     1435         List<Subsequence>                           potentialPredecessors, 
     1436         Map<Subsequence, List<SubsequenceLocation>> allLocations, 
     1437         RuleApplicationData                         appData) 
    12801438    { 
    12811439        List<Collision> precedingCollisions = new LinkedList<Collision>(); 
    1282         int interleavingStartIndex; 
    1283         int interleavingEndIndex; 
    1284          
    1285         for (SubsequenceLocation location : locations) { 
     1440         
     1441        for (SubsequenceLocation location : allLocations.get(subsequence)) { 
    12861442            for (Subsequence predecessor : potentialPredecessors) { 
    1287                 // start where the interleaving would start 
    1288                 interleavingStartIndex = location.getIndex() - predecessor.size() + 1; 
    1289                  
    1290                 if (interleavingStartIndex >= 0) { 
    1291                     interleavingEndIndex = 
    1292                         getSubListIndex(location.getSession(), predecessor, interleavingStartIndex); 
    1293                  
    1294                     if (interleavingStartIndex == interleavingEndIndex) { 
     1443                for (SubsequenceLocation predecessorLocation : allLocations.get(predecessor)) { 
     1444                    if ((location.getSession() == predecessorLocation.getSession()) && 
     1445                        (location.getIndex() - predecessor.size() + 1 == predecessorLocation.getIndex())) 
     1446                    { 
    12951447                        precedingCollisions.add(new Collision(location, subsequence, predecessor)); 
    12961448                    } 
     
    13051457     * 
    13061458     */ 
    1307     private List<Collision> getSucceedingCollisions(Subsequence               subsequence, 
    1308                                                     List<SubsequenceLocation> locations, 
    1309                                                     List<Subsequence>         potentialPredecessors, 
    1310                                                     RuleApplicationData       appData) 
     1459    private List<Collision> getSucceedingCollisions 
     1460        (Subsequence                                 subsequence, 
     1461         List<Subsequence>                           potentialSuccessors, 
     1462         Map<Subsequence, List<SubsequenceLocation>> allLocations, 
     1463         RuleApplicationData                         appData) 
    13111464    { 
    13121465        List<Collision> succeedingCollisions = new LinkedList<Collision>(); 
    1313         int interleavingStartIndex; 
    1314         int interleavingEndIndex; 
    1315  
    1316         for (SubsequenceLocation location : locations) { 
    1317             for (Subsequence successor : potentialPredecessors) { 
    1318                 interleavingStartIndex = location.getIndex() + subsequence.size() - 1; 
    1319                 interleavingEndIndex = 
    1320                     getSubListIndex(location.getSession(), successor, interleavingStartIndex); 
    1321  
    1322                 if (interleavingStartIndex == interleavingEndIndex) { 
    1323                     succeedingCollisions.add(new Collision(location, subsequence, successor)); 
     1466 
     1467        for (SubsequenceLocation location : allLocations.get(subsequence)) { 
     1468            for (Subsequence successor : potentialSuccessors) { 
     1469                for (SubsequenceLocation successorLocation : allLocations.get(successor)) { 
     1470                    if ((location.getSession() == successorLocation.getSession()) && 
     1471                        (location.getIndex() + subsequence.size() - 1 == successorLocation.getIndex())) 
     1472                    { 
     1473                        succeedingCollisions.add(new Collision(location, subsequence, successor)); 
     1474                    } 
    13241475                } 
    13251476            } 
     
    17891940             
    17901941            if (this.currentCount == count) { 
     1942                /* 
     1943                // this is a potential performance improvement: 
     1944                // the task is of interest. Ensure that only the longest remain 
     1945                if ((foundSubsequences.size() > 0) && 
     1946                    (foundSubsequences.get(0).size() < foundTask.size())) 
     1947                { 
     1948                    foundSubsequences.clear();  
     1949                } 
     1950                 
     1951                foundSubsequences.add(new Subsequence(currentCount, foundTask));*/ 
     1952                 
    17911953                // the task is of interest. Sort it into the other found tasks so that 
    17921954                // the longest come first 
    17931955                boolean added = false; 
    17941956                for (int i = 0; i < foundSubsequences.size(); i++) { 
    1795                     if (foundSubsequences.get(i).size() < foundTask.size()) { 
     1957                    if (foundSubsequences.get(i).size() <= foundTask.size()) { 
    17961958                        foundSubsequences.add(i, new Subsequence(currentCount, foundTask)); 
    17971959                        added = true; 
     
    18231985            // (i.e. come later in the sorted list) and that represent a subpart of the task 
    18241986             
    1825             boolean removeI; 
    1826              
    1827             for (int i = 0; i < foundSubsequences.size();) { 
    1828                 removeI = false; 
    1829                 boolean removeJ; 
    1830                  
    1831                 for (int j = i + 1; j < foundSubsequences.size();) { 
    1832                     removeJ = false; 
     1987            boolean removeFirst; 
     1988            ListIterator<Subsequence> iterator1 = foundSubsequences.listIterator(); 
     1989             
     1990            while (iterator1.hasNext()) { 
     1991                removeFirst = false; 
     1992                boolean removeSecond; 
     1993                Subsequence longTask = iterator1.next(); 
     1994                 
     1995                ListIterator<Subsequence> iterator2 = 
     1996                    foundSubsequences.listIterator(iterator1.nextIndex()); 
     1997                 
     1998                while (iterator2.hasNext()) { 
     1999                    removeSecond = false; 
     2000                    Subsequence shortTask = iterator2.next(); 
    18332001                     
    1834                     if (foundSubsequences.get(j).size() < foundSubsequences.get(i).size()) { 
     2002                    if (shortTask.size() < longTask.size()) { 
    18352003                        // found a task that is a potential subtask. Check for this and remove the 
    18362004                        // subtask if needed 
    1837                         Subsequence longTask = foundSubsequences.get(i); 
    1838                         Subsequence shortTask = foundSubsequences.get(j); 
    18392005                         
    18402006                        int index = getSubListIndex(longTask, shortTask, 0); 
     
    18602026                                    // Console.traceln(Level.FINEST, "short: " + toPlainStr(shortTask)); 
    18612027                                    // Console.traceln(Level.FINEST, "long: " + toPlainStr(longTask)); 
    1862                                     removeI = true; 
     2028                                    removeFirst = true; 
    18632029                                } 
    18642030                                else { 
     
    18662032                                    // Console.traceln(Level.FINEST, "short: " + toPlainStr(shortTask)); 
    18672033                                    // Console.traceln(Level.FINEST, "long: " + toPlainStr(longTask)); 
    1868                                     removeJ = true; 
     2034                                    removeSecond = true; 
    18692035                                } 
    18702036                            } 
     
    18732039                                // Console.traceln(Level.FINEST, "short: " + toPlainStr(shortTask)); 
    18742040                                // Console.traceln(Level.FINEST, "long: " + toPlainStr(longTask)); 
    1875                                 removeJ = true; 
     2041                                removeSecond = true; 
    18762042                            } 
    18772043                        } 
    18782044                    } 
    18792045                     
    1880                     if (removeJ) { 
    1881                         foundSubsequences.remove(j); 
    1882                     } 
    1883                     else { 
    1884                         j++; 
    1885                     } 
    1886                 } 
    1887                  
    1888                 if (removeI) { 
    1889                     foundSubsequences.remove(i); 
    1890                 } 
    1891                 else { 
    1892                     i++; 
     2046                    if (removeSecond) { 
     2047                        // unfortunately, this invalidates the first iterator. So recreate it after 
     2048                        // the removal. As the removed element will be after the current position of 
     2049                        // the first iterator, it is sufficient to remember its location 
     2050                        int indexOf1 = iterator1.nextIndex() - 1; 
     2051                        iterator2.remove(); 
     2052                        iterator1 = foundSubsequences.listIterator(indexOf1); 
     2053                        iterator1.next(); 
     2054                    } 
     2055                } 
     2056                 
     2057                if (removeFirst) { 
     2058                    iterator1.remove(); 
    18932059                } 
    18942060            } 
Note: See TracChangeset for help on using the changeset viewer.