Changeset 4 for bidspace/src/main

Timestamp:

09/18/19 10:00:22 (5 years ago)

Author:

bart

Message:

Faster example parties

Location:

bidspace/src/main/java/geniusweb/bidspace

Files:

• BidsWithUtility.java (modified) (1 diff)
• Interval.java (added)
• IssueInfo.java (added)

bidspace/src/main/java/geniusweb/bidspace/BidsWithUtility.java

@@ -3 +3 @@
 import java.math.BigDecimal;
 import java.math.BigInteger;
-import java.util.ArrayList;
-import java.util.LinkedList;
+import java.util.Collections;
+import java.util.HashMap;
 import java.util.List;
+import java.util.Map;
+import java.util.stream.Collectors;
 
 import geniusweb.issuevalue.Bid;
+import geniusweb.issuevalue.Domain;
+import geniusweb.issuevalue.Value;
 import geniusweb.profile.utilityspace.LinearAdditiveUtilitySpace;
 import tudelft.utilities.immutablelist.AbstractImmutableList;
+import tudelft.utilities.immutablelist.FixedList;
+import tudelft.utilities.immutablelist.ImmutableList;
+import tudelft.utilities.immutablelist.JoinedList;
+import tudelft.utilities.immutablelist.MapList;
+import tudelft.utilities.immutablelist.Tuple;
 
 /**
- * Object containing a subset of all bids, that have utility within given range.
+ * Tool class containing functions dealing with utilities of all bids in a given
+ * {@link LinearAdditiveUtilitySpace}. This class caches previously computed
+ * values to accelerate the calls and subsequent calls. Re-use the object to
+ * keep/reuse the cache.
  */
-public class BidsWithUtility extends AbstractImmutableList<Bid> {
-
-        private final List<Bid> collectedbids;
-
-        /**
-         * Create Bids with utility within given bounds.
-         * 
-         * @param space the {@link LinearAdditiveUtilitySpace} to search
-         * @param min   the minimum required utility
-         * @param max   the maximum required utility
-         */
-        public BidsWithUtility(LinearAdditiveUtilitySpace space, BigDecimal min, BigDecimal max) {
-                this.collectedbids = new ArrayList<Bid>(getBids(space, min, max));
-        }
-
-        /**
-         * Brute force hack for this time. Maybe we can construct this in a lazy way.
-         * 
-         * @param space
-         * @param min
-         * @param max
-         * @return
-         */
-        private List<Bid> getBids(LinearAdditiveUtilitySpace space, BigDecimal min, BigDecimal max) {
-                List<Bid> goodbids = new LinkedList<Bid>();
-                for (Bid bid : new AllBidsList(space.getDomain())) {
-                        BigDecimal util = space.getUtility(bid);
-                        if (util.compareTo(min) >= 0 && util.compareTo(max) <= 0) {
-                                goodbids.add(bid);
-                        }
-                }
-                return goodbids;
+public class BidsWithUtility {
+
+        private final List<IssueInfo> issueInfo;
+        private final int precision; // #digits used for Intervals
+
+        /**
+         * cache. Key = call arguments for {@link #get(int, Interval)}. Value=return
+         * value of that call.
+         */
+        private final Map<Tuple<Integer, Interval>, ImmutableList<Bid>> cache = new HashMap<>();
+
+        /**
+         * Default constructor, uses default precision 6. This value seems practical
+         * for the common range of issues, utilities and weights. See
+         * {@link #BidsWithUtil(LinearAdditiveUtilitySpace, int)} for more details
+         * on the precision.
+         * 
+         * @param space the {@link LinearAdditiveUtilitySpace} to analyze
+         */
+        public BidsWithUtility(LinearAdditiveUtilitySpace space) {
+                this(space, 6);
+        }
+
+        /**
+         * 
+         * @param space     the {@link LinearAdditiveUtilitySpace} to analyze
+         * @param precision the number of digits to use for computations. This value
+         *                  should match the max number of (digits used in the
+         *                  weight of an issue + number of digits used in the issue
+         *                  utility). Usually you also look at the step size, and
+         *                  the range of interest. For instance if your utility
+         *                  function has values 1/3 and 2/3, then these have an
+         *                  'infinite' number of relevant digits. But if we want to
+         *                  search bids between utility 0.1 and 0.2, then computing
+         *                  in 2 digits might already be sufficient. This algorithm
+         *                  has memory and space complexity O( |nissues|
+         *                  10^precision ). For spaces up to 7 issues, 7 digits
+         *                  should be feasible; for 9 issues, 6 digits may be the
+         *                  maximum.
+         */
+        public BidsWithUtility(LinearAdditiveUtilitySpace space, int precision) {
+                this(getInfo(space, precision), precision);
+        }
+
+        /**
+         * 
+         * @param issuesInfo List of the relevant issues (in order of relevance) and
+         *                   all info of each issue.
+         * @param precision  the number of digits used in Intervals.
+         */
+        public BidsWithUtility(List<IssueInfo> issuesInfo, int precision) {
+                if (issuesInfo == null || issuesInfo.isEmpty()) {
+                        throw new IllegalArgumentException(
+                                        "sortedissues list must contain at least 1 element");
+                }
+
+                this.issueInfo = issuesInfo;
+                this.precision = precision;
+
+        }
+
+        /**
+         * @return the utility {@link Interval} of this space: minimum and maximum
+         *         achievable utility.
+         */
+        public Interval getRange() {
+                return getRange(issueInfo.size() - 1);
+        }
+
+        /**
+         * 
+         * @param range the minimum and maximum utility required of the bids. to be
+         *              included (both ends inclusive).
+         * @return a list with bids that have utility inside range. possibly empty.
+         *         With decreasing precision, more bids may drop out due to rounding
+         *         errors.
+         */
+        public ImmutableList<Bid> getBids(Interval range) {
+                return get(issueInfo.size() - 1, range.round(precision));
+        }
+
+        public List<IssueInfo> getInfo() {
+                return Collections.unmodifiableList(issueInfo);
+        }
+
+        /**
+         * Create partial BidsWithUtil list considering only issues 0..n, with
+         * utilities in given range.
+         * 
+         * @param n    the number of {@link #issueRanges} to consider, we consider
+         *             0..n here. The recursion decreases n until n=0
+         * @param goal the minimum and maximum utility required of the bids. to be
+         *             included (both ends inclusive)
+         * @return BidsWithUtil list, possibly empty.
+         */
+        protected ImmutableList<Bid> get(int n, Interval goal) {
+                if (goal == null) {
+                        throw new NullPointerException("Interval=null");
+                }
+
+                // clamp goal into what is reachable. Avoid caching empty
+                goal = goal.intersect(getRange(n));
+                if (goal.isEmpty()) {
+                        return new FixedList<>();
+                }
+
+                Tuple<Integer, Interval> cachetuple = new Tuple<>(n, goal);
+                ImmutableList<Bid> cached = cache.get(cachetuple);
+                if (cached != null) {
+                        // hits++;
+                        return cached;
+                }
+
+                ImmutableList<Bid> result = checkedGet(n, goal);
+                cache.put(cachetuple, result);
+                return result;
+        }
+
+        private static List<IssueInfo> getInfo(LinearAdditiveUtilitySpace space2,
+                        int precision) {
+                Domain dom = space2.getDomain();
+                return space2.getDomain().getIssues().stream()
+                                .map(issue -> new IssueInfo(issue, dom.getValues(issue),
+                                                space2.getUtilities().get(issue),
+                                                space2.getWeight(issue), precision))
+                                .collect(Collectors.toList());
+        }
+
+        private ImmutableList<Bid> checkedGet(int n, Interval goal) {
+                IssueInfo info = issueInfo.get(n);
+                // issue is the first issuesWithRange.
+                String issue = issueInfo.get(n).getName();
+
+                if (n == 0)
+                        return new OneIssueSubset(info, goal);
+
+                // make new list, joining all sub-lists
+                ImmutableList<Bid> fulllist = new FixedList<>();
+                for (Value val : info.getValues()) {
+                        BigDecimal weightedutil = info.getWeightedUtil(val);
+                        Interval subgoal = goal.subtract(weightedutil);
+                        // recurse: get list of bids for the subspace
+                        ImmutableList<Bid> partialbids = get(n - 1, subgoal);
+
+                        Bid bid = new Bid(issue, val);
+                        ImmutableList<Bid> fullbids = new MapList<Bid, Bid>(
+                                        pbid -> pbid.merge(bid), partialbids);
+                        if (!fullbids.size().equals(BigInteger.ZERO))
+                                fulllist = new JoinedList<Bid>(fullbids, fulllist);
+                }
+                return fulllist;
+        }
+
+        /**
+         * @param n the maximum issuevalue utility to include. Use n=index of last
+         *          issue s= (#issues in the domain - 1) for the full range of this
+         *          domain.
+         * @return Interval (min, max) of the total weighted utility Interval of
+         *         issues 0..n. All weighted utilities have been rounded to the set
+         *         {@link #precision}
+         */
+        private Interval getRange(int n) {
+                Interval value = Interval.ZERO;
+                for (int i = 0; i <= n; i++) {
+                        value = value.add(issueInfo.get(i).getInterval());
+                }
+                return value;
+        }
+
+}
+
+/**
+ * List of all one-issue bids that have utility inside given interval.
+ */
+class OneIssueSubset extends AbstractImmutableList<Bid> {
+        private final IssueInfo info;
+        private final Interval interval;
+        private BigInteger size;
+
+        /**
+         * 
+         * @param info     the {@link IssueInfo}
+         * @param interval a utility interval (weighted)
+         */
+        OneIssueSubset(IssueInfo info, Interval interval) {
+                this.info = info;
+                this.interval = interval;
+                this.size = BigInteger.valueOf(info.subsetSize(interval));
         }
 
         @Override
         public Bid get(BigInteger index) {
-                return collectedbids.get(index.intValue());
+                return new Bid(info.getName(),
+                                info.subset(interval).get(index.intValue()));
         }
 
         @Override
         public BigInteger size() {
-                return BigInteger.valueOf(collectedbids.size());
+                return size;
         }