From b4489e38bff16c4f6ce9ef186f2feed80644fa32 Mon Sep 17 00:00:00 2001 From: Mattias Andrée Date: Sun, 12 Oct 2014 03:39:31 +0200 Subject: fix errors and start on a performance test MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: Mattias Andrée --- src/datastructures/PerformanceTest.java | 95 ++++++++++++++++++++++ .../linkedlists/ArrayCircularDoublyLinkedList.java | 1 + .../linkedlists/ArrayCircularSinglyLinkedList.java | 1 + .../ArrayCircularXORDoublyLinkedList.java | 1 + .../linkedlists/ArrayDoublyLinkedList.java | 1 + .../linkedlists/ArraySentinelDoublyLinkedList.java | 1 + .../linkedlists/ArraySentinelSinglyLinkedList.java | 1 + .../linkedlists/ArraySinglyLinkedList.java | 1 + .../linkedlists/ArrayTaillessDoublyLinkedList.java | 1 + .../linkedlists/ArrayTaillessSinglyLinkedList.java | 1 + .../ArrayTaillessXORDoublyLinkedList.java | 1 + .../linkedlists/ArrayXORDoublyLinkedList.java | 1 + .../linkedlists/CircularDoublyLinkedList.java | 1 + .../linkedlists/CircularSinglyLinkedList.java | 1 + .../linkedlists/DoublyLinkedList.java | 1 + .../linkedlists/HeadlessDoublyLinkedList.java | 1 + .../linkedlists/HeadlessSinglyLinkedList.java | 1 + .../linkedlists/SentinelDoublyLinkedList.java | 1 + .../linkedlists/SentinelSinglyLinkedList.java | 1 + .../linkedlists/SinglyLinkedList.java | 1 + .../linkedlists/TaillessDoublyLinkedList.java | 1 + .../linkedlists/TaillessSinglyLinkedList.java | 1 + src/datastructures/linkedlists/template | 63 ++++++++++---- 23 files changed, 162 insertions(+), 17 deletions(-) create mode 100644 src/datastructures/PerformanceTest.java (limited to 'src/datastructures') diff --git a/src/datastructures/PerformanceTest.java b/src/datastructures/PerformanceTest.java new file mode 100644 index 0000000..b771aad --- /dev/null +++ b/src/datastructures/PerformanceTest.java @@ -0,0 +1,95 @@ +/** + * Copyright © 2014 Mattias Andrée (maandree@member.fsf.org) + * + * 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 . + */ +package datastructures; +import datastructures.linkedlists.*; + +import java.util.Random; + + +/** + * This program be used to test the performance of + * some datastructures + */ +public class PerformanceTest +{ + /** + * This is the main entry point of the test + * + * @param args Command line arguments + */ + public static void main(final String... args) + { + int numElements, maxElements = 1 << 23; + Random rng = new Random(); + + for (numElements = 1; numElements <= maxElements; numElements <<= 1) + { + long time, subtime; + Integer[] elements = new Integer[numElements]; + System.out.println("Using " + numElements + " random elements."); + for (int i = 0; i < numElements; i++) + elements[i] = Integer.valueOf(rng.nextInt()); + + ArrayDoublyLinkedList arrayDoublyLinkedList = + new ArrayDoublyLinkedList(Integer.class); + DoublyLinkedList doublyLinkedList = + new DoublyLinkedList(Integer.class); + ArraySinglyLinkedList arraySinglyLinkedList = + new ArraySinglyLinkedList(Integer.class); + SinglyLinkedList singlyLinkedList = + new SinglyLinkedList(Integer.class); + ArraySentinelDoublyLinkedList arraySentinelDoublyLinkedList = + new ArraySentinelDoublyLinkedList(Integer.class); + SentinelDoublyLinkedList sentinelDoublyLinkedList = + new SentinelDoublyLinkedList(Integer.class); + ArraySentinelSinglyLinkedList arraySentinelSinglyLinkedList = + new ArraySentinelSinglyLinkedList(Integer.class); + SentinelSinglyLinkedList sentinelSinglyLinkedList = + new SentinelSinglyLinkedList(Integer.class); + + System.out.println(); + System.out.println("Insert at beginning:"); + +£list=${list_a,,}${list_b} + System.gc(); + try + { + Thread.sleep(100); + } catch(InterruptedException e) {} + time = 0; + for (int i = 0; i < numElements; i++) + { + subtime = System.nanoTime(); + £{list}.insertBeginning(elements[i]); + time += System.nanoTime() - subtime; + } + time /= numElements; + System.out.printf("%30s: %7d.%03d µs/element\n", "£{class}", + time / 1000, time % 1000); + £{list} = null; +£>done + + System.out.println(); + System.out.println(); + } + } + +} + diff --git a/src/datastructures/linkedlists/ArrayCircularDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayCircularDoublyLinkedList.java index a77de10..cb2c1b6 100644 --- a/src/datastructures/linkedlists/ArrayCircularDoublyLinkedList.java +++ b/src/datastructures/linkedlists/ArrayCircularDoublyLinkedList.java @@ -15,6 +15,7 @@ * along with this program. If not, see . */ package datastructures.linkedlists; +import java.lang.reflect.Array; /** diff --git a/src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java b/src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java index b67eb69..bc5e2e8 100644 --- a/src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java +++ b/src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java @@ -15,6 +15,7 @@ * along with this program. If not, see . */ package datastructures.linkedlists; +import java.lang.reflect.Array; /** diff --git a/src/datastructures/linkedlists/ArrayCircularXORDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayCircularXORDoublyLinkedList.java index 862433b..d29d39b 100644 --- a/src/datastructures/linkedlists/ArrayCircularXORDoublyLinkedList.java +++ b/src/datastructures/linkedlists/ArrayCircularXORDoublyLinkedList.java @@ -15,6 +15,7 @@ * along with this program. If not, see . */ package datastructures.linkedlists; +import java.lang.reflect.Array; /** diff --git a/src/datastructures/linkedlists/ArrayDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayDoublyLinkedList.java index 4a1df1d..182787f 100644 --- a/src/datastructures/linkedlists/ArrayDoublyLinkedList.java +++ b/src/datastructures/linkedlists/ArrayDoublyLinkedList.java @@ -15,6 +15,7 @@ * along with this program. If not, see . */ package datastructures.linkedlists; +import java.lang.reflect.Array; /** diff --git a/src/datastructures/linkedlists/ArraySentinelDoublyLinkedList.java b/src/datastructures/linkedlists/ArraySentinelDoublyLinkedList.java index 0b357f5..93b9abd 100644 --- a/src/datastructures/linkedlists/ArraySentinelDoublyLinkedList.java +++ b/src/datastructures/linkedlists/ArraySentinelDoublyLinkedList.java @@ -15,6 +15,7 @@ * along with this program. If not, see . */ package datastructures.linkedlists; +import java.lang.reflect.Array; /** diff --git a/src/datastructures/linkedlists/ArraySentinelSinglyLinkedList.java b/src/datastructures/linkedlists/ArraySentinelSinglyLinkedList.java index aab6b2f..79822ea 100644 --- a/src/datastructures/linkedlists/ArraySentinelSinglyLinkedList.java +++ b/src/datastructures/linkedlists/ArraySentinelSinglyLinkedList.java @@ -15,6 +15,7 @@ * along with this program. If not, see . */ package datastructures.linkedlists; +import java.lang.reflect.Array; /** diff --git a/src/datastructures/linkedlists/ArraySinglyLinkedList.java b/src/datastructures/linkedlists/ArraySinglyLinkedList.java index 635bf83..efe69c0 100644 --- a/src/datastructures/linkedlists/ArraySinglyLinkedList.java +++ b/src/datastructures/linkedlists/ArraySinglyLinkedList.java @@ -15,6 +15,7 @@ * along with this program. If not, see . */ package datastructures.linkedlists; +import java.lang.reflect.Array; /** diff --git a/src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java index 24b9740..3c41d56 100644 --- a/src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java +++ b/src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java @@ -15,6 +15,7 @@ * along with this program. If not, see . */ package datastructures.linkedlists; +import java.lang.reflect.Array; /** diff --git a/src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java b/src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java index 20e71c0..06f9210 100644 --- a/src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java +++ b/src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java @@ -15,6 +15,7 @@ * along with this program. If not, see . */ package datastructures.linkedlists; +import java.lang.reflect.Array; /** diff --git a/src/datastructures/linkedlists/ArrayTaillessXORDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayTaillessXORDoublyLinkedList.java index 6984c19..c530ca2 100644 --- a/src/datastructures/linkedlists/ArrayTaillessXORDoublyLinkedList.java +++ b/src/datastructures/linkedlists/ArrayTaillessXORDoublyLinkedList.java @@ -15,6 +15,7 @@ * along with this program. If not, see . */ package datastructures.linkedlists; +import java.lang.reflect.Array; /** diff --git a/src/datastructures/linkedlists/ArrayXORDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayXORDoublyLinkedList.java index a06302d..3b4bb40 100644 --- a/src/datastructures/linkedlists/ArrayXORDoublyLinkedList.java +++ b/src/datastructures/linkedlists/ArrayXORDoublyLinkedList.java @@ -15,6 +15,7 @@ * along with this program. If not, see . */ package datastructures.linkedlists; +import java.lang.reflect.Array; /** diff --git a/src/datastructures/linkedlists/CircularDoublyLinkedList.java b/src/datastructures/linkedlists/CircularDoublyLinkedList.java index 21e7a48..63997e2 100644 --- a/src/datastructures/linkedlists/CircularDoublyLinkedList.java +++ b/src/datastructures/linkedlists/CircularDoublyLinkedList.java @@ -15,6 +15,7 @@ * along with this program. If not, see . */ package datastructures.linkedlists; +import java.lang.reflect.Array; /** diff --git a/src/datastructures/linkedlists/CircularSinglyLinkedList.java b/src/datastructures/linkedlists/CircularSinglyLinkedList.java index df60349..08f2754 100644 --- a/src/datastructures/linkedlists/CircularSinglyLinkedList.java +++ b/src/datastructures/linkedlists/CircularSinglyLinkedList.java @@ -15,6 +15,7 @@ * along with this program. If not, see . */ package datastructures.linkedlists; +import java.lang.reflect.Array; /** diff --git a/src/datastructures/linkedlists/DoublyLinkedList.java b/src/datastructures/linkedlists/DoublyLinkedList.java index 699ea12..fc0eeb0 100644 --- a/src/datastructures/linkedlists/DoublyLinkedList.java +++ b/src/datastructures/linkedlists/DoublyLinkedList.java @@ -15,6 +15,7 @@ * along with this program. If not, see . */ package datastructures.linkedlists; +import java.lang.reflect.Array; /** diff --git a/src/datastructures/linkedlists/HeadlessDoublyLinkedList.java b/src/datastructures/linkedlists/HeadlessDoublyLinkedList.java index 636e12a..444e7b3 100644 --- a/src/datastructures/linkedlists/HeadlessDoublyLinkedList.java +++ b/src/datastructures/linkedlists/HeadlessDoublyLinkedList.java @@ -15,6 +15,7 @@ * along with this program. If not, see . */ package datastructures.linkedlists; +import java.lang.reflect.Array; /** diff --git a/src/datastructures/linkedlists/HeadlessSinglyLinkedList.java b/src/datastructures/linkedlists/HeadlessSinglyLinkedList.java index 43c006c..821439c 100644 --- a/src/datastructures/linkedlists/HeadlessSinglyLinkedList.java +++ b/src/datastructures/linkedlists/HeadlessSinglyLinkedList.java @@ -15,6 +15,7 @@ * along with this program. If not, see . */ package datastructures.linkedlists; +import java.lang.reflect.Array; /** diff --git a/src/datastructures/linkedlists/SentinelDoublyLinkedList.java b/src/datastructures/linkedlists/SentinelDoublyLinkedList.java index d13c676..c448c52 100644 --- a/src/datastructures/linkedlists/SentinelDoublyLinkedList.java +++ b/src/datastructures/linkedlists/SentinelDoublyLinkedList.java @@ -15,6 +15,7 @@ * along with this program. If not, see . */ package datastructures.linkedlists; +import java.lang.reflect.Array; /** diff --git a/src/datastructures/linkedlists/SentinelSinglyLinkedList.java b/src/datastructures/linkedlists/SentinelSinglyLinkedList.java index 7ee3512..2bef187 100644 --- a/src/datastructures/linkedlists/SentinelSinglyLinkedList.java +++ b/src/datastructures/linkedlists/SentinelSinglyLinkedList.java @@ -15,6 +15,7 @@ * along with this program. If not, see . */ package datastructures.linkedlists; +import java.lang.reflect.Array; /** diff --git a/src/datastructures/linkedlists/SinglyLinkedList.java b/src/datastructures/linkedlists/SinglyLinkedList.java index acbc55b..8e9e1d3 100644 --- a/src/datastructures/linkedlists/SinglyLinkedList.java +++ b/src/datastructures/linkedlists/SinglyLinkedList.java @@ -15,6 +15,7 @@ * along with this program. If not, see . */ package datastructures.linkedlists; +import java.lang.reflect.Array; /** diff --git a/src/datastructures/linkedlists/TaillessDoublyLinkedList.java b/src/datastructures/linkedlists/TaillessDoublyLinkedList.java index ea88413..b58599f 100644 --- a/src/datastructures/linkedlists/TaillessDoublyLinkedList.java +++ b/src/datastructures/linkedlists/TaillessDoublyLinkedList.java @@ -15,6 +15,7 @@ * along with this program. If not, see . */ package datastructures.linkedlists; +import java.lang.reflect.Array; /** diff --git a/src/datastructures/linkedlists/TaillessSinglyLinkedList.java b/src/datastructures/linkedlists/TaillessSinglyLinkedList.java index 7cf113f..106decd 100644 --- a/src/datastructures/linkedlists/TaillessSinglyLinkedList.java +++ b/src/datastructures/linkedlists/TaillessSinglyLinkedList.java @@ -15,6 +15,7 @@ * along with this program. If not, see . */ package datastructures.linkedlists; +import java.lang.reflect.Array; /** diff --git a/src/datastructures/linkedlists/template b/src/datastructures/linkedlists/template index 53a7c4a..b225457 100644 --- a/src/datastructures/linkedlists/template +++ b/src/datastructures/linkedlists/template @@ -120,6 +120,21 @@ public class £{name} } + /** + * Constructor + */ + public £{name}(Class tClass) + { + this.tClass = tClass; +£>if (( with_sentinel )); then +£>new node null + this.edge = node; +£>for var in $refs; do + £($var this.edge) = £(singularity this.edge); +£>done +£>fi + } + £>else /** @@ -153,9 +168,10 @@ public class £{name} /** * Constructor */ - public £{name}() + @SuppressWarnings("unchecked") + public £{name}(Class tClass) { - this(DEFAULT_INITIAL_CAPACITY); + this(tClass, DEFAULT_INITIAL_CAPACITY); } /** @@ -164,15 +180,23 @@ public class £{name} * @param initialCapacity The initial size of the arrays */ @SuppressWarnings("unchecked") - public £{name}(int initialCapacity) + public £{name}(Class tClass, int initialCapacity) { + this.tClass = tClass; initialCapacity = algorithms.bits.Powers.toPowerOf2(initialCapacity); this.capacity = initialCapacity; £>for var in $refs reusable; do this.£{var} = new int[initialCapacity]; £>done - this.values = (T[])(new Object[initialCapacity]); + this.values = (T[])(Array.newInstance(this.tClass, initialCapacity)); +£>if (( with_sentinel )); then +£>new node null + this.edge = node; +£>for var in $refs; do + £($var this.edge) = £(singularity this.edge); +£>done +£>fi } @@ -233,22 +257,27 @@ public class £{name} £>fi £>fi + /** + * Java's generics erasure is kind of silly + * when it comes to arrays. We can either + * create {@code Object[]} and cast it to + * {@code T[]} and let the user of the class + * cast it back to {@code Object[]}, get an + * element and cast it back to {@code T}; or + * we can let the user not only specify + * {@code } when calling the constructor, + * but also add an {@code T.class} argument + * and then store that argument so we can + * at any time use the class {@link Array} + * to create an array. + */ + private Class tClass; + £>if (( with_sentinel )); then /** * The sentinel node in the list */ public £{Node} edge; - - /** - * Initialiser - */ - { -£>new node null - this.edge = node; -£>for var in $refs; do - £($var this.edge) = £(singularity this.edge); -£>done - } £>fi £>if (( with_head )); then @@ -290,7 +319,7 @@ public class £{name} £>(( with_xor )) && int prev = EDGE; @SuppressWarnings("unchecked") - T[] vals = (T[])(new Object[cap]); + T[] vals = (T[])(Array.newInstance(this.tClass, cap)); £>if (( 1 - with_head )); then int head = 0; while ((head < this.end) && (£($forward head) == UNUSED)) @@ -359,7 +388,7 @@ public class £{name} if (this.end == this.capacity) { this.capacity <<= 1; - System.arraycopy(this.values, 0, this.values = (T[])(new Object[this.capacity]), 0, this.end); + System.arraycopy(this.values, 0, this.values = (T[])(Array.newInstance(this.tClass, this.capacity)), 0, this.end); £>for var in $refs reusable; do System.arraycopy(this.£{var}, 0, this.£{var} = new int[this.capacity], 0, this.end); £>done -- cgit v1.2.3-70-g09d2