diff options
Diffstat (limited to 'test/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TestHeapPerformance.java')
-rw-r--r-- | test/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TestHeapPerformance.java | 127 |
1 files changed, 0 insertions, 127 deletions
diff --git a/test/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TestHeapPerformance.java b/test/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TestHeapPerformance.java deleted file mode 100644 index f80fbec5..00000000 --- a/test/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TestHeapPerformance.java +++ /dev/null @@ -1,127 +0,0 @@ -package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; - -/* - This file is part of ELKI: - Environment for Developing KDD-Applications Supported by Index-Structures - - Copyright (C) 2012 - Ludwig-Maximilians-Universität München - Lehr- und Forschungseinheit für Datenbanksysteme - ELKI Development Team - - This program is free software: you can redistribute it and/or modify - it under the terms of the GNU Affero General Public License as published by - the Free Software Foundation, either version 3 of the License, or - (at your option) any later version. - - This program 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 Affero General Public License for more details. - - You should have received a copy of the GNU Affero General Public License - along with this program. If not, see <http://www.gnu.org/licenses/>. - */ - -import static org.junit.Assert.assertEquals; -import static org.junit.Assert.assertTrue; - -import java.util.ArrayList; -import java.util.Collections; -import java.util.List; -import java.util.PriorityQueue; -import java.util.Queue; -import java.util.Random; - -import org.junit.Test; - -/** - * Unit test to ensure that our heap is not significantly worse than SUN javas - * regular PriorityQueue. - * - * @author Erich Schubert - */ -public class TestHeapPerformance { - final private int queueSize = 200000; - - final private int preiterations = 20; - - final private int iterations = 200; - - final private long seed = 123456L; - - @Test - public void testRuntime() throws Exception { - // prepare the data set - final List<Integer> elements = new ArrayList<>(queueSize); - { - final Random random = new Random(seed); - for(int i = 0; i < queueSize; i++) { - elements.add(i); - } - Collections.shuffle(elements, random); - } - - // Pretest, to trigger hotspot compiler, hopefully. - { - for(int j = 0; j < preiterations; j++) { - ComparableMinHeap<Integer> pq = new ComparableMinHeap<>(); - testHeap(elements, pq); - } - for(int j = 0; j < preiterations; j++) { - PriorityQueue<Integer> pq = new PriorityQueue<>(); - testQueue(elements, pq); - } - } - - long pqstart = System.nanoTime(); - { - for(int j = 0; j < iterations; j++) { - PriorityQueue<Integer> pq = new PriorityQueue<>(); - testQueue(elements, pq); - } - } - long pqtime = System.nanoTime() - pqstart; - - long hstart = System.nanoTime(); - { - for(int j = 0; j < iterations; j++) { - ComparableMinHeap<Integer> pq = new ComparableMinHeap<>(); - testHeap(elements, pq); - } - } - long htime = System.nanoTime() - hstart; - - System.err.println("Heap performance test: us: " + htime*1E-9 + " java: " + pqtime*1E-9); - assertTrue("Heap performance regression - run test individually, since the hotspot optimizations may make the difference! " + htime + " >>= " + pqtime, htime < 1.05 * pqtime); - // 1.05 allows some difference in measuring - } - - private void testHeap(final List<Integer> elements, ComparableMinHeap<Integer> pq) { - // Insert all - for(int i = 0; i < elements.size(); i++) { - pq.add(elements.get(i)); - } - // Poll first half. - for(int i = 0; i < elements.size() >> 1; i++) { - assertEquals((int) pq.poll(), i); - // assertEquals((int) pq.poll(), queueSize - 1 - i); - } - assertTrue("Heap not half-empty?", pq.size() == (elements.size() >> 1)); - pq.clear(); - } - - private void testQueue(final List<Integer> elements, Queue<Integer> pq) { - // Insert all - for(int i = 0; i < elements.size(); i++) { - pq.add(elements.get(i)); - } - // Poll first half. - for(int i = 0; i < elements.size() >> 1; i++) { - assertEquals((int) pq.poll(), i); - // assertEquals((int) pq.poll(), queueSize - 1 - i); - } - assertTrue("Heap not half-empty?", pq.size() == (elements.size() >> 1)); - pq.clear(); - } -}
\ No newline at end of file |