Ignore:
Timestamp:
03/08/12 09:38:19 (13 years ago)
Author:
sherbold
Message:
  • optimized the run-time of the command generateGreedy. Worst-case nearly unchanged, but the average run-time has been reduced to 1/3 of the worst case.
  • The optional parameter validEnd has been added to the command generateGreedy. If the parameter is true, only sequences that end in de.ugoe.cs.eventbench.data.Event.ENDEVENT are generated. If the parameter is false, the final event is arbitrary.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/EventBenchConsole/src/de/ugoe/cs/eventbench/commands/CMDgenerateGreedy.java

    r311 r395  
    22 
    33import java.security.InvalidParameterException; 
    4 import java.util.ArrayList; 
     4import java.util.Collection; 
     5import java.util.Iterator; 
    56import java.util.LinkedHashSet; 
    67import java.util.LinkedList; 
     
    1011 
    1112import de.ugoe.cs.eventbench.CommandHelpers; 
    12 import de.ugoe.cs.eventbench.coverage.CoverageCalculatorProcess; 
    1313import de.ugoe.cs.eventbench.coverage.SequenceTools; 
    1414import de.ugoe.cs.eventbench.data.Event; 
     
    5050                int coverageDepth; 
    5151                float desiredCoverage; 
     52                boolean validEnd = true; 
    5253                try { 
    5354                        modelname = (String) parameters.get(0); 
     
    5758                        coverageDepth = Integer.parseInt((String) parameters.get(4)); 
    5859                        desiredCoverage = Float.parseFloat((String) parameters.get(5)); 
     60                        if (parameters.size() >= 7) { 
     61                                validEnd = Boolean.parseBoolean((String) parameters.get(6)); 
     62                        } 
    5963                } catch (Exception e) { 
    6064                        throw new InvalidParameterException(); 
     
    7478 
    7579                // set up everything 
    76                 List<List<? extends Event<?>>> allSequences = new ArrayList<List<? extends Event<?>>>(); 
     80                List<List<? extends Event<?>>> allSequences = new LinkedList<List<? extends Event<?>>>(); 
    7781                for (int length = minLength; length <= maxLength; length++) { 
    78                         allSequences.addAll(model.generateValidSequences(length + 2)); 
     82                        if (validEnd) { 
     83                                allSequences.addAll(model.generateValidSequences(length + 2)); 
     84                        } else { 
     85                                allSequences.addAll(model.generateSequences(length + 1, true)); 
     86                        } 
    7987                } 
    8088                Console.traceln("" + allSequences.size() + " possible"); 
    8189 
    82                 Set<List<? extends Event<?>>> allSubSeqs = SequenceTools 
    83                                 .containedSubSequences(allSequences, coverageDepth); 
     90                Collection<List<? extends Event<?>>> allSubSeqs = model 
     91                                .generateSequences(coverageDepth); 
    8492                Map<List<? extends Event<?>>, Double> weightMap = SequenceTools 
    8593                                .generateWeights(model, allSubSeqs); 
    8694                Set<List<? extends Event<?>>> coveredSubSeqs = new LinkedHashSet<List<? extends Event<?>>>(); 
    8795 
    88                 List<Set<List<? extends Event<?>>>> containedSubSeqs = new ArrayList<Set<List<? extends Event<?>>>>( 
    89                                 allSequences.size()); 
     96                List<Set<List<? extends Event<?>>>> containedSubSeqs = new LinkedList<Set<List<? extends Event<?>>>>(); 
    9097                for (List<? extends Event<?>> sequence : allSequences) { 
    9198                        List<List<? extends Event<?>>> wrapper = new LinkedList<List<? extends Event<?>>>(); 
     
    96103                } 
    97104 
    98                 Double[] sequenceGain = new Double[allSequences.size()]; 
    99105                List<List<? extends Event<?>>> testSuite = new LinkedList<List<? extends Event<?>>>(); 
    100                 CoverageCalculatorProcess coverageCalculator = new CoverageCalculatorProcess( 
    101                                 model, testSuite, coverageDepth); 
    102106                double currentCoverage = 0.0d; 
    103107 
    104108                // Build test suite 
     109                double prevGain = 1.0d; 
     110                boolean gainEqual = false; 
    105111                while (currentCoverage < desiredCoverage) { 
    106                         for (int i = 0; i < allSequences.size(); i++) { 
     112                        Double[] sequenceGain = new Double[allSequences.size()]; 
     113                        int i = 0; 
     114                        for (Set<List<? extends Event<?>>> containedSubSeq : containedSubSeqs) { 
    107115                                double gain = 0.0d; 
    108                                 for (List<? extends Event<?>> subSeq : containedSubSeqs.get(i)) { 
     116                                Iterator<List<? extends Event<?>>> subSeqIter = containedSubSeq 
     117                                                .iterator(); 
     118                                while (subSeqIter.hasNext()) { 
     119                                        List<? extends Event<?>> subSeq = subSeqIter.next(); 
    109120                                        if (!coveredSubSeqs.contains(subSeq)) { 
    110121                                                gain += weightMap.get(subSeq); 
     122                                        } else { 
     123                                                subSeqIter.remove(); 
    111124                                        } 
    112125                                } 
    113126                                sequenceGain[i] = gain; 
     127                                // optimization using that the gain is monotonically decreasing 
     128                                if (Math.abs(gain - prevGain) <= eps) { 
     129                                        gainEqual = true; 
     130                                        break; 
     131                                } 
     132                                i++; 
    114133                        } 
    115                         int maxIndex = ArrayTools.findMax(sequenceGain); 
    116                         if (sequenceGain[maxIndex] <= 0.0 + eps) { 
     134                        int maxIndex; 
     135                        if (gainEqual) { 
     136                                maxIndex = i; 
     137                        } else { 
     138                                maxIndex = ArrayTools.findMax(sequenceGain); 
     139                        } 
     140                        if (maxIndex < 0 || sequenceGain[maxIndex] <= 0.0 + eps) { 
    117141                                Console.traceln("No gain anymore! Desired coverage cannot be satisfied!"); 
    118142                                break; 
    119143                        } 
     144                        prevGain = sequenceGain[maxIndex]; 
    120145                        testSuite.add(allSequences.get(maxIndex)); 
    121146                        coveredSubSeqs.addAll(containedSubSeqs.get(maxIndex)); 
    122                         coverageCalculator.setSequences(testSuite); 
    123                         currentCoverage = coverageCalculator.getCoveragePossibleWeight(); 
     147                        currentCoverage += sequenceGain[maxIndex]; 
     148                        if (gainEqual) { 
     149                                allSequences.remove(maxIndex); 
     150                                containedSubSeqs.remove(maxIndex); 
     151                                gainEqual = false; 
     152                        } else { 
     153                                for (int j = sequenceGain.length - 1; j >= 0; j--) { 
     154                                        if (j == maxIndex || sequenceGain[j] <= 0.0 + eps) { 
     155                                                allSequences.remove(j); 
     156                                                containedSubSeqs.remove(j); 
     157                                        } 
     158                                } 
     159                        } 
    124160                } 
    125161 
     
    138174        @Override 
    139175        public void help() { 
    140                 Console.println("generateGreedy <modelname> <sequencesName> <minLength> <maxLength> <coverageDepth> <desiredCoverage>"); 
     176                Console.println("generateGreedy <modelname> <sequencesName> <minLength> <maxLength> <coverageDepth> <desiredCoverage> {<validEnd>}"); 
    141177        } 
    142178 
Note: See TracChangeset for help on using the changeset viewer.