Changeset 4 for bidspace

Timestamp:

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

Author:

bart

Message:

Faster example parties

Location:

bidspace

Files:

• pom.xml (modified) (1 diff)
• src/main/java/geniusweb/bidspace/BidsWithUtility.java (modified) (1 diff)
• src/main/java/geniusweb/bidspace/Interval.java (added)
• src/main/java/geniusweb/bidspace/IssueInfo.java (added)
• src/test/java/geniusweb/bidspace/BidsWithUtilityTest.java (modified) (1 diff)
• src/test/java/geniusweb/bidspace/IntervalTest.java (added)
• src/test/resources/9issues (added)
• src/test/resources/9issues/9issues1.json (added)

bidspace/pom.xml

@@ -140 +140 @@
                                         <target>1.8</target>
                                 </configuration>
+                        </plugin>
+                        <plugin>
+                                <groupId>org.apache.maven.plugins</groupId>
+                                <artifactId>maven-source-plugin</artifactId>
+                                <executions>
+                                        <execution>
+                                                <id>attach-sources</id>
+                                                <goals>
+                                                        <goal>jar</goal>
+                                                </goals>
+                                        </execution>
+                                </executions>
                         </plugin>
 

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;
         }
 

bidspace/src/test/java/geniusweb/bidspace/BidsWithUtilityTest.java

@@ -1 +1 @@
 package geniusweb.bidspace;
 
-import static org.junit.Assert.assertEquals;
-import static org.mockito.Matchers.any;
-import static org.mockito.Mockito.mock;
-import static org.mockito.Mockito.when;
+import static org.junit.Assert.assertTrue;
 
 import java.io.IOException;
 import java.math.BigDecimal;
 import java.math.BigInteger;
+import java.math.RoundingMode;
 import java.nio.file.Files;
 import java.nio.file.Paths;
+import java.util.Arrays;
 import java.util.Collection;
-import java.util.HashMap;
-import java.util.LinkedList;
-import java.util.Map;
+import java.util.Random;
 
-import org.junit.Before;
 import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
 
 import com.fasterxml.jackson.databind.ObjectMapper;
 
 import geniusweb.issuevalue.Bid;
-import geniusweb.issuevalue.DiscreteValue;
-import geniusweb.issuevalue.DiscreteValueSet;
-import geniusweb.issuevalue.Domain;
-import geniusweb.issuevalue.NumberValue;
-import geniusweb.issuevalue.NumberValueSet;
-import geniusweb.issuevalue.ValueSet;
 import geniusweb.profile.Profile;
 import geniusweb.profile.utilityspace.LinearAdditiveUtilitySpace;
+import tudelft.utilities.immutablelist.ImmutableList;
 
+@RunWith(Parameterized.class)
 public class BidsWithUtilityTest {
-        private static final DiscreteValue I1V2 = new DiscreteValue("i1v2");
-        private static final DiscreteValue I1V1 = new DiscreteValue("i1v1");
-        private static final NumberValue I2V1 = new NumberValue("2.00");
-        private static final NumberValue I2V2 = new NumberValue("2.45");
-        private static final NumberValue I2V3 = new NumberValue("2.90");
-        private static final String DOMAINNAME = "testdomain";
-        private static final String ISSUE1 = "issue1";
-        private static final String ISSUE2 = "issue2";
-        private static final Map<String, ValueSet> issues = new HashMap<>();
+        private final static ObjectMapper jackson = new ObjectMapper();
+        private final Interval utilityGoal = new Interval(new BigDecimal("0.50"),
+                        new BigDecimal("0.51"));
+        private LinearAdditiveUtilitySpace profile;
+        private long expectedSize;
+        private int accuracy = 5;
 
-        private static ValueSet values1;
-        private static ValueSet values2;
-        private static final BigDecimal TWO = new BigDecimal("2");
-        private static final BigDecimal THREE = new BigDecimal("3");
-        private final static BigDecimal ZERO_1 = new BigDecimal("0.1"), ZERO_2 = new BigDecimal("0.2"),
-                        ZERO_3 = new BigDecimal("0.3");
+        @Parameters
+        public static Collection<Object[]> data() {
+                return Arrays.asList(new Object[][] {
+                                { "src/test/resources/jobs/jobs1.json", 11 },
+                                { "src/test/resources/7issues/7issues1.json", 260000 },
+                                { "src/test/resources/9issues/9issues1.json", 25000000 } });
+        }
 
-        private static Domain domain;
-        private final static ObjectMapper jackson = new ObjectMapper();
+        public BidsWithUtilityTest(String filename, long expectedsize)
+                        throws IOException {
+                String file = new String(Files.readAllBytes(Paths.get(filename)));
+                profile = (LinearAdditiveUtilitySpace) jackson.readValue(file,
+                                Profile.class);
+                this.expectedSize = expectedsize;
+        }
 
-        @Before
-        public void before() {
-                Collection<DiscreteValue> discretevalues1 = new LinkedList<>();
-                discretevalues1.add(I1V1);
-                discretevalues1.add(I1V2);
-                values1 = new DiscreteValueSet(discretevalues1);
-                issues.put(ISSUE1, values1);
-
-                values2 = new NumberValueSet(TWO, THREE, new BigDecimal("0.45"));
-                issues.put(ISSUE2, values2);
-
-                domain = new Domain(DOMAINNAME, issues);
+        /**
+         * Test if the values are within acceptable range from the goal.
+         */
+        @Test
+        public void test() {
+                ImmutableList<Bid> list = new BidsWithUtility(profile, accuracy)
+                                .getBids(utilityGoal);
+                Random rand = new Random();
+                // check not all but only 10000 random bids as list may be way too large
+                // to test them all. Testing 1 billion bids may take 15 minutes or so on
+                // quad core i7 @2.4GHz.....
+                // also notice that we may be checking only part of the list if
+                // the size of the list would become bigger than maxint.
+                for (int n = 0; n < 10000; n++) {
+                        Bid bid = list.get(rand.nextInt(list.size().intValue()));
+                        assertTrue(utilityGoal.contains(profile.getUtility(bid)
+                                        .setScale(accuracy - 1, RoundingMode.HALF_UP)));
+                }
+                assertTrue(
+                                list.size().compareTo(BigInteger.valueOf(expectedSize)) >= 0);
 
         }
 
         @Test
-        public void smokeTest() {
-                LinearAdditiveUtilitySpace space = mock(LinearAdditiveUtilitySpace.class);
-                when(space.getDomain()).thenReturn(domain);
-                when(space.getUtility(any(Bid.class))).thenReturn(ZERO_2);
-                new BidsWithUtility(space, new BigDecimal("0.1"), new BigDecimal("0.3"));
+        public void testMaxUtil() {
+                BidsWithUtility bidswithutil = new BidsWithUtility(profile);
+                // notice, this is the *rounded* max util
+                BigDecimal maxutil = bidswithutil.getRange().getMax();
+                Interval goal = new Interval(
+                                maxutil.subtract(new BigDecimal("0.00001")), maxutil);
+
+                ImmutableList<Bid> bidsnearmax = bidswithutil.getBids(goal);
+                assertTrue(bidsnearmax.size() != BigInteger.ZERO);
+
+                BigDecimal foundmax = BigDecimal.ZERO;
+                for (Bid bid : bidsnearmax) {
+                        BigDecimal util = profile.getUtility(bid);
+                        if (util.compareTo(foundmax) > 0) {
+                                foundmax = util;
+                        }
+                }
+                // found maximum may be slightly lower or higher because we rounded
+                // all weighted utilities.
+                assertTrue(Math
+                                .abs(foundmax.doubleValue() - maxutil.doubleValue()) < 0.0001);
         }
 
         @Test
-        public void testSelection() {
-                LinearAdditiveUtilitySpace space = mock(LinearAdditiveUtilitySpace.class);
+        public void benchmark() {
+                System.out.println("\nBenchmarking " + profile.getName());
+                BigInteger domainsize = new AllBidsList(profile.getDomain()).size();
 
-                when(space.getDomain()).thenReturn(domain);
-                when(space.getUtility(any(Bid.class))).thenReturn(ZERO_2);
-                BidsWithUtility selected = new BidsWithUtility(space, new BigDecimal("0.1"), new BigDecimal("0.3"));
-                assertEquals(new BigInteger("6"), selected.size());
-        }
-
-        @Test
-        public void testRealSpace() throws IOException {
-                String file1 = new String(Files.readAllBytes(Paths.get("src/test/resources/jobs/jobs1.json")));
-                LinearAdditiveUtilitySpace profile = (LinearAdditiveUtilitySpace) jackson.readValue(file1, Profile.class);
-                BidsWithUtility selected = new BidsWithUtility(profile, ZERO_1, ZERO_3);
-
-                assertEquals(new BigInteger("56"), selected.size());
-                for (Bid bid : selected) {
-                        assertEquals(1, profile.getUtility(bid).compareTo(ZERO_1));
-                        assertEquals(-1, profile.getUtility(bid).compareTo(ZERO_3));
-                }
+                long start = System.currentTimeMillis();
+                BidsWithUtility body = new BidsWithUtility(profile, accuracy);
+                ImmutableList<Bid> list = body.getBids(utilityGoal);
+                long end = System.currentTimeMillis();
+                System.out.println("run time: " + (end - start) / 1000. + "s");
+                System.out.println("Total size of bidspace:" + domainsize);
+                System.out.println("Result size: " + list.size());
         }