changeset 1208:eedfa64aa9da

7901401: Optimize Multisets.countHighest: windowed collections Contributed-by: Vladimir Sitnikov <sitnikov.vladimir@gmail.com>
author shade
date Thu, 23 Apr 2015 01:56:42 +0300
parents 549a04ac4526
children 172094a4b2c4
files jmh-core/src/main/java/org/openjdk/jmh/util/BoundedPriorityQueue.java jmh-core/src/main/java/org/openjdk/jmh/util/Multisets.java jmh-core/src/test/java/org/openjdk/jmh/util/BoundedPriorityQueueTest.java jmh-core/src/test/java/org/openjdk/jmh/util/MultisetsTest.java
diffstat 4 files changed, 266 insertions(+), 27 deletions(-) [+]
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/jmh-core/src/main/java/org/openjdk/jmh/util/BoundedPriorityQueue.java	Thu Apr 23 01:56:42 2015 +0300
@@ -0,0 +1,120 @@
+/*
+ * Copyright (c) 2014, 2015, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.  Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package org.openjdk.jmh.util;
+
+import java.io.Serializable;
+import java.util.*;
+
+/**
+ * Bounded variant of {@link PriorityQueue}.
+ * Note: elements are returned in reverse order.
+ * For instance, if "top N smallest elements" are required, use {@code new BoundedPriorityQueue(N)},
+ * and the elements would be returned in largest to smallest order.
+ *
+ * @param <E> type of the element
+ */
+public class BoundedPriorityQueue<E> extends AbstractQueue<E> implements Serializable {
+    private static final long serialVersionUID = 7159618773497127413L;
+
+    private final int maxSize;
+    private final Comparator<? super E> comparator;
+    private final Queue<E> queue;
+
+    /**
+     * Creates a bounded priority queue with the specified maximum size and default ordering.
+     * At most {@code maxSize} smallest elements would be kept in the queue.
+     *
+     * @param maxSize maximum size of the queue
+     */
+    public BoundedPriorityQueue(int maxSize) {
+        this(maxSize, null);
+    }
+
+    /**
+     * Creates a bounded priority queue with the specified maximum size.
+     * At most {@code maxSize} smallest elements would be kept in the queue.
+     *
+     * @param maxSize    maximum size of the queue
+     * @param comparator comparator that orders the elements
+     */
+    public BoundedPriorityQueue(int maxSize, Comparator<? super E> comparator) {
+        this.maxSize = maxSize;
+        this.comparator = reverse(comparator);
+        this.queue = new PriorityQueue<E>(10, this.comparator);
+    }
+
+    /**
+     * Internal queue should be in fact in reverse order.
+     * By default, the queue aims for "top N smallest elements".
+     * So peek() should return the biggest element, so it can be removed when adding smaller element
+     *
+     * @param comparator comparator that designates ordering of the entries or {@code null} for default ordering
+     * @param <E>        type of the element
+     * @return reverse comparator
+     */
+    private static <E> Comparator<? super E> reverse(Comparator<? super E> comparator) {
+        if (comparator == null) {
+            return Collections.reverseOrder();
+        }
+        return Collections.reverseOrder(comparator);
+    }
+
+    @Override
+    public boolean add(E e) {
+        return offer(e);
+    }
+
+    @Override
+    public boolean offer(E e) {
+        if (queue.size() >= maxSize) {
+            E head = peek();
+            if (comparator.compare(e, head) < 1) {
+                return false;
+            }
+            poll();
+        }
+        return queue.offer(e);
+    }
+
+    @Override
+    public E poll() {
+        return queue.poll();
+    }
+
+    @Override
+    public E peek() {
+        return queue.peek();
+    }
+
+    @Override
+    public Iterator<E> iterator() {
+        return queue.iterator();
+    }
+
+    @Override
+    public int size() {
+        return queue.size();
+    }
+}
--- a/jmh-core/src/main/java/org/openjdk/jmh/util/Multisets.java	Thu Apr 23 01:12:17 2015 +0300
+++ b/jmh-core/src/main/java/org/openjdk/jmh/util/Multisets.java	Thu Apr 23 01:56:42 2015 +0300
@@ -24,32 +24,28 @@
  */
 package org.openjdk.jmh.util;
 
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.Collections;
-import java.util.Comparator;
-import java.util.List;
-import java.util.PriorityQueue;
+import java.util.*;
 
 public class Multisets {
 
-    public static <T> Collection<T> countHighest(Multiset<T> set, int top) {
-        // crude and inefficient
-        PriorityQueue<Pair<T, Long>> q = new PriorityQueue<Pair<T, Long>>(10, new Comparator<Pair<T, Long>>() {
+    public static <T> List<T> countHighest(Multiset<T> set, int top) {
+        Queue<Map.Entry<T, Long>> q = new BoundedPriorityQueue<Map.Entry<T, Long>>(top, new Comparator<Map.Entry<T, Long>>() {
             @Override
-            public int compare(Pair<T, Long> o1, Pair<T, Long> o2) {
-                return o2.k2.compareTo(o1.k2);
+            public int compare(Map.Entry<T, Long> o1, Map.Entry<T, Long> o2) {
+                return o2.getValue().compareTo(o1.getValue());
             }
         });
 
-        for (T key : set.keys()) {
-            q.add(new Pair<T, Long>(key, set.count(key)));
+        q.addAll(set.entrySet());
+
+        List<T> result = new ArrayList<T>(q.size());
+
+        for (Map.Entry<T, Long> pair : q) {
+            result.add(pair.getKey());
         }
 
-        List<T> result = new ArrayList<T>();
-        for (int t = 0; (t < top && !q.isEmpty()); t++) {
-            result.add(q.poll().k1);
-        }
+        // BoundedPriorityQueue returns "smallest to largest", so we reverse the result
+        Collections.reverse(result);
 
         return result;
     }
@@ -67,14 +63,4 @@
         return sorted;
     }
 
-    private static class Pair<K1, K2> {
-        public final K1 k1;
-        public final K2 k2;
-
-        private Pair(K1 k1, K2 k2) {
-            this.k1 = k1;
-            this.k2 = k2;
-        }
-    }
-
 }
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/jmh-core/src/test/java/org/openjdk/jmh/util/BoundedPriorityQueueTest.java	Thu Apr 23 01:56:42 2015 +0300
@@ -0,0 +1,68 @@
+/*
+ * Copyright (c) 2014, 2015, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.  Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package org.openjdk.jmh.util;
+
+import junit.framework.Assert;
+import org.junit.Test;
+
+import java.util.Collections;
+import java.util.Queue;
+
+public class BoundedPriorityQueueTest {
+    @Test
+    public void top3Smallest() {
+        Queue<Integer> queue = new BoundedPriorityQueue<Integer>(3);
+        queue.add(50);
+        queue.add(40);
+        queue.add(10);
+        queue.add(20);
+        queue.add(30);
+        queue.add(30);
+        queue.add(80);
+
+        Assert.assertEquals(3, queue.size());
+        Assert.assertEquals((Integer) 30, queue.poll());
+        Assert.assertEquals((Integer) 20, queue.poll());
+        Assert.assertEquals((Integer) 10, queue.poll());
+    }
+
+    @Test
+    public void top3Largest() {
+        Queue<Integer> queue = new BoundedPriorityQueue<Integer>(3, Collections.reverseOrder());
+        queue.add(50);
+        queue.add(40);
+        queue.add(10);
+        queue.add(20);
+        queue.add(30);
+        queue.add(30);
+        queue.add(80);
+
+        Assert.assertEquals(3, queue.size());
+        Assert.assertEquals((Integer) 40, queue.poll());
+        Assert.assertEquals((Integer) 50, queue.poll());
+        Assert.assertEquals((Integer) 80, queue.poll());
+    }
+
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/jmh-core/src/test/java/org/openjdk/jmh/util/MultisetsTest.java	Thu Apr 23 01:56:42 2015 +0300
@@ -0,0 +1,65 @@
+/*
+ * Copyright (c) 2014, 2015, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.  Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package org.openjdk.jmh.util;
+
+import junit.framework.Assert;
+import org.junit.Test;
+
+import java.util.List;
+
+public class MultisetsTest {
+    @Test
+    public void testCountHighest() {
+        Multiset<Integer> set = new HashMultiset<Integer>();
+        set.add(10);
+        set.add(10);
+        set.add(10);
+        set.add(20);
+        set.add(20);
+        set.add(70);
+        List<Integer> topInts = Multisets.countHighest(set, 2);
+
+        Assert.assertEquals(2, topInts.size());
+        Assert.assertEquals((Integer) 10, topInts.get(0));
+        Assert.assertEquals((Integer) 20, topInts.get(1));
+    }
+
+    @Test
+    public void testSortedDesc() {
+        Multiset<Integer> set = new HashMultiset<Integer>();
+        set.add(10);
+        set.add(10);
+        set.add(10);
+        set.add(20);
+        set.add(20);
+        set.add(70);
+        List<Integer> topInts = Multisets.sortedDesc(set);
+
+        Assert.assertEquals(3, topInts.size());
+        Assert.assertEquals((Integer) 10, topInts.get(0));
+        Assert.assertEquals((Integer) 20, topInts.get(1));
+        Assert.assertEquals((Integer) 70, topInts.get(2));
+    }
+}