Changeset 395

Timestamp:

03/08/12 09:38:19 (12 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:

• trunk/EventBenchConsole/src/de/ugoe/cs/eventbench/commands/CMDgenerateGreedy.java (modified) (7 diffs)

trunk/EventBenchConsole/src/de/ugoe/cs/eventbench/commands/CMDgenerateGreedy.java

@@ -2 +2 @@
 
 import java.security.InvalidParameterException;
-import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Iterator;
 import java.util.LinkedHashSet;
 import java.util.LinkedList;
@@ -10 +11 @@
 
 import de.ugoe.cs.eventbench.CommandHelpers;
-import de.ugoe.cs.eventbench.coverage.CoverageCalculatorProcess;
 import de.ugoe.cs.eventbench.coverage.SequenceTools;
 import de.ugoe.cs.eventbench.data.Event;
@@ -50 +50 @@
                 int coverageDepth;
                 float desiredCoverage;
+                boolean validEnd = true;
                 try {
                         modelname = (String) parameters.get(0);
@@ -57 +58 @@
                         coverageDepth = Integer.parseInt((String) parameters.get(4));
                         desiredCoverage = Float.parseFloat((String) parameters.get(5));
+                        if (parameters.size() >= 7) {
+                                validEnd = Boolean.parseBoolean((String) parameters.get(6));
+                        }
                 } catch (Exception e) {
                         throw new InvalidParameterException();
@@ -74 +78 @@
 
                 // set up everything
-                List<List<? extends Event<?>>> allSequences = new ArrayList<List<? extends Event<?>>>();
+                List<List<? extends Event<?>>> allSequences = new LinkedList<List<? extends Event<?>>>();
                 for (int length = minLength; length <= maxLength; length++) {
-                        allSequences.addAll(model.generateValidSequences(length + 2));
+                        if (validEnd) {
+                                allSequences.addAll(model.generateValidSequences(length + 2));
+                        } else {
+                                allSequences.addAll(model.generateSequences(length + 1, true));
+                        }
                 }
                 Console.traceln("" + allSequences.size() + " possible");
 
-                Set<List<? extends Event<?>>> allSubSeqs = SequenceTools
-                                .containedSubSequences(allSequences, coverageDepth);
+                Collection<List<? extends Event<?>>> allSubSeqs = model
+                                .generateSequences(coverageDepth);
                 Map<List<? extends Event<?>>, Double> weightMap = SequenceTools
                                 .generateWeights(model, allSubSeqs);
                 Set<List<? extends Event<?>>> coveredSubSeqs = new LinkedHashSet<List<? extends Event<?>>>();
 
-                List<Set<List<? extends Event<?>>>> containedSubSeqs = new ArrayList<Set<List<? extends Event<?>>>>(
-                                allSequences.size());
+                List<Set<List<? extends Event<?>>>> containedSubSeqs = new LinkedList<Set<List<? extends Event<?>>>>();
                 for (List<? extends Event<?>> sequence : allSequences) {
                         List<List<? extends Event<?>>> wrapper = new LinkedList<List<? extends Event<?>>>();
@@ -96 +103 @@
                 }
 
-                Double[] sequenceGain = new Double[allSequences.size()];
                 List<List<? extends Event<?>>> testSuite = new LinkedList<List<? extends Event<?>>>();
-                CoverageCalculatorProcess coverageCalculator = new CoverageCalculatorProcess(
-                                model, testSuite, coverageDepth);
                 double currentCoverage = 0.0d;
 
                 // Build test suite
+                double prevGain = 1.0d;
+                boolean gainEqual = false;
                 while (currentCoverage < desiredCoverage) {
-                        for (int i = 0; i < allSequences.size(); i++) {
+                        Double[] sequenceGain = new Double[allSequences.size()];
+                        int i = 0;
+                        for (Set<List<? extends Event<?>>> containedSubSeq : containedSubSeqs) {
                                 double gain = 0.0d;
-                                for (List<? extends Event<?>> subSeq : containedSubSeqs.get(i)) {
+                                Iterator<List<? extends Event<?>>> subSeqIter = containedSubSeq
+                                                .iterator();
+                                while (subSeqIter.hasNext()) {
+                                        List<? extends Event<?>> subSeq = subSeqIter.next();
                                         if (!coveredSubSeqs.contains(subSeq)) {
                                                 gain += weightMap.get(subSeq);
+                                        } else {
+                                                subSeqIter.remove();
                                         }
                                 }
                                 sequenceGain[i] = gain;
+                                // optimization using that the gain is monotonically decreasing
+                                if (Math.abs(gain - prevGain) <= eps) {
+                                        gainEqual = true;
+                                        break;
+                                }
+                                i++;
                         }
-                        int maxIndex = ArrayTools.findMax(sequenceGain);
-                        if (sequenceGain[maxIndex] <= 0.0 + eps) {
+                        int maxIndex;
+                        if (gainEqual) {
+                                maxIndex = i;
+                        } else {
+                                maxIndex = ArrayTools.findMax(sequenceGain);
+                        }
+                        if (maxIndex < 0 || sequenceGain[maxIndex] <= 0.0 + eps) {
                                 Console.traceln("No gain anymore! Desired coverage cannot be satisfied!");
                                 break;
                         }
+                        prevGain = sequenceGain[maxIndex];
                         testSuite.add(allSequences.get(maxIndex));
                         coveredSubSeqs.addAll(containedSubSeqs.get(maxIndex));
-                        coverageCalculator.setSequences(testSuite);
-                        currentCoverage = coverageCalculator.getCoveragePossibleWeight();
+                        currentCoverage += sequenceGain[maxIndex];
+                        if (gainEqual) {
+                                allSequences.remove(maxIndex);
+                                containedSubSeqs.remove(maxIndex);
+                                gainEqual = false;
+                        } else {
+                                for (int j = sequenceGain.length - 1; j >= 0; j--) {
+                                        if (j == maxIndex || sequenceGain[j] <= 0.0 + eps) {
+                                                allSequences.remove(j);
+                                                containedSubSeqs.remove(j);
+                                        }
+                                }
+                        }
                 }
 
@@ -138 +174 @@
         @Override
         public void help() {
-                Console.println("generateGreedy <modelname> <sequencesName> <minLength> <maxLength> <coverageDepth> <desiredCoverage>");
+                Console.println("generateGreedy <modelname> <sequencesName> <minLength> <maxLength> <coverageDepth> <desiredCoverage> {<validEnd>}");
         }