1
2
3
4
5
6
7 package net.sf.bddbddb.order;
8
9 import java.util.Collection;
10 import java.util.Collections;
11 import java.util.Iterator;
12 import java.util.LinkedList;
13
14 import jwutil.math.Distributions;
15 import net.sf.bddbddb.FindBestDomainOrder;
16 import net.sf.bddbddb.InferenceRule;
17 import net.sf.bddbddb.Solver;
18 import net.sf.bddbddb.Variable;
19 import net.sf.bddbddb.XMLFactory;
20
21 import org.jdom.Element;
22
23
24 /***
25 * Information about a particular constraint.
26 *
27 * @author jwhaley
28 * @version $Id: ConstraintInfo.java 448 2005-03-07 06:58:48Z cs343 $
29 */
30 public class ConstraintInfo implements Comparable {
31
32
33
34
35
36
37
38
39
40
41
42 /***
43 * The constraint that this info is about.
44 */
45 OrderConstraint c;
46
47 /***
48 * The collection of trials that are used in the computation of the score.
49 */
50 Collection trials;
51
52 /*** * The rest of the fields are computed based on the trials. ** */
53
54 double sumCost;
55
56 double sumMinimumCost;
57
58 double sumNormalizedCost;
59
60 double sumNormalizedCostSq;
61
62 int numTrials;
63
64 /***
65 * Construct a new ConstraintInfo.
66 *
67 * @param c constraint
68 */
69 public ConstraintInfo(OrderConstraint c) {
70 this.c = c;
71 this.trials = new LinkedList();
72 this.sumCost = 0.;
73 this.sumMinimumCost = 0.;
74 this.sumNormalizedCost = 0.;
75 this.sumNormalizedCostSq = 0.;
76 this.numTrials = 0;
77 }
78
79
80
81
82 public String toString() {
83 return c + ": score " + FindBestDomainOrder.format(getMean()) + " +- " + FindBestDomainOrder.format(getConfidenceInterval(.1));
84 }
85
86 /***
87 * A measure of, when using an order with this constraint, how long
88 * the operation would take versus the best time for that operation.
89 * For example, a score of 2 would mean that on average, orders with
90 * this constraint took twice as long on an operation as the best
91 * known order for that operation.
92 *
93 * Obviously, the best possible score is 1, and lower numbers are better.
94 */
95 public double getMean() {
96 if (numTrials == 0) return 0.;
97 return sumNormalizedCost / numTrials;
98 }
99
100 /***
101 * The number of trials used in the computation of the score.
102 */
103 public int getNumberOfTrials() {
104 return numTrials;
105 }
106
107 public static double getVariance(Collection cis) {
108 double sum = 0.;
109 double sumOfSquares = 0.;
110 int n = 0;
111 for (Iterator i = cis.iterator(); i.hasNext();) {
112 ConstraintInfo ci = (ConstraintInfo) i.next();
113 sum += ci.sumNormalizedCost;
114 sumOfSquares += ci.sumNormalizedCostSq;
115 n += ci.numTrials;
116 }
117
118 double variance = (sumOfSquares * n - sum * sum) / (n * n);
119 return variance;
120 }
121
122 /***
123 * The variance of the normalized times used in the computation of the score.
124 */
125 public double getVariance() {
126
127 int n = numTrials;
128 double variance = (sumNormalizedCostSq * n -
129 sumNormalizedCost * sumNormalizedCost) / (n * n);
130 return variance;
131 }
132
133 /***
134 * The standard deviation of the normalized times used in the computation
135 * of the score.
136 */
137 public double getStdDev() {
138 return Math.sqrt(getVariance());
139 }
140
141 /***
142 * The same as the score, but each trial is weighted by the absolute
143 * time spent by the best trial of that operation. This means that
144 * operations that took longer will be weighted in this score more
145 * heavily.
146 */
147 public double getWeightedMean() {
148 if (sumMinimumCost == 0.) return 0.;
149 return sumCost / sumMinimumCost;
150 }
151
152 public double getMinimumCost() {
153 return sumMinimumCost;
154 }
155
156 /***
157 * Returns the confidence interval of the normalized times with the given
158 * significance level.
159 */
160 public double getConfidenceInterval(double sigLevel) {
161
162 int N = getNumberOfTrials();
163 if (N < 2) return Double.POSITIVE_INFINITY;
164 double s = getStdDev();
165 return Distributions.uc_stDist(sigLevel / 2, N - 1) * s / Math.sqrt(N);
166 }
167
168 public void registerTrial(TrialInfo t) {
169 registerTrials(Collections.singleton(t));
170 }
171
172 /***
173 * Register new trials with this ConstraintInfo.
174 */
175 public void registerTrials(Collection newTrials) {
176 if (newTrials.isEmpty()) return;
177 EpisodeCollection tc = ((TrialInfo) newTrials.iterator().next()).getCollection();
178 long min = tc.getMinimum().cost + 1;
179 sumMinimumCost += min;
180 for (Iterator i = newTrials.iterator(); i.hasNext();) {
181 TrialInfo t = (TrialInfo) i.next();
182 Order o = t.order;
183
184 sumCost += t.cost + 1;
185 double normalized = (double) (t.cost + 1) / (double) min;
186 sumNormalizedCost += normalized;
187 sumNormalizedCostSq += normalized * normalized;
188 trials.add(t);
189 numTrials++;
190 }
191 }
192
193 public int compareTo(Object o) {
194 return compareTo((ConstraintInfo) o);
195 }
196
197 public int compareTo(ConstraintInfo that) {
198 if (this == that) return 0;
199 int result = FindBestDomainOrder.signum(that.getWeightedMean() - this.getWeightedMean());
200 if (result == 0) {
201 result = (int) FindBestDomainOrder.signum(this.getVariance() - that.getVariance());
202 if (result == 0) {
203 result = this.c.compareTo(that.c);
204 }
205 }
206 return result;
207 }
208
209 /***
210 * Dump this constraint info to the screen.
211 */
212 public void dump() {
213 System.out.println("Constraint: " + c);
214 System.out.print(" Average=" + FindBestDomainOrder.format(getMean()) + " (weighted=" + FindBestDomainOrder.format(getWeightedMean()));
215 System.out.println(" stddev " + FindBestDomainOrder.format(getStdDev()) + " conf=+-" + FindBestDomainOrder.format(getConfidenceInterval(.1)));
216 System.out.println(" Based on " + numTrials + " trials:");
217 for (Iterator i = trials.iterator(); i.hasNext();) {
218 TrialInfo ti = (TrialInfo) i.next();
219 System.out.println(" " + ti.toString());
220 }
221 }
222
223 public Element toXMLElement(Solver solver) {
224 Element dis = new Element("constraintInfo");
225 InferenceRule ir = null;
226 if (c.isVariableConstraint()) ir = solver.getRuleThatContains((Variable) c.getFirst());
227 Element constraint = c.toXMLElement(ir);
228 dis.setAttribute("sumCost", Double.toString(sumCost));
229 dis.setAttribute("sumMinimumCost", Double.toString(sumMinimumCost));
230 dis.setAttribute("sumNormalizedCost", Double.toString(sumNormalizedCost));
231 dis.setAttribute("sumNormalizedCostSq", Double.toString(sumNormalizedCostSq));
232 dis.setAttribute("numTrials", Integer.toString(numTrials));
233 return dis;
234 }
235
236 public static ConstraintInfo fromXMLElement(Element e, XMLFactory f) {
237 OrderConstraint c = null;
238 for (Iterator i = e.getContent().iterator(); i.hasNext();) {
239 Element e2 = (Element) i.next();
240 Object o = f.fromXML(e2);
241 if (o instanceof OrderConstraint) {
242 c = (OrderConstraint) o;
243 break;
244 }
245 }
246 if (c == null) return null;
247 ConstraintInfo ci = new ConstraintInfo(c);
248 ci.sumCost = Double.parseDouble(e.getAttributeValue("sumCost", "0."));
249 ci.sumMinimumCost = Double.parseDouble(e.getAttributeValue("sumMinimumCost", "0."));
250 ci.sumNormalizedCost = Double.parseDouble(e.getAttributeValue("sumNormalizedCost", "0."));
251 ci.sumNormalizedCostSq = Double.parseDouble(e.getAttributeValue("sumNormalizedCostSq", "0."));
252 ci.numTrials = Integer.parseInt(e.getAttributeValue("numTrials", "0"));
253 return ci;
254 }
255 }