source: java2python/geniuswebtranslator/geniuswebsrc/geniusweb/bidspace/BidsWithUtility.java@ 889

Last change on this file since 889 was 854, checked in by wouter, 5 months ago

#264 more fixes
File size: 9.7 KB
Line 
1package geniusweb.bidspace;
2
3import java.math.BigDecimal;
4import java.math.BigInteger;
5import java.util.Collections;
6import java.util.HashMap;
7import java.util.List;
8import java.util.Map;
9import java.util.function.Function;
10import java.util.stream.Collectors;
11
12import org.eclipse.jdt.annotation.NonNull;
13
14import geniusweb.issuevalue.Bid;
15import geniusweb.issuevalue.Domain;
16import geniusweb.issuevalue.Value;
17import geniusweb.profile.utilityspace.LinearAdditive;
18import tudelft.utilities.immutablelist.AbstractImmutableList;
19import tudelft.utilities.immutablelist.FixedList;
20import tudelft.utilities.immutablelist.ImmutableList;
21import tudelft.utilities.immutablelist.JoinedList;
22import tudelft.utilities.immutablelist.MapList;
23import tudelft.utilities.immutablelist.Tuple;
24
25/**
26 * Tool class containing functions dealing with utilities of all bids in a given
27 * {@link LinearAdditive}. This class caches previously computed values to
28 * accelerate the calls and subsequent calls. Re-use the object to keep/reuse
29 * the cache.
30 * <h2>Rounding</h2> Internally, utilities of bids are rounded to the given
31 * precision. This may cause inclusion/exclusion of some bids in the results.
32 * See {@link #BidsWithUtility(LinearAdditive, int)} for more details
33 */
34public class BidsWithUtility {
35
36 private final @NonNull List<@NonNull IssueInfo> issueInfo;
37 private final int precision; // #digits used for Intervals
38
39 /**
40 * cache. Key = call arguments for {@link #get(int, Interval)}. Value=return
41 * value of that call.
42 */
43 private final @NonNull Map<@NonNull Tuple<@NonNull Integer, @NonNull Interval>, @NonNull ImmutableList<@NonNull Bid>> cache = new HashMap<>();
44 private final @NonNull ImmutableList<@NonNull Bid> emptylist = new FixedList<>();
45
46 /**
47 * Default constructor, uses default precision 6. This value seems practical
48 * for the common range of issues, utilities and weights. See
49 * {@link #BidsWithUtility(LinearAdditive, int)} for more details on the
50 * precision.
51 *
52 * @param space the {@link LinearAdditive} to analyze
53 */
54 public BidsWithUtility(@NonNull LinearAdditive space) {
55 this(space, 6);
56 }
57
58 /**
59 *
60 * @param space the {@link LinearAdditive} to analyze
61 * @param precision the number of digits to use for computations. In
62 * practice, 6 seems a good default value.
63 * <p>
64 * All utilities * weight are rounded to this number of
65 * digits. This value should match the max number of
66 * (digits used in the weight of an issue + number of
67 * digits used in the issue utility). To determine the
68 * optimal value, one may consider the step size of the
69 * issues, and the range of interest. For instance if the
70 * utility function has values 1/3 and 2/3, then these have
71 * an 'infinite' number of relevant digits. But if the goal
72 * is to search bids between utility 0.1 and 0.2, then
73 * computing in 2 digits might already be sufficient.
74 * <p>
75 * This algorithm has memory and space complexity O(
76 * |nissues| 10^precision ). For spaces up to 7 issues, 7
77 * digits should be feasible; for 9 issues, 6 digits may be
78 * the maximum.
79 */
80 public BidsWithUtility(@NonNull LinearAdditive space, int precision) {
81 this(getInfo(space, precision), precision);
82 }
83
84 /**
85 *
86 * @param issuesInfo List of the relevant issues (in order of relevance) and
87 * all info of each issue. Must not be empty.
88 * @param precision the number of digits used in Intervals.
89 */
90 public BidsWithUtility(@NonNull List<@NonNull IssueInfo> issuesInfo,
91 int precision) {
92 if (issuesInfo == null || issuesInfo.isEmpty()) {
93 throw new IllegalArgumentException(
94 "sortedissues list must contain at least 1 element");
95 }
96
97 this.issueInfo = issuesInfo;
98 this.precision = precision;
99
100 }
101
102 @NonNull
103 /**
104 * @return the (rounded) utility {@link Interval} of this space: minimum and
105 * maximum achievable utility.
106 */
107 public Interval getRange() {
108 return getRange(issueInfo.size() - 1);
109 }
110
111 @NonNull
112 /**
113 *
114 * @param range the minimum and maximum utility required of the bids. to be
115 * included (both ends inclusive).
116 * @return a list with bids that have a (rounded) utility inside range.
117 * possibly empty.
118 */
119 public ImmutableList<@NonNull Bid> getBids(@NonNull Interval range) {
120 return get(issueInfo.size() - 1, range.round(precision));
121 }
122
123 public @NonNull List<@NonNull IssueInfo> getInfo() {
124 return Collections.unmodifiableList(issueInfo);
125 }
126
127 @NonNull
128 /**
129 *
130 * @param isMax the extreme bid required
131 * @return the extreme bid, either the minimum if isMax=false or maximum if
132 * isMax=true
133 */
134 public Bid getExtremeBid(boolean isMax) {
135 final @NonNull Map<@NonNull String, @NonNull Value> map = new HashMap<>();
136 for (final @NonNull IssueInfo info : issueInfo) {
137 map.put(info.getName(), info.getExtreme(isMax));
138 }
139 return new Bid(map);
140 }
141
142 @SuppressWarnings("unused")
143 @NonNull
144 /**
145 * Create partial BidsWithUtil list considering only issues 0..n, with
146 * utilities in given range.
147 * <h2>Memory use</h2> Memory use of the return value can be large, if large
148 * domains are given and the requested interval contains large numbers of
149 * bids. To give some idea, here are some typical memory uses:
150 * <table border="1">
151 * <tr>
152 * <td>domain</td>
153 * <td>mem use (MB) of returned object</td>
154 * <td>nr. of selected bids</td>
155 * </tr>
156 * <tr>
157 * <td>jobs1</td>
158 * <td>0.028</td>
159 * <td>23</td>
160 * </tr>
161 * <tr>
162 * <td>7issues1</td>
163 * <td>34</td>
164 * <td>346327</td>
165 * </tr>
166 * <tr>
167 * <td>9issues1</td>
168 * <td>98</td>
169 * <td>37160666</td>
170 * </tr>
171 * </table>
172 *
173 * @param n the number of issueRanges to consider, we consider 0..n here.
174 * The recursion decreases n until n=0
175 * @param goal the minimum and maximum utility required of the bids. to be
176 * included (both ends inclusive)
177 * @return BidsWithUtil list, possibly empty.
178 */
179 protected ImmutableList<@NonNull Bid> get(int n, @NonNull Interval goal) {
180 if (goal == null) {
181 throw new NullPointerException("Interval=null");
182 }
183
184 // clamp goal into what is reachable. Avoid caching empty
185 goal = goal.intersect(getRange(n));
186 if (goal.isEmpty()) {
187 return new FixedList<>();
188 }
189
190 final @NonNull Tuple<@NonNull Integer, @NonNull Interval> cachetuple = new Tuple<>(
191 n, goal);
192 final ImmutableList<@NonNull Bid> cached = cache.get(cachetuple);
193 if (cached != null) {
194 // hits++;
195 return cached;
196 }
197
198 final @NonNull ImmutableList<@NonNull Bid> result = checkedGet(n, goal);
199 cache.put(cachetuple, result);
200 return result;
201 }
202
203 private static @NonNull List<@NonNull IssueInfo> getInfo(
204 @NonNull LinearAdditive space2, int precision) {
205 final @NonNull Domain dom = space2.getDomain();
206 /*#PY
207 * return [ IssueInfo(issue, dom.getValues(issue),
208 * space2.getUtilities().get(issue),
209 * space2.getWeight(issue), precision))
210 * for issue in space2.getDomain().getIssues() ]
211 */
212 return space2.getDomain().getIssuesValues().keySet().stream()
213 .map(issue -> new IssueInfo(issue, dom.getValues(issue),
214 space2.getUtilities().get(issue),
215 space2.getWeight(issue), precision))
216 .collect(Collectors.toList());
217 }
218
219 private @NonNull ImmutableList<@NonNull Bid> checkedGet(int n,
220 final @NonNull Interval goal) {
221 final @NonNull IssueInfo info = issueInfo.get(n);
222 // issue is the first issuesWithRange.
223 final @NonNull String issue = info.getName();
224
225 if (n == 0)
226 return new OneIssueSubset(info, goal);
227
228 // make new list, joining all sub-lists
229 @NonNull
230 ImmutableList<@NonNull Bid> fulllist = emptylist;
231 for (@NonNull
232 Value val : info.getValues()) {
233 BigDecimal weightedutil = info.getWeightedUtil(val);
234 @NonNull
235 Interval subgoal = goal.subtract(weightedutil);
236 // recurse: get list of bids for the subspace
237 @NonNull
238 ImmutableList<@NonNull Bid> partialbids = get(n - 1, subgoal);
239
240 ImmutableList<@NonNull Bid> fullbids = new MapList<@NonNull Bid, @NonNull Bid>(
241 (Function<@NonNull Bid, @NonNull Bid>) pbid -> pbid
242 .merge(new Bid(issue, val)),
243 partialbids);
244 if (!fullbids.size().equals(BigInteger.ZERO))
245 fulllist = new JoinedList<@NonNull Bid>(fullbids, fulllist);
246 }
247 return fulllist;
248 }
249
250 @NonNull
251 /**
252 * @param n the maximum issuevalue utility to include. Use n=index of last
253 * issue s= (#issues in the domain - 1) for the full range of this
254 * domain.
255 * @return Interval (min, max) of the total weighted utility Interval of
256 * issues 0..n. All weighted utilities have been rounded to the set
257 * {@link #precision}
258 */
259 private Interval getRange(int n) {
260 @NonNull
261 Interval value = Interval.ZERO;
262 for (int i = 0; i <= n; i = i + 1) {
263 value = value.add(issueInfo.get(i).getInterval());
264 }
265 return value;
266 }
267
268}
269
270/**
271 * List of all one-issue bids that have utility inside given interval.
272 */
273class OneIssueSubset extends AbstractImmutableList<@NonNull Bid> {
274 private final @NonNull IssueInfo info;
275 private final @NonNull Interval interval;
276 private @NonNull BigInteger size;
277
278 /**
279 *
280 * @param info the {@link IssueInfo}
281 * @param interval a utility interval (weighted)
282 */
283 OneIssueSubset(@NonNull IssueInfo info, @NonNull Interval interval) {
284 this.info = info;
285 this.interval = interval;
286 this.size = BigInteger.valueOf(info.subsetSize(interval));
287 }
288
289 @Override
290 public @NonNull Bid get(@NonNull BigInteger index) {
291 return new Bid(info.getName(),
292 info.subset(interval).get(index.intValue()));
293 }
294
295 @Override
296 public @NonNull BigInteger size() {
297 return size;
298 }
299
300}
Note: See TracBrowser for help on using the repository browser.