Heiner Kücker
2007-10-31 19:12:45 UTC
Permalink
Christian Schmelzer schriebPost by Christian Schmelzer
Post by Heiner Kücker
Christian Schmelzer schrieb
Post by Christian Schmelzer
Hallo,
ich habe ein Array mit int Werten. Im Ergebnis dürfen keine doppelten
Einträge übrig bleiben.
int[] test = new int[] {1, 2, 3, 4, 5, 5, 5, 6, 7};
=>
int[] ergebnis = new int[] {1, 2, 3, 4, 5, 6, 7};
Die Sortierung ist unwichtig. Bis jetzt sind mir nur nicht gerade effektive
Wege eingefallen. Hat jemand eine gute Idee?
umwandeln in eine HashMap putten.
Aus dieser kannst Du dann entweder mit
map.toArray( new Integer[ map.size() ] );
wieder die Integer-Objekte auslesen.
Dies dann wiederum mit einer
Schleife in ein int-Array
kopieren (umwandeln).
Hallo,
das war auch meine Idee, aber das klingt für mich nicht effektiv. Wenn mir
nix besseres einfällt, werde ich das erstmal nehmen und vielleicht später
das mal ändern.
Evtl auch so:
/*
* Copyright 2003, Dr. Matthias Laux
*
* This file is part of ML Utilities.
*
* ML Utilities is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* ML Utilities 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 for more details.
*
* You should have received a copy of the GNU General Public License
* along with ML Utilities; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
USA
*/
//package ml.tool;
package util.collections.primitve;
/**
* A hash map mapping int values to objects. This offers the benefit of not
having to use objects
* as keys, which can result in performance benefits.
*/
public class IntHashSet
{
/**
* The default capacity for hash map instances.
*/
public static final int DEFAULT_CAPACITY = 17;
/**
* The maximum allowed capacity for hash map instances.
*/
public static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The default load factor for hash map instances.
*/
public static final float DEFAULT_LOADFACTOR = 0.75f;
private SetElement[] map = null; // The first bucket for
each key
private int[] count = null; // The count of buckets
in each chain
private int contents = 0;
private int objectCounter = 0; // Counter for objects
created
private int capacity = DEFAULT_CAPACITY;
private int initialCap = DEFAULT_CAPACITY;
private float loadFactor = DEFAULT_LOADFACTOR;
private int maxLoad = 0;
private boolean rehashing = true;
/**
* Constructs an empty instance with the default initial capacity and the
default load factor
*/
public IntHashSet() {
this(DEFAULT_CAPACITY, DEFAULT_LOADFACTOR);
}
/**
* Constructs an empty instance with the given initial capacity and the
default load factor
* <p>
* @param initialCapacity The initial capacity for this hash map.
*/
public IntHashSet(int initialCapacity) {
this(initialCapacity, DEFAULT_LOADFACTOR);
}
/**
* Constructs an empty instance with the given initial capacity and the
given load factor
* <p>
* @param initialCapacity The initial capacity for this hash map.
* @param loadFactor The load factor for this hash map.
*/
public IntHashSet(int initialCapacity, float loadFactor) {
construct(initialCapacity, loadFactor);
}
/**
* Constructs a new HashMap with the same mappings as the specified Map. The
HashMap
* is created with default load factor and an initial capacity sufficient to
hold the
* mappings in the specified Map.
* <p>
* @param m The map whose mappings are to be placed in this map. Throws:
* <p>
* @throws NullPointerException if the specified map is <code>null</code>.
*/
public IntHashSet(IntHashSet m) {
if (m == null) throw new IllegalArgumentException("m may not be null");
//.... Determine parameters
loadFactor = DEFAULT_LOADFACTOR; // As per standard API
for java.util.HashMap
capacity = (int)(m.size()/loadFactor);
if (capacity < DEFAULT_CAPACITY) { // Avoid underflow
capacity = DEFAULT_CAPACITY;
} else if (capacity % 2 == 0) { // Make sure we have
an odd value
capacity++;
}
//.... Standard initialization for the internal map elements
maxLoad = (int)(loadFactor*capacity + 0.5f); // Max. number of
elements before a rehash occurs
initialCap = capacity;
objectCounter += 2;
map = new SetElement[capacity];
count = new int[capacity];
//.... Copy the elements to the new map
int[] keys = m.keySet();
for (int i = 0; i < m.size(); i++) {
//put(keys[i], m.get(keys[i]));
add( keys[i] );
}
}
/**
* Return the current number of mappings in the hash map.
* <p>
* @return The current number of mappings in the hash map.
*/
public int size() {
return contents;
}
/**
* Returns <code>true</code> if this map contains no key-value mappings.
*/
public boolean isEmpty() {
return contents == 0;
}
/**
* Removes all mappings from this map.
*/
public void clear() {
construct(initialCap, loadFactor);
}
/**
* Return the number of objects created in / by this instance
* <p>
* @return The number of objects created
*/
public int getObjectCounter() {
return objectCounter;
}
/**
* Return the current capacity of the instance. If rehashing is enabled
(which it is per
* default), the capacity may have been increased as necessary from the
initial value.
* <p>
* @return The current capacity for this hash map.
*/
public int getCapacity() {
return capacity;
}
/**
* Return the load factor of the instance.
* <p>
* @return The load factor for this hash map.
*/
public float getLoadFactor() {
return loadFactor;
}
/**
* Return the keys in the hash map
* <p>
* @return An array containing the keys for which mappings are stored in
this hash map.
*/
public int[] keySet() {
objectCounter++;
int[] keys = new int[contents];
int cnt = 0;
SetElement me = null;
for (int i = 0; i < capacity; i++) {
if (map[i] != null) {
me = map[i];
for (int j = 0; j < count[i]; j++) {
keys[cnt++] = me.getKey();
me = me.getNext();
}
}
}
return keys;
}
/**
* Enable/disable rehashing (defaults to <code>true</code>).
* <p>
* @param pIsRehashing A boolean indicating the desired rehashing status.
*/
public void setRehash(boolean pIsRehashing) {
this.rehashing = pIsRehashing;
}
/**
* Associates the specified value with the specified key in this map. If
* the map previously contained a mapping for this key, the old value is
replaced.
* <p>
* @param key The key with which the specified value is to be associated.
* @param value The value to be associated with the specified key.
* <p>
* @return Previous value associated with specified key, or
<code>null</code> if there was no mapping
* for key. A <code>null</code> return can also indicate that the
HashMap previously associated <code>null</code>
* with the specified key.
*/
public
//Object
boolean
//put
add(
int key
//, Object value
)
{
int index = computeIndex( key );
//.... This is a new key since no bucket exists
if (map[index] == null) {
objectCounter++;
map[index] =
new SetElement(
key
//, value
);
count[index]++;
contents++;
if (contents > maxLoad) rehash();
return true; // Eelemnt noch nicht enthalten im set null;
//.... A bucket already exists for this index: check whether we already have
a mapping for this key
} else {
SetElement me = map[index];
while (true) {
if (me.getKey() == key) { // We have a mapping: just
replace the value for this element
//Object previous = me.getValue(); // Return the current
value - same as for java.util.HashMap.put()
//me.setValue(value);
return false; // object schon im set enthalten previous;
} else {
if (me.getNext() == null) { // No next element: so we have
no mapping for this key
objectCounter++;
me.setNext(
new SetElement(
key
//, value
));
count[index]++;
contents++;
if (contents > maxLoad) rehash();
return true; // Eelemnt noch nicht enthalten im set null;
} else {
me = me.getNext();
}
}
}
}
}
/**
* Returns the value to which the specified key is mapped in this identity
* hash map, or <code>null</code> if the map contains no mapping for this
key. A return
* value of <code>null</code> does not necessarily indicate that the map
contains no
* mapping for the key; it is also possible that the map explicitly maps
* the key to <code>null</code>. The <code>containsKey</code>
* method may be used to distinguish these two cases.
* <p>
* @param key The key whose associated value is to be returned.
* <p>
* @return The value to which this map maps the specified key, or
* <code>null</code> if the map contains no mapping for this key.
*/
public
//Object get
boolean contains
(int key) {
SetElement me = exists(key);
if (me == null) {
return false; // null;
} else {
return true; // me.getValue();
}
}
/**
* Returns <code>true</code> if this map contains a mapping for the
specified key.
* <p>
* @param key The key whose presence in this map is to be tested.
* <p>
* @return <code>true</code> if this map contains a mapping for the
specified key.
*/
public boolean containsKey(int key) {
if (exists(key) == null) {
return false;
} else {
return true;
}
}
/**
* Removes the mapping for this key from this map if present.
* <p>
* @param key The key whose mapping is to be removed from the map.
* <p>
* @return Previous value associated with specified key, or
* <code>null</code> if there was no mapping for key. A
<code>null</code> return can
* also indicate that the map previously associated
<code>null</code> with the specified key.
*/
public
//Object
boolean
remove(int key)
{
int index = computeIndex( key );
if (map[index] == null) {
return false; // null;
} else {
SetElement me = map[index];
SetElement prev = null;
while (true) {
if (me.getKey() == key) { // Keys match
if (prev == null) { // The first element in the chain
matches
map[index] = me.getNext();
} else { // An element further down in the
chain matches - delete it from the chain
prev.setNext(me.getNext());
}
count[index]--;
contents--;
return true; // me.getValue();
} else { // Keys don't match, try the next
element
prev = me;
me = me.getNext();
if (me == null)
{
return false; // null;
}
}
}
}
}
/**
* Helper method: returns the element matching the key, or <code>null</code>
if no such element exists
*/
private SetElement exists(int key)
{
int index = computeIndex( key );
if (map[index] == null) {
return null;
} else {
SetElement me = map[index];
while (true) {
if (me.getKey() == key) {
return me;
} else {
me = me.getNext();
if (me == null) return null;
}
}
}
}
/**
* Increase the capacity of the map to improve performance
*/
private void rehash() {
if (rehashing) {
int newCapacity = 2*capacity + 1;
if (newCapacity > MAXIMUM_CAPACITY) return;
objectCounter += 2;
SetElement[] newMap = new SetElement[newCapacity];
int[] newCount = new int[newCapacity];
SetElement me = null;
SetElement t = null;
SetElement next = null;
int newIndex = 0;
for (int index = 0; index < capacity; index++) {
me = map[index];
while (me != null) {
next = me.getNext();
newIndex = me.getKey() % newCapacity;
if (newIndex < 0) newIndex = -newIndex;
newCount[newIndex]++;
if (newMap[newIndex] == null) { // No element yet for
this new index
newMap[newIndex] = me;
me.setNext(null);
} else { // Hook the element
into the beginning of the chain
t = newMap[newIndex];
newMap[newIndex] = me;
me.setNext(t);
}
me = next;
}
}
map = newMap;
count = newCount;
capacity = newCapacity;
maxLoad = (int)(loadFactor*capacity + 0.5f); // Max. number
of elements before a rehash occurs
newMap = null;
}
}
/**
* Construction helper method
*/
private void construct(int initialCapacity, float loadFactor) {
if (initialCapacity < 0) throw new IllegalArgumentException("Invalid
initial capacity: " + initialCapacity);
if (initialCapacity < DEFAULT_CAPACITY) initialCapacity =
DEFAULT_CAPACITY;
if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity =
MAXIMUM_CAPACITY;
if (loadFactor <= 0.0f || Float.isNaN(loadFactor)) throw new
IllegalArgumentException("Invalid load factor: " + loadFactor);
this.initialCap = initialCapacity;
this.capacity = initialCapacity;
this.loadFactor = loadFactor;
objectCounter += 2;
maxLoad = (int)(loadFactor*capacity + 0.5f); // Max.
number of elements before a rehash occurs
map = new SetElement[capacity];
count = new int[capacity];
contents = 0;
}
/**
* Statistical output for this map.
* <p>
* @param full A boolean indicating whether just a short of the full
information should be printed.
*/
public void printStatistics(boolean full) {
if (full) {
for (int i = 0; i < capacity; i++) {
System.out.println("Count[" + i + "] = " + count[i]);
}
}
System.out.println("Initial capacity = " + initialCap);
System.out.println("Capacity = " + capacity);
System.out.println("Number of elements = " + contents);
}
/**
* @param key
* @return
*/
private int computeIndex(
final int key)
{
int index = key % capacity;
if (index < 0) index = -index;
return index;
}
/**
*
*/
class SetElement
{
// TODO default scope und direkter zugriff statt get set
private int key = 0;
//private Object value = null;
private SetElement next = null;
/**
* Constructor
*/
public SetElement(
final int key
//, Object value
)
{
this.key = key;
//this.value = value;
}
/**
* Getter method for <code>key</code> property
* <p>
* @return The value for the <code>key</code> property
*/
public int getKey() {
return key;
}
/**
* Setter method for <code>value</code> property
* <p>
* @param value The value for the <code>value</code> property
*/
// public void setValue(Object value) {
// this.value = value;
// }
/**
* Getter method for <code>value</code> property
* <p>
* @return The value for the <code>value</code> property
*/
// public Object getValue() {
// return value;
// }
/**
* Setter method for <code>next</code> property
* <p>
* @param next The value for the <code>next</code> property
*/
public void setNext(SetElement next) {
this.next = next;
}
/**
* Getter method for <code>next</code> property
* <p>
* @return The value for the <code>next</code> property
*/
public SetElement getNext() {
return next;
}
}
}
--
Heiner Kücker
www.heinerkuecker.de
www.control-and-command.de
Wanja Gayk
2007-11-01 13:45:59 UTC
Permalink
Christian Schmelzer said...Post by Christian Schmelzer
Post by Heiner Kücker
Du kannst die int-Werte in Integer-Objekte
umwandeln in eine HashMap putten.
Post by Christian Schmelzer
Hallo,
das war auch meine Idee, aber das klingt für mich nicht effektiv. Wenn mir
nix besseres einfällt, werde ich das erstmal nehmen und vielleicht später
das mal ändern.
der Speicehrverbrauch, weil es nicht "in place" geschieht.
HashSet#put(Object) hat ne Laufzeit von O(1) und die Werte des Sets zu
holen hat eine Laufzeit von O(n), insgesamt also O(n), effizienter geht
es kaum, es sei denn du hast ein HashSet von primitiven* oder dein
Wertebereich ist so eng begrenzt, dass es sich lohnt auf das Hashing zu
verzichten und für jeden Wert ein Flag zu setzen. ob er vorkommt.
Hier also drei Lösungen:
a) J2SE, hashing:
Diese Lösung ist gut, sie läuft in O(n) und hat einen passablen
Speicherverbrauch.
import java.util.Set;
import java.util.HashSet;
public int[] withoutDupes(final int[] array){
if(array.length==0){return array;}
if(array.length==1){return new int[]{array[0]};}
final Set set = new HashSet<Integer>();
for(final int value : array){
set.add(value);
}
final int[] result = new int[s.size()];
int t=-1;
for(final int value : set){
result[++t]=value;
}
return result;
}
b) Trove, hashing:
Diese Lösung ist besser, sie läuft in O(n), hat einen passablen
Speicherverbrauch, ist lesbarer und verzichtet auf das Boxing/Unboxing
von Integer-Werten.
import gnu.trove.TIntHashSet;
public int[] withoutDupes(final int[] array){
if(array.length==0){return array;}
if(array.length==1){return new int[]{array[0]};}
final TIntHashSet set = new TIntHashSet();
set.addAll(array);
return set.toArray();
}
c) J2SE, Buckets:
Diese Lösung ist scheiße.
Den Grund dazu erkläre ich weiter unten, erst mal der Code:
public int[] withoutDupes(final int[] array) {
if(array.length==0){return array;}
if(array.length==1){return new int[]{array[0]};}
//scan range:
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (final int value : array) {
if (value < min) {min = value;}
if (value > max) { max = value;}
}
//check range
final int range = Math.abs(max - min);
if (range == Integer.MAX_VALUE || range<0) {
throw new IllegalArgumentException("array content range too large ");
}
//scan for values
int resultLen = 0;
final boolean[] seen = new boolean[range + 1];
for (final int value : array) {
final int pos = value - min;
if (!seen[pos]) {
seen[pos] = true;
++resultLen;
}
}
//build result:
int[] result = new int[resultLen];
int resPos = -1;
for (int t = 0; t < seen.length; ++t) {
if (seen[t]) {
result[++resPos] = t + min;
}
}
return result;
}
Wie du siehst, hat das Bucket-Verfahren die Nachteile, dass:
- bei einem unbekannten Wertebereich dieser durch einen zusätzichen
Durchlauf heraus gefunden werden muss (scan range)
- dass der Wertebereich begrenzt ist (check range)
- die Laufzeit und der Speicherverbrauch nicht nur von der Menge (n) der
Eingabedaten, sondern auch von deren Wertebereich (m) direkt abhängt,
die Laufzeit liegt bei O(n+m), genauso wie der Speicherverbrauch - das
ist zwar noch linear, aber trotzdem untragbar.
Worst case (Gibt bei mir einen OutOfMemoryError):
int[] worstCase = new int[Integer.MAX_VALUE];
worstCase[1]=Integer.MAX_VALUE-1;
Als Demonstration (bei mir noch lauffähig):
int[] badCase = new int[Integer.MAX_VALUE/64];
badCase [1]=Integer.MAX_VALUE/32;
dauert etwa 1 Sekunde (Athlon XP 2400+, 2 GHz);
Ich würde deswegen Möglichkeit c) streichen, es sei denn dein
Wertebereich ist wirklich klein und von vornherein fest.
Gruß,
-Wanja-
[*] //trove4j.sourceforge.net/
Siehe: TIntHashSet in //trove4j.sourceforge.net/javadocs/
--
"Gewisse Schriftsteller sagen von ihren Werken immer: 'Mein Buch, mein
Kommentar, meine Geschichte'. [..] Es wäre besser, wenn sie sagten:
'unser Buch, unser Kommentar, unsere Geschichte'; wenn man bedenkt, dass
das Gute darin mehr von anderen ist als von ihnen." [Blaise Pascal]
Christian Schmelzer
2007-11-01 15:17:12 UTC
Permalink
Post by Wanja Gayk
Christian Schmelzer said...
Post by Christian Schmelzer
Post by Heiner Kücker
Du kannst die int-Werte in Integer-Objekte
umwandeln in eine HashMap putten.
Post by Christian Schmelzer
Hallo,
das war auch meine Idee, aber das klingt für mich nicht effektiv.
Wenn mir nix besseres einfällt, werde ich das erstmal nehmen und
vielleicht später das mal ändern.
ggf der Speicehrverbrauch, weil es nicht "in place" geschieht.
HashSet#put(Object) hat ne Laufzeit von O(1) und die Werte des Sets zu
holen hat eine Laufzeit von O(n), insgesamt also O(n), effizienter geht
es kaum, es sei denn du hast ein HashSet von primitiven* oder dein
Wertebereich ist so eng begrenzt, dass es sich lohnt auf das Hashing
zu verzichten und für jeden Wert ein Flag zu setzen. ob er vorkommt.
[3 Lösungen]
Post by Wanja Gayk
Ich würde deswegen Möglichkeit c) streichen, es sei denn dein
Wertebereich ist wirklich klein und von vornherein fest.
vielen Dank für die umfangreichen Lösungen. Das Trove Projekt kannte ich
noch nicht, sieht aber vielversprechend auch für ähnliche Probleme aus.
Christian
Ralf Ullrich
2007-11-01 23:34:34 UTC
Permalink
Post by Sven Köhler
Post by Achim Peters
... finde ich sehr effektiv.
Ich würde tippen, dass die "Sortieren und rausfiltern" mit einem Array
in etwa die hälfte der Zeit braucht - mindestens.
Messen nicht Tippen!
Ich dachte auch ein leicht modifizierter Heapsort sei die beste Lösung,
aber nach Messungen sieht es dann (bei mir) so aus:
1. Platz: Heiner Kückers HashSet mit geboxten Integern:
public int[] unique(int[] a) {
Set<Integer> set = new HashSet<Integer>();
for (int v : a) {
set.add(v);
}
int[] rv = new int[set.size()];
int i = 0;
for (Integer v : set) {
rv[i++] = v;
}
return rv;
}
Das ist zwar bei wenigen Dubletten etwa 10% langsamer als der 2. Platz,
ist aber sehr klarer und kurzer Code und wird schneller je größer der
Anteil der Dubletten ist.
[Nachtrag: Mit dieser kleinen Änderung:
// Set<Integer> set = new HashSet<Integer>();
Set<Integer> set = new HashSet<Integer>(a.length);
ist diese Variante sogar im allgemeinen schneller als der 2. Platz, weil
die Präallokation im Schnitt 15-30% Laufzeit einspart.]
2. Platz: Bernd Posts Array-Sort und Unique-Copy:
public int[] unique(int[] a) {
if (a.length == 0) {
return a;
}
int[] b = a.clone();
Arrays.sort(b);
int j = 1;
int i = 1;
int v = b[0];
while (i < b.length) {
int w = b[i++];
if (v != w) {
b[j++] = v = w;
}
}
return Arrays.copyOf(b, j);
}
Hier ist das Problem, dass, selbst wenn viele Dubletten vorhanden sind,
diese dennoch sortiert werden müssen. Dies ist offenbar ein so großer
Nachteil, dass der zusätzliche Aufwand für Boxing in der ersten Lösung
sehr schnell ausgeglichen wird, je größer die Arrays werden.
3. Platz: Mein modifizierter Heap-Sort:
public int[] unique(final int[] a) {
if (a.length == 0) {
return a;
}
int size = a.length;
int[] q = new int[size + 1];
System.arraycopy(a, 0, q, 1, size);
for (int i = size / 2; i > 0; i--) {
{
int k = i;
int v = q[k];
while (k <= size / 2) {
int j = 2 * k;
if ((j < size) && (q[j] < q[j + 1])) {
j += 1;
}
if (v >= q[j]) {
break;
}
q[k] = q[j];
k = j;
}
q[k] = v;
}
}
int pos = size + 1;
int last = q[1];
q[1] = q[size--];
q[--pos] = last;
while (size > 0) {
{
int k = 1;
int v = q[k];
while (k <= size / 2) {
int j = 2 * k;
if ((j < size) && (q[j] < q[j + 1])) {
j += 1;
}
if (v >= q[j]) {
break;
}
q[k] = q[j];
k = j;
}
q[k] = v;
}
int v = q[1];
q[1] = q[size--];
if (v < last) {
last = q[--pos] = v;
}
}
return Arrays.copyOfRange(q, pos, q.length);
}
}
Ziemlich komplexer unüberschaubarer Code, der zu allem Überfluss dann
sogar in der Regel deutlich langsamer bleibt, als die beiden vorherigen
Lösungen, obwohl O(n*log(n)) bereits der Worst-Case ist und es im Schnitt
deutlich in Richtung O(n) gehen sollte. Aber auch hier müssen Dubletten
erst mit einsortiert werden.
Nicht im Rennen, weil keine allgemeine Lösung, sondern nur für begrenzte
Wertebereiche möglich: Stefan Rams Vorschlag mit Flags:
public int[] unique(int[] a) {
boolean[] seen = new boolean[a.length+2];
int[] rv = new int[a.length];
int size = 0;
for (int v : a) {
if (!seen[v]) {
rv[size++] = v;
seen[v] = true;
}
}
return Arrays.copyOf(rv, size);
}
Natürlich wieder sehr schöner klarer und kurzer Code und vor allem
wirklich rasant. Im Schnitt bei mir zehnmal schneller als der 1. Platz und
kann vor allem auch von vielen Dubletten profitieren.
Alles in allem wieder mal ein Lehrstück in Sachen »frühzeitige Optimierung
ist übel«, da beide naiven Implementierungen (HKs und BPs) bereits sehr
schnell sind, und für beide nur schwer bessere Lösungen geschrieben werden
können.
Ich würde an dieser Stelle vermuten, dass man im Originalprogramm nur dann
deutliche Verbesserungen erreichen kann, wenn man den schlechten »quasi
primitiven« Datentyp 'Array' durch einen *abstrakten* Datentyp ersetzt,
und dieser dann in einer Besser-Als-Simples-Array-Implementierung
bestimmte Eigenschaften des Problemraums ausnutzen kann. Ein solcher
abstrakter Datentyp könnte dann vielleicht schon beim dem Prozess der
Erzeugung der »Ganzzahlsammlungen« ansetzen und Dubletten bereits dabei
ausschließen.
cu
PS: Ich habe vorwiegend mit großen Arrays (length > 1000) gemessen, ich
denke mit kleinen Arrays würden HKs und BPs Lösung die Plätze tauschen.
Wanja Gayk
2007-11-01 23:51:50 UTC
Permalink
Ralf Ullrich said...Post by Ralf Ullrich
Nicht im Rennen, weil keine allgemeine Lösung, sondern nur für begrenzte
public int[] unique(int[] a) {
boolean[] seen = new boolean[a.length+2];
int[] rv = new int[a.length];
int size = 0;
for (int v : a) {
if (!seen[v]) {
rv[size++] = v;
seen[v] = true;
}
}
return Arrays.copyOf(rv, size);
}
Natürlich wieder sehr schöner klarer und kurzer Code und vor allem
wirklich rasant. Im Schnitt bei mir zehnmal schneller als der 1. Platz und
kann vor allem auch von vielen Dubletten profitieren.
Wert >= 2*array.length im Array und das Ding knallt ihm um die Ohren.
Das ist schon sehr begrenzt, da würde ich die naive Implementation mit
einer HashMap vorziehen, solange es nicht unbedingt nötig ist.
Post by Ralf Ullrich
Alles in allem wieder mal ein Lehrstück in Sachen »frühzeitige Optimierung
ist übel«, da beide naiven Implementierungen (HKs und BPs) bereits sehr
schnell sind, und für beide nur schwer bessere Lösungen geschrieben werden
können.
Gruß,
-Wanja-
--
"Gewisse Schriftsteller sagen von ihren Werken immer: 'Mein Buch, mein
Kommentar, meine Geschichte'. [..] Es wäre besser, wenn sie sagten:
'unser Buch, unser Kommentar, unsere Geschichte'; wenn man bedenkt, dass
das Gute darin mehr von anderen ist als von ihnen." [Blaise Pascal]
Ralf Ullrich
2007-11-02 02:45:43 UTC
Permalink
Post by Sven Köhler
Post by Ralf Ullrich
Messen nicht Tippen!
Ich dachte auch ein leicht modifizierter Heapsort sei die beste Lösung,
Kannste vielleicht nochmal messen, mit dem HashSet von trove4j ?
Ausnahmsweise, denn normalerweise halte ich nix von solchen 3rd-Party
Bibliotheken, wie commons und (was wohl gerade im Kommen ist) trove.
Post by Sven Köhler
Die haben ja auch so spezielle HashSets extra für ints - ohne
Wrapperobjekte und so.
public int[] unique(int[] a) {
return new TIntHashSet(a).toArray();
}
Ist bei meinen Tests mal doppelt so schnell und mal halb so schnell wie
die Standard-Lösung mit HashSet<Integer>. Im Vergleich zu dieser zeigt
sich, dass die Trove-Variante im Trend umso schlechter ist, je kleiner die
Arrays sind bzw. je mehr Dubletten es gibt.
Was wieder Mal zeigt, dass meine Vorbehalte begründet sind, da Troves
TIntHashSet in vielen Anwendungen offensichtlich langsamer ist, als ein
HashSet<Integer> mit Boxing. Trove wird seinem vorgeblichen Ruf also
keineswegs gerecht.
cu
PS: Hier eine komplette (aufgewärmte) Messreihe, wobei >Simple< die
Array-Sort-Und-Unique-Copy Variante ist, und >Example< die Beispieldaten
aus dem OP sind, und die übrigen Testcases so gebildet werden:
// ### range/size
static int[] testcase(int range, int size) {
Random r = new Random(0);
int[] rv = new int[size];
for (int i = 0; i < size; i++) {
rv[i] = r.nextInt(range);
}
return rv;
}
### Example 0,472s Simple 0,985s HKImpl 1,238s Trove
### 1/15 0,471s Simple 0,708s HKImpl 1,403s Trove
### 2/15 0,565s Simple 0,793s HKImpl 1,700s Trove
### 5/15 0,888s Simple 1,034s HKImpl 2,050s Trove
### 10/15 0,820s Simple 1,301s HKImpl 2,202s Trove
### 15/15 0,865s Simple 1,471s HKImpl 2,198s Trove
### 1/150 0,214s Simple 0,488s HKImpl 0,847s Trove
### 10/150 0,717s Simple 0,562s HKImpl 0,877s Trove
### 50/150 1,143s Simple 0,874s HKImpl 0,966s Trove
### 100/150 1,262s Simple 1,146s HKImpl 1,064s Trove
### 150/150 1,353s Simple 1,367s HKImpl 1,134s Trove
### 10/1500 0,660s Simple 0,444s HKImpl 0,796s Trove
### 100/1500 1,154s Simple 0,528s HKImpl 0,859s Trove
### 500/1500 1,687s Simple 1,005s HKImpl 0,936s Trove
### 1000/1500 1,802s Simple 1,286s HKImpl 1,022s Trove
### 1500/1500 1,865s Simple 1,496s HKImpl 1,060s Trove
### 100/15000 1,087s Simple 0,431s HKImpl 0,808s Trove
### 1000/15000 1,684s Simple 0,730s HKImpl 0,857s Trove
### 5000/15000 2,177s Simple 1,397s HKImpl 0,966s Trove
### 10000/15000 2,319s Simple 1,800s HKImpl 1,076s Trove
### 15000/15000 2,366s Simple 2,056s HKImpl 1,108s Trove
Achja, noch zu erwähnen ist, dass die Anzahl Wiederholungen (loop) so
gewählt ist, dass in jeder Zeile gilt:
size * loop = constant
Ralf Ullrich
2007-11-02 19:01:44 UTC
Permalink
Post by Heiner Kücker
Könntest Du mal den Main-Code für die Messung posten.
Class-Path nehmen.)
cu
package de.jnana.dclj;
import gnu.trove.TIntHashSet;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;
public class UniqueIntArrayDemo {
public interface UniqueIntArrayFunction {
int[] unique(int[] a);
}
public static class Simple implements UniqueIntArrayFunction {
@Override
public int[] unique(int[] a) {
if (a.length == 0) {
return a;
}
int[] b = a.clone();
Arrays.sort(b);
int j = 1;
int i = 1;
int v = b[0];
while (i < b.length) {
int w = b[i++];
if (v != w) {
b[j++] = v = w;
}
}
return Arrays.copyOf(b, j);
}
}
public static class HKImpl implements UniqueIntArrayFunction {
@Override
public int[] unique(int[] a) {
Set<Integer> set = new HashSet<Integer>(a.length);
for (int v : a) {
set.add(v);
}
int[] rv = new int[set.size()];
int i = 0;
for (Integer v : set) {
rv[i++] = v;
}
return rv;
}
}
public static class Trove implements UniqueIntArrayFunction {
@Override
public int[] unique(int[] a) {
return new TIntHashSet(a).toArray();
}
}
public static class SRImpl implements UniqueIntArrayFunction {
public int[] unique(int[] a) {
boolean[] seen = new boolean[a.length + 2];
int[] rv = new int[a.length];
int size = 0;
for (int v : a) {
if (!seen[v]) {
rv[size++] = v;
seen[v] = true;
}
}
return Arrays.copyOf(rv, size);
}
}
public static class Heap implements UniqueIntArrayFunction {
@Override
public int[] unique(final int[] a) {
if (a.length == 0) {
return a;
}
int size = a.length;
int[] q = a.clone();
for (int i = (size - 1) / 2; i >= 0; i--) {
{
int k = i;
int v = q[k];
while (2 * k + 1 < size) {
int j = 2 * k + 1; // k < (size-1)/2
if ((j + 1 < size) && (q[j] < q[j + 1])) {
j += 1;
}
if (v >= q[j]) {
break;
}
q[k] = q[j];
k = j;
}
q[k] = v;
}
}
int pos = size;
int last = q[0];
q[0] = q[--size];
q[--pos] = last;
while (size > 0) {
{
int k = 0;
int v = q[k];
while (2 * k + 1 < size) {
int j = 2 * k + 1;
if ((j + 1 < size) && (q[j] < q[j + 1])) {
j += 1;
}
if (v >= q[j]) {
break;
}
q[k] = q[j];
k = j;
}
q[k] = v;
}
int v = q[0];
q[0] = q[--size];
if (v < last) {
last = q[--pos] = v;
}
}
return Arrays.copyOfRange(q, pos, q.length);
}
}
public static class HeapOrig implements UniqueIntArrayFunction {
@Override
public int[] unique(final int[] a) {
if (a.length == 0) {
return a;
}
int size = a.length;
int[] q = new int[size + 1];
System.arraycopy(a, 0, q, 1, size);
for (int i = size / 2; i > 0; i--) {
{
int k = i;
int v = q[k];
while (k <= size / 2) {
int j = 2 * k;
if ((j < size) && (q[j] < q[j + 1])) {
j += 1;
}
if (v >= q[j]) {
break;
}
q[k] = q[j];
k = j;
}
q[k] = v;
}
}
int pos = size + 1;
int last = q[1];
q[1] = q[size--];
q[--pos] = last;
while (size > 0) {
{
int k = 1;
int v = q[k];
while (k <= size / 2) {
int j = 2 * k;
if ((j < size) && (q[j] < q[j + 1])) {
j += 1;
}
if (v >= q[j]) {
break;
}
q[k] = q[j];
k = j;
}
q[k] = v;
}
int v = q[1];
q[1] = q[size--];
if (v < last) {
last = q[--pos] = v;
}
}
return Arrays.copyOfRange(q, pos, q.length);
}
}
static int[] testcase(int range, int size) {
Random r = new Random(0);
int[] rv = new int[size];
for (int i = 0; i < size; i++) {
rv[i] = r.nextInt(range);
}
return rv;
}
static boolean equalsUnordered(final int[] a, final int[] b) {
int[] aa = a.clone();
int[] bb = b.clone();
Arrays.sort(aa);
Arrays.sort(bb);
return Arrays.equals(aa, bb);
}
static void time(String msg, UniqueIntArrayFunction[] tests, int[] data, int[] expect, int loop) {
if (expect == null) {
expect = new Simple().unique(data.clone());
}
StringBuilder sb = new StringBuilder(String.format("%-18s", msg));
for (UniqueIntArrayFunction fn : tests) {
int[] copy = data.clone();
long start = System.nanoTime();
int[] result;
int n = loop;
do {
result = fn.unique(copy);
} while (--n > 0);
long end = System.nanoTime();
boolean success = Arrays.equals(data, copy) && equalsUnordered(result, expect);
double seconds = (end - start) / 1000000000.0;
sb.append(String.format("%7.3fs %s %-6s", seconds, success ? "OK" : "NO", fn.getClass().
getSimpleName()));
}
System.out.println(sb.toString());
}
public static void main(String[] args) {
UniqueIntArrayFunction[] tests = new UniqueIntArrayFunction[]{new Simple(), new HKImpl(), new Trove()};
// , new SRImpl(), new Heap()
for (int warmup = 0; warmup < 10; warmup++) {
time("### Example", tests, new int[]{1, 2, 3, 4, 5, 5, 5, 6, 7}, new int[]{1, 2, 3, 4, 5, 6, 7},
1000000);
time("### 1/15", tests, testcase(1, 15), null, 1000000);
time("### 2/15", tests, testcase(2, 15), null, 1000000);
time("### 5/15", tests, testcase(5, 15), null, 1000000);
time("### 10/15", tests, testcase(10, 15), null, 1000000);
time("### 15/15", tests, testcase(15, 15), null, 1000000);
time("### 1/150", tests, testcase(1, 150), null, 100000);
time("### 10/150", tests, testcase(10, 150), null, 100000);
time("### 50/150", tests, testcase(50, 150), null, 100000);
time("### 100/150", tests, testcase(100, 150), null, 100000);
time("### 150/150", tests, testcase(150, 150), null, 100000);
time("### 10/1500", tests, testcase(10, 1500), null, 10000);
time("### 100/1500", tests, testcase(100, 1500), null, 10000);
time("### 500/1500", tests, testcase(500, 1500), null, 10000);
time("### 1000/1500", tests, testcase(1000, 1500), null, 10000);
time("### 1500/1500", tests, testcase(1500, 1500), null, 10000);
time("### 100/15000", tests, testcase(100, 15000), null, 1000);
time("### 1000/15000", tests, testcase(1000, 15000), null, 1000);
time("### 5000/15000", tests, testcase(5000, 15000), null, 1000);
time("### 10000/15000", tests, testcase(10000, 15000), null, 1000);
time("### 15000/15000", tests, testcase(15000, 15000), null, 1000);
}
}
}
Heiner Kücker
2007-11-03 10:09:36 UTC
Permalink
Ralf Ullrich schriebPost by Ralf Ullrich
Post by Heiner Kücker
Könntest Du mal den Main-Code für die Messung posten.
Class-Path nehmen.)
Danke, Super.
Ich habe den Test für die Variante mit dem Trie die
ganze Nacht laufen lassen.
Grottenschlecht.
Von 20 mal so schlecht bis 1000 mal so schlecht
schwankt es.
Das hätte ich nicht gedacht.
Also das Standard-Java-API ist gar nicht so
leicht zu schlagen:
package de.jnana.dclj;
//import gnu.trove.TIntHashSet;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;
import util.collections.primitve.IntTrieSet;
public class UniqueIntArrayDemo {
public interface UniqueIntArrayFunction {
int[] unique(int[] a);
}
public static class Simple implements UniqueIntArrayFunction {
// @Override
public int[] unique(int[] a) {
if (a.length == 0) {
return a;
}
int[] b = a.clone();
Arrays.sort(b);
int j = 1;
int i = 1;
int v = b[0];
while (i < b.length) {
int w = b[i++];
if (v != w) {
b[j++] = v = w;
}
}
return Arrays.copyOf(b, j);
}
}
public static class HKImpl implements UniqueIntArrayFunction {
// @Override
public int[] unique(int[] a) {
Set<Integer> set = new HashSet<Integer>(a.length);
for (int v : a) {
set.add(v);
}
int[] rv = new int[set.size()];
int i = 0;
for (Integer v : set) {
rv[i++] = v;
}
return rv;
}
}
// public static class Trove implements UniqueIntArrayFunction {
// @Override
// public int[] unique(int[] a) {
// return new TIntHashSet(a).toArray();
// }
// }
public static class Trie implements UniqueIntArrayFunction {
//@Override
public int[] unique(int[] a) {
return new IntTrieSet(a).toArray();
}
}
public static class SRImpl implements UniqueIntArrayFunction {
public int[] unique(int[] a) {
boolean[] seen = new boolean[a.length + 2];
int[] rv = new int[a.length];
int size = 0;
for (int v : a) {
if (!seen[v]) {
rv[size++] = v;
seen[v] = true;
}
}
return Arrays.copyOf(rv, size);
}
}
public static class Heap implements UniqueIntArrayFunction {
// @Override
public int[] unique(final int[] a) {
if (a.length == 0) {
return a;
}
int size = a.length;
int[] q = a.clone();
for (int i = (size - 1) / 2; i >= 0; i--) {
{
int k = i;
int v = q[k];
while (2 * k + 1 < size) {
int j = 2 * k + 1; // k < (size-1)/2
if ((j + 1 < size) && (q[j] < q[j + 1])) {
j += 1;
}
if (v >= q[j]) {
break;
}
q[k] = q[j];
k = j;
}
q[k] = v;
}
}
int pos = size;
int last = q[0];
q[0] = q[--size];
q[--pos] = last;
while (size > 0) {
{
int k = 0;
int v = q[k];
while (2 * k + 1 < size) {
int j = 2 * k + 1;
if ((j + 1 < size) && (q[j] < q[j + 1])) {
j += 1;
}
if (v >= q[j]) {
break;
}
q[k] = q[j];
k = j;
}
q[k] = v;
}
int v = q[0];
q[0] = q[--size];
if (v < last) {
last = q[--pos] = v;
}
}
return Arrays.copyOfRange(q, pos, q.length);
}
}
public static class HeapOrig implements UniqueIntArrayFunction {
// @Override
public int[] unique(final int[] a) {
if (a.length == 0) {
return a;
}
int size = a.length;
int[] q = new int[size + 1];
System.arraycopy(a, 0, q, 1, size);
for (int i = size / 2; i > 0; i--) {
{
int k = i;
int v = q[k];
while (k <= size / 2) {
int j = 2 * k;
if ((j < size) && (q[j] < q[j + 1])) {
j += 1;
}
if (v >= q[j]) {
break;
}
q[k] = q[j];
k = j;
}
q[k] = v;
}
}
int pos = size + 1;
int last = q[1];
q[1] = q[size--];
q[--pos] = last;
while (size > 0) {
{
int k = 1;
int v = q[k];
while (k <= size / 2) {
int j = 2 * k;
if ((j < size) && (q[j] < q[j + 1])) {
j += 1;
}
if (v >= q[j]) {
break;
}
q[k] = q[j];
k = j;
}
q[k] = v;
}
int v = q[1];
q[1] = q[size--];
if (v < last) {
last = q[--pos] = v;
}
}
return Arrays.copyOfRange(q, pos, q.length);
}
}
static int[] testcase(int range, int size) {
Random r = new Random(0);
int[] rv = new int[size];
for (int i = 0; i < size; i++) {
rv[i] = r.nextInt(range);
}
return rv;
}
static boolean equalsUnordered(final int[] a, final int[] b) {
int[] aa = a.clone();
int[] bb = b.clone();
Arrays.sort(aa);
Arrays.sort(bb);
return Arrays.equals(aa, bb);
}
static void time(String msg, UniqueIntArrayFunction[] tests, int[]
data, int[] expect, int loop) {
if (expect == null) {
expect = new Simple().unique(data.clone());
}
StringBuilder sb = new StringBuilder(String.format("%-18s", msg));
for (UniqueIntArrayFunction fn : tests) {
int[] copy = data.clone();
long start = System.nanoTime();
int[] result;
int n = loop;
do {
result = fn.unique(copy);
} while (--n > 0);
long end = System.nanoTime();
boolean success = Arrays.equals(data, copy) &&
equalsUnordered(result, expect);
double seconds = (end - start) / 1000000000.0;
sb.append(String.format("%7.3fs %s %-6s", seconds, success ?
"OK" : "NO", fn.getClass().
getSimpleName()));
}
System.out.println(sb.toString());
}
public static void main(String[] args) {
UniqueIntArrayFunction[] tests =
new UniqueIntArrayFunction[]{
new Simple(),
new HKImpl(),
//new Trove()
new Trie()
};
// , new SRImpl(), new Heap()
for (int warmup = 0; warmup < 10; warmup++) {
time("### Example", tests, new int[]{1, 2, 3, 4, 5, 5, 5, 6,
7}, new int[]{1, 2, 3, 4, 5, 6, 7},
1000000);
time("### 1/15", tests, testcase(1, 15), null, 1000000);
time("### 2/15", tests, testcase(2, 15), null, 1000000);
time("### 5/15", tests, testcase(5, 15), null, 1000000);
time("### 10/15", tests, testcase(10, 15), null, 1000000);
time("### 15/15", tests, testcase(15, 15), null, 1000000);
time("### 1/150", tests, testcase(1, 150), null, 100000);
time("### 10/150", tests, testcase(10, 150), null, 100000);
time("### 50/150", tests, testcase(50, 150), null, 100000);
time("### 100/150", tests, testcase(100, 150), null, 100000);
time("### 150/150", tests, testcase(150, 150), null, 100000);
time("### 10/1500", tests, testcase(10, 1500), null, 10000);
time("### 100/1500", tests, testcase(100, 1500), null, 10000);
time("### 500/1500", tests, testcase(500, 1500), null, 10000);
time("### 1000/1500", tests, testcase(1000, 1500), null,
10000);
time("### 1500/1500", tests, testcase(1500, 1500), null,
10000);
time("### 100/15000", tests, testcase(100, 15000), null, 1000);
time("### 1000/15000", tests, testcase(1000, 15000), null,
1000);
time("### 5000/15000", tests, testcase(5000, 15000), null,
1000);
time("### 10000/15000", tests, testcase(10000, 15000), null,
1000);
time("### 15000/15000", tests, testcase(15000, 15000), null,
1000);
}
}
}
package util.collections.primitve;
import java.util.Arrays;
import de.heinerkuecker.util.TestFailedException;
/**
* Diese experimentelle Klasse
* enthält ein Set von int-Werten
* (Primitiven) welches als
* Trie oder sogenannter
* Patricia-Baum aufgebaut ist.
*
* Dabei wird für jedes Bit
* der zu vermekenden int-Werte
* ein 2-stelliges boolean-Array
* angelegt.
*
* Begonnen wird mit dem
* niederwertigsten Bit.
*
* Je nach dem, ob das
* betrachtete Bit 0 oder
* 1 ist, wird im jeweiligen
* linken oder rechten
* Sub-Array weitergesucht.
*
* Ist das nächste Sub-Array
* null, so sind alle Werte
* ab diesem Bit nicht vorhanden.
*
* Wird das letzte Array erreicht,
* so entscheidet der Zustand
* des Boolean-Merkers, ob
* der entsprechende int-Wert
* vermerkt ist oder nicht.
*
* TODO statt Arrays mit je zwei Einträgen mal mit Arrays mit 4, 8 oder 16
Einträgen testen
*
* @author Heiner Kücker
*/
public class IntTrieSet
{
public static final int BIT_COUNT = 32;
private Object[] trieArr =
new Object[ 2 ];
private int size;
/**
* Constructor
*/
public IntTrieSet()
{
super();
}
/**
* Constructor
*/
public IntTrieSet(
final int[] pIntArr )
{
super();
addAll( pIntArr );
}
/**
* @param pIntArr
*/
public void addAll(
final int[] pIntArr )
{
for (int i = 0; i < pIntArr.length; i++ )
{
add( pIntArr[ i ] );
}
}
/**
* Zurückgeben der Anzahl vermerkter Werte
* @return Anzahl vermerkter Werte
* @see java.util.Set#size()
*/
public int size()
{
return this.size;
}
/**
* Alle vermerkten
* Werte löschen.
*/
public void clear()
{
this.size = 0;
this.trieArr[ 0 ] = null;
this.trieArr[ 1 ] = null;
}
/**
* Vermerken des übergebenen
* int-Wertes.
*
* @param pValue zu vermerkender Wert
* @return <tt>true</tt> if this set did not already contain the specified
* element.
* @see java.util.Set#add(E)
*/
public boolean add(
final int pValue )
{
Object[] runArr =
this.trieArr;
int bitMask = 1;
// TODO umstellen auf abwärts zählen, weil Test auf 0 schneller sein
soll
for (int i = 0; i < BIT_COUNT - 2; i++ )
{
//System.out.println( "bitMask: " + bitMask );
final boolean isBit =
( pValue & bitMask ) != 0;
final Object[] preRunArr =
runArr;
if ( isBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
runArr = (Object[]) runArr[ 1 ];
if ( runArr == null )
{
runArr =
new Object[ 2 ];
preRunArr[ 1 ] =
runArr;
}
}
else
{
runArr = (Object[]) runArr[ 0 ];
if ( runArr == null )
{
runArr =
new Object[ 2 ];
preRunArr[ 0 ] =
runArr;
}
}
bitMask = ( bitMask << 1 );
}
final boolean isPreLastBit =
( pValue & bitMask ) != 0;
boolean[] finalArr;
if ( isPreLastBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
finalArr = (boolean[]) runArr[ 1 ];
if ( finalArr == null )
{
finalArr =
new boolean[ 2 ];
runArr[ 1 ] =
finalArr;
}
}
else
{
finalArr = (boolean[]) runArr[ 0 ];
if ( finalArr == null )
{
finalArr =
new boolean[ 2 ];
runArr[ 0 ] =
finalArr;
}
}
bitMask = ( bitMask << 1 );
final boolean isLastBit =
( pValue & bitMask ) != 0;
final boolean isValueNotAlreadyContain;
if ( isLastBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
isValueNotAlreadyContain =
!finalArr[ 1 ];
finalArr[ 1 ] = true;
}
else
{
isValueNotAlreadyContain =
! finalArr[ 0 ];
finalArr[ 0 ] = true;
}
if ( isValueNotAlreadyContain )
{
this.size++;
}
return isValueNotAlreadyContain;
}
/**
* Prüfen, ob der übergebene
* int-Wert in diesem Set enthalten ist.
*
* @param pValue zu prüfender Wert
* @return <tt>true</tt> if this set contains the specified element.
* @see java.util.Set#contains(java.lang.Object)
*/
public boolean contains(
final int pValue )
{
Object[] runArr =
this.trieArr;
int bitMask = 1;
// TODO umstellen auf abwärts zählen, weil Test auf 0 schneller sein
soll
for (int i = 0; i < BIT_COUNT - 2; i++ )
{
//System.out.println( "bitMask: " + bitMask );
final boolean isBit =
( pValue & bitMask ) != 0;
// final Object[] preRunArr =
// runArr;
if ( isBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
runArr = (Object[]) runArr[ 1 ];
if ( runArr == null )
{
return false;
}
}
else
{
runArr = (Object[]) runArr[ 0 ];
if ( runArr == null )
{
return false;
}
}
bitMask = ( bitMask << 1 );
}
final boolean isPreLastBit =
( pValue & bitMask ) != 0;
boolean[] finalArr;
if ( isPreLastBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
finalArr = (boolean[]) runArr[ 1 ];
if ( finalArr == null )
{
return false;
}
}
else
{
finalArr = (boolean[]) runArr[ 0 ];
if ( finalArr == null )
{
return false;
}
}
bitMask = ( bitMask << 1 );
final boolean isLastBit =
( pValue & bitMask ) != 0;
final boolean isValueContain;
if ( isLastBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
isValueContain =
finalArr[ 1 ];
}
else
{
isValueContain =
finalArr[ 0 ];
}
return isValueContain;
}
/**
* Entfernen des übergebenen
* int-Wertes.
*
* @param pValue zu entfernender Wert
* @return true if the set contained the specified element.
* @see java.util.Set#remove(java.lang.Object)
*/
public boolean remove(
final int pValue )
{
Object[] runArr =
this.trieArr;
int bitMask = 1;
final PathElem[] pathArr =
new PathElem[ BIT_COUNT - 2 ];
// TODO umstellen auf abwärts zählen, weil Test auf 0 schneller sein
soll
for (int i = 0; i < BIT_COUNT - 2; i++ )
{
//System.out.println( "bitMask: " + bitMask );
final boolean isBit =
( pValue & bitMask ) != 0;
if ( i > 0 )
{
pathArr[ i ] =
new PathElem(
// Achtung es ist wichtig, dass das gleiche
// Array referenziert wird und keine Kopie/Clone
runArr,
isBit ? 1 : 0 );
}
// final Object[] preRunArr =
// runArr;
if ( isBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
runArr = (Object[]) runArr[ 1 ];
if ( runArr == null )
{
return false;
}
}
else
{
runArr = (Object[]) runArr[ 0 ];
if ( runArr == null )
{
return false;
}
}
bitMask = ( bitMask << 1 );
}
final boolean isPreLastBit =
( pValue & bitMask ) != 0;
boolean[] finalArr;
if ( isPreLastBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
finalArr = (boolean[]) runArr[ 1 ];
if ( finalArr == null )
{
return false;
}
}
else
{
finalArr = (boolean[]) runArr[ 0 ];
if ( finalArr == null )
{
return false;
}
}
bitMask = ( bitMask << 1 );
final boolean isLastBit =
( pValue & bitMask ) != 0;
final boolean isValuePreviousContain;
if ( isLastBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
isValuePreviousContain =
finalArr[ 1 ];
finalArr[ 1 ] = false;
if ( finalArr[ 0 ] == false )
// beide Einträge sind false, Array kann gelöscht werden
{
runArr[ isPreLastBit ? 1 : 0 ] = null;
}
}
else
{
isValuePreviousContain =
finalArr[ 0 ];
finalArr[ 0 ] = false;
if ( finalArr[ 1 ] == false )
// beide Einträge sind false, Array kann gelöscht werden
{
runArr[ isPreLastBit ? 1 : 0 ] = null;
}
}
if ( isValuePreviousContain )
{
this.size--;
/*
* nicht benutzte Knoten Löschen um Speicher freizugeben
*/
for ( int i = pathArr.length - 1 ; i > 0 ; i-- )
{
final PathElem pathElem =
pathArr[ i ];
final Object[] pathTrieArr =
pathElem.trieArr;
final Object[] subPathTrieArr =
(Object[]) pathTrieArr[
pathElem.trieArrIndex ];
if ( subPathTrieArr[ 0 ] == null && subPathTrieArr[ 1 ] == null )
// das aktuelle Pfad Element ist leer und kann gelöscht werden
{
// final PathElem parentPathElem =
// pathArr[ i - 1 ];
//
// parentPathElem.trieArr[
// parentPathElem.trieArrIndex ]
// = null;
// break;
pathTrieArr[ pathElem.trieArrIndex ] = null;
}
}
}
return isValuePreviousContain;
}
/**
* Zurückgeben aller enthaltenen
* Werte als Objekt-Array.
* @return Array mit allen enthaltenen Werten als Objekte
*/
public Integer[] toObjArray()
{
final int[] shortPrmvArr =
toArray();
final Integer[] retArr =
new Integer[ shortPrmvArr.length ];
for (int i = 0; i < shortPrmvArr.length; i++ )
{
final int tmp = shortPrmvArr[i];
retArr[ i ] =
new Integer( tmp );
}
return retArr;
}
/**
* Zurückgeben aller enthaltenen
* Werte als Array.
* @return Array mit allen enthaltenen Werten
*/
public int[] toArray()
{
final ShortArrAndIndexVo vo =
new ShortArrAndIndexVo(
this.size );
innerToArray(
vo ,
this.trieArr ,
0 ,
0 );
final int[] retArr =
vo.shortArr;
Arrays.sort( retArr );
return retArr;
}
/**
* @param pVo Value-Objekt zum Sammeln der Werte
* @param pTrieArrNode aktueller zu prüfender Knoten
* @param pBitPos Position des aktuell bearbeiteten Bits
* @param pPreValue bisheriger Wert, der an der aktuellen bit-Position um
1 oder 0 erhöht werden muss
*/
private void innerToArray(
final ShortArrAndIndexVo pVo ,
final Object[] pTrieArrNode ,
final int pBitPos ,
final int pPreValue )
{
if ( pTrieArrNode == null )
// Pfad endet hier
{
return;
}
if ( pBitPos < BIT_COUNT - 2 )
// finales Merker-Array noch nicht erreicht
{
innerToArray(
pVo ,
(Object[]) pTrieArrNode[ 0 ] ,
pBitPos + 1 ,
pPreValue /* + 0 */ );
innerToArray(
pVo ,
(Object[]) pTrieArrNode[ 1 ] ,
pBitPos + 1 ,
pPreValue + (int) Math.pow( 2 , ( pBitPos ) ) );
}
else
// finales Merker-Array erreicht
{
{
final boolean[] finalArr0 =
(boolean[]) pTrieArrNode[ 0 ];
if ( finalArr0 != null )
{
final int preValue =
pPreValue + 0;
if ( finalArr0[ 0 ] )
{
pVo.add(
preValue );
}
if ( finalArr0[ 1 ] )
{
pVo.add(
(int) (
preValue +
Math.pow( 2 , ( BIT_COUNT - 1 ) ) ) );
}
}
}
{
final boolean[] finalArr1 =
(boolean[]) pTrieArrNode[ 1 ];
if ( finalArr1 != null )
{
final int preValue =
pPreValue +
(int) Math.pow( 2 , ( BIT_COUNT - 2 ) );
if ( finalArr1[ 0 ] )
{
pVo.add(
preValue );
}
if ( finalArr1[ 1 ] )
{
pVo.add(
(int) (
preValue +
Math.pow( 2 , BIT_COUNT - 1 ) ) );
}
}
}
}
}
/**
* Value-Objekt mit einem
* int-Array und einem
* Index.
*/
static final class ShortArrAndIndexVo
{
/**
* Array zum Sammeln der Werte
*/
final int[] shortArr;
/**
* aktueller Index
*/
int index;
/**
* Constructor
* @param pSize
*/
public ShortArrAndIndexVo(
final int pSize )
{
super();
this.shortArr =
new int[ pSize ];
}
/**
* Set value at index position
* and increment index.
* @param pValue
*/
public void add(
final int pValue )
{
this.shortArr[ this.index ] =
pValue;
this.index++;
}
}
/**
* Hilfsklasse für ein Element
* des Pfades zu einem Eintrag
* in einem {@link IntTrieSet}.
*
* Wird benutzt in
* {@link IntTrieSet#remove(int)}
*/
static final class PathElem
{
/**
* Sub-Array des Pfades
* innerhalb des Baumes
*/
final Object[] trieArr;
/**
* Index zum nächsten
* hierarchisch tiefergelegenen
* Sub-Array des Pfades
*/
final int trieArrIndex;
/**
* Constructor
* @param pTrieArr
* @param pTrieArrIndex
*/
public PathElem(Object[] pTrieArr, int pTrieArrIndex)
{
super();
// TODO Auto-generated constructor stub
this.trieArr = pTrieArr;
this.trieArrIndex = pTrieArrIndex;
}
/**
* debug output
* @see java.lang.Object#toString()
*/
@Override
public String toString()
{
return
"trieArr: " + Arrays.asList( this.trieArr ) +
"trieArrIndex: " + this.trieArrIndex;
}
}
/**
* @param args
*/
public static void main(
String[] args )
{
final IntTrieSet set = new IntTrieSet();
/*
* add 1
*/
boolean valPrvContain = ! set.add( 1 );
if ( valPrvContain || set.size() != 1 )
{
throw new TestFailedException();
}
if ( set.contains( 0 ) )
{
throw new TestFailedException();
}
if ( ! set.contains( 1 ) )
{
throw new TestFailedException();
}
String setStr = Arrays.asList( set.toObjArray() ).toString();
System.out.println( setStr );
if ( ! setStr.equals( "[1]" ) )
{
throw new TestFailedException();
}
/*
* add 2
*/
valPrvContain = ! set.add( 2 );
if ( valPrvContain || set.size() != 2 )
{
throw new TestFailedException();
}
if ( set.contains( 0 ) )
{
throw new TestFailedException();
}
if ( ! set.contains( 1 ) )
{
throw new TestFailedException();
}
if ( ! set.contains( 2 ) )
{
throw new TestFailedException();
}
setStr = Arrays.asList( set.toObjArray() ).toString();
System.out.println( setStr );
if ( ! setStr.equals( "[1, 2]" ) )
{
throw new TestFailedException();
}
/*
* remove 1
*/
valPrvContain = set.remove( 1 );
if ( ( ! valPrvContain ) || set.size() != 1 )
{
throw new TestFailedException();
}
if ( set.contains( 0 ) )
{
throw new TestFailedException();
}
if ( set.contains( 1 ) )
{
throw new TestFailedException();
}
if ( ! set.contains( 2 ) )
{
throw new TestFailedException();
}
setStr = Arrays.asList( set.toObjArray() ).toString();
System.out.println( setStr );
if ( ! setStr.equals( "[2]" ) )
{
throw new TestFailedException();
}
/*
* remove 2
*/
valPrvContain = set.remove( 2 );
if ( ( ! valPrvContain ) || set.size() != 0 )
{
throw new TestFailedException();
}
if ( set.contains( 0 ) )
{
throw new TestFailedException();
}
if ( set.contains( 1 ) )
{
throw new TestFailedException();
}
if ( set.contains( 2 ) )
{
throw new TestFailedException();
}
setStr = Arrays.asList( set.toObjArray() ).toString();
System.out.println( setStr );
if ( ! setStr.equals( "[]" ) )
{
throw new TestFailedException();
}
}
}
package util.collections.primitve;
import java.util.Arrays;
import de.heinerkuecker.util.TestFailedException;
/**
* Diese experimentelle Klasse
* enthält ein Set von short-Werten
* (Primitiven) welches als
* Trie oder sogenannter
* Patricia-Baum aufgebaut ist.
*
* Dabei wird für jedes Bit
* der zu vermekenden short-Werte
* ein 2-stelliges boolean-Array
* angelegt.
*
* Begonnen wird mit dem
* niederwertigsten Bit.
*
* Je nach dem, ob das
* betrachtete Bit 0 oder
* 1 ist, wird im jeweiligen
* linken oder rechten
* Sub-Array weitergesucht.
*
* Ist das nächste Sub-Array
* null, so sind alle Werte
* ab diesem Bit nicht vorhanden.
*
* Wird das letzte Array erreicht,
* so entscheidet der Zustand
* des Boolean-Merkers, ob
* der entsprechende short-Wert
* vermerkt ist oder nicht.
*
* TODO statt Arrays mit je zwei Einträgen mal mit Arrays mit 4, 8 oder 16
Einträgen testen
*
* @author Heiner Kücker
*/
public class ShortTrieSet
{
public static final int BIT_COUNT = 16;
private Object[] trieArr =
new Object[ 2 ];
private int size;
/**
* Constructor
*/
public ShortTrieSet()
{
super();
}
/**
* Constructor
*/
public ShortTrieSet(
final short[] pShrtArr )
{
super();
addAll( pShrtArr );
}
/**
* @param pShrtArr
*/
public void addAll(
final short[] pShrtArr )
{
for (int i = 0; i < pShrtArr.length; i++ )
{
add( pShrtArr[ i ] );
}
}
/**
* Zurückgeben der Anzahl vermerkter Werte
* @return Anzahl vermerkter Werte
* @see java.util.Set#size()
*/
public int size()
{
return this.size;
}
/**
* Alle vermerkten
* Werte löschen.
*/
public void clear()
{
this.size = 0;
this.trieArr[ 0 ] = null;
this.trieArr[ 1 ] = null;
}
/**
* Vermerken des übergebenen
* short-Wertes.
*
* @param pValue zu vermerkender Wert
* @return <tt>true</tt> if this set did not already contain the specified
* element.
* @see java.util.Set#add(E)
*/
public boolean add(
final short pValue )
{
Object[] runArr =
this.trieArr;
short bitMask = 1;
// TODO umstellen auf abwärts zählen, weil Test auf 0 schneller sein
soll
for (int i = 0; i < BIT_COUNT - 2; i++ )
{
//System.out.println( "bitMask: " + bitMask );
final boolean isBit =
( pValue & bitMask ) != 0;
final Object[] preRunArr =
runArr;
if ( isBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
runArr = (Object[]) runArr[ 1 ];
if ( runArr == null )
{
runArr =
new Object[ 2 ];
preRunArr[ 1 ] =
runArr;
}
}
else
{
runArr = (Object[]) runArr[ 0 ];
if ( runArr == null )
{
runArr =
new Object[ 2 ];
preRunArr[ 0 ] =
runArr;
}
}
bitMask = (short) ( bitMask << 1 );
}
final boolean isPreLastBit =
( pValue & bitMask ) != 0;
boolean[] finalArr;
if ( isPreLastBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
finalArr = (boolean[]) runArr[ 1 ];
if ( finalArr == null )
{
finalArr =
new boolean[ 2 ];
runArr[ 1 ] =
finalArr;
}
}
else
{
finalArr = (boolean[]) runArr[ 0 ];
if ( finalArr == null )
{
finalArr =
new boolean[ 2 ];
runArr[ 0 ] =
finalArr;
}
}
bitMask = (short) ( bitMask << 1 );
final boolean isLastBit =
( pValue & bitMask ) != 0;
final boolean isValueNotAlreadyContain;
if ( isLastBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
isValueNotAlreadyContain =
!finalArr[ 1 ];
finalArr[ 1 ] = true;
}
else
{
isValueNotAlreadyContain =
! finalArr[ 0 ];
finalArr[ 0 ] = true;
}
if ( isValueNotAlreadyContain )
{
this.size++;
}
return isValueNotAlreadyContain;
}
/**
* Prüfen, ob der übergebene
* short-Wert in diesem Set enthalten ist.
*
* @param pValue zu prüfender Wert
* @return <tt>true</tt> if this set contains the specified element.
* @see java.util.Set#contains(java.lang.Object)
*/
public boolean contains(
final short pValue )
{
Object[] runArr =
this.trieArr;
short bitMask = 1;
// TODO umstellen auf abwärts zählen, weil Test auf 0 schneller sein
soll
for (int i = 0; i < BIT_COUNT - 2; i++ )
{
//System.out.println( "bitMask: " + bitMask );
final boolean isBit =
( pValue & bitMask ) != 0;
// final Object[] preRunArr =
// runArr;
if ( isBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
runArr = (Object[]) runArr[ 1 ];
if ( runArr == null )
{
return false;
}
}
else
{
runArr = (Object[]) runArr[ 0 ];
if ( runArr == null )
{
return false;
}
}
bitMask = (short) ( bitMask << 1 );
}
final boolean isPreLastBit =
( pValue & bitMask ) != 0;
boolean[] finalArr;
if ( isPreLastBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
finalArr = (boolean[]) runArr[ 1 ];
if ( finalArr == null )
{
return false;
}
}
else
{
finalArr = (boolean[]) runArr[ 0 ];
if ( finalArr == null )
{
return false;
}
}
bitMask = (short) ( bitMask << 1 );
final boolean isLastBit =
( pValue & bitMask ) != 0;
final boolean isValueContain;
if ( isLastBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
isValueContain =
finalArr[ 1 ];
}
else
{
isValueContain =
finalArr[ 0 ];
}
return isValueContain;
}
/**
* Entfernen des übergebenen
* short-Wertes.
*
* @param pValue zu entfernender Wert
* @return true if the set contained the specified element.
* @see java.util.Set#remove(java.lang.Object)
*/
public boolean remove(
final short pValue )
{
Object[] runArr =
this.trieArr;
short bitMask = 1;
final PathElem[] pathArr =
new PathElem[ BIT_COUNT - 2 ];
// TODO umstellen auf abwärts zählen, weil Test auf 0 schneller sein
soll
for (int i = 0; i < BIT_COUNT - 2; i++ )
{
//System.out.println( "bitMask: " + bitMask );
final boolean isBit =
( pValue & bitMask ) != 0;
if ( i > 0 )
{
pathArr[ i ] =
new PathElem(
// Achtung es ist wichtig, dass das gleiche
// Array referenziert wird und keine Kopie/Clone
runArr,
isBit ? 1 : 0 );
}
// final Object[] preRunArr =
// runArr;
if ( isBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
runArr = (Object[]) runArr[ 1 ];
if ( runArr == null )
{
return false;
}
}
else
{
runArr = (Object[]) runArr[ 0 ];
if ( runArr == null )
{
return false;
}
}
bitMask = (short) ( bitMask << 1 );
}
final boolean isPreLastBit =
( pValue & bitMask ) != 0;
boolean[] finalArr;
if ( isPreLastBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
finalArr = (boolean[]) runArr[ 1 ];
if ( finalArr == null )
{
return false;
}
}
else
{
finalArr = (boolean[]) runArr[ 0 ];
if ( finalArr == null )
{
return false;
}
}
bitMask = (short) ( bitMask << 1 );
final boolean isLastBit =
( pValue & bitMask ) != 0;
final boolean isValuePreviousContain;
if ( isLastBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
isValuePreviousContain =
finalArr[ 1 ];
finalArr[ 1 ] = false;
if ( finalArr[ 0 ] == false )
// beide Einträge sind false, Array kann gelöscht werden
{
runArr[ isPreLastBit ? 1 : 0 ] = null;
}
}
else
{
isValuePreviousContain =
finalArr[ 0 ];
finalArr[ 0 ] = false;
if ( finalArr[ 1 ] == false )
// beide Einträge sind false, Array kann gelöscht werden
{
runArr[ isPreLastBit ? 1 : 0 ] = null;
}
}
if ( isValuePreviousContain )
{
this.size--;
/*
* nicht benutzte Knoten Löschen um Speicher freizugeben
*/
for ( int i = pathArr.length - 1 ; i > 0 ; i-- )
{
final PathElem pathElem =
pathArr[ i ];
final Object[] pathTrieArr =
pathElem.trieArr;
final Object[] subPathTrieArr =
(Object[]) pathTrieArr[
pathElem.trieArrIndex ];
if ( subPathTrieArr[ 0 ] == null && subPathTrieArr[ 1 ] == null )
// das aktuelle Pfad Element ist leer und kann gelöscht werden
{
// final PathElem parentPathElem =
// pathArr[ i - 1 ];
//
// parentPathElem.trieArr[
// parentPathElem.trieArrIndex ]
// = null;
// break;
pathTrieArr[ pathElem.trieArrIndex ] = null;
}
}
}
return isValuePreviousContain;
}
/**
* Zurückgeben aller enthaltenen
* Werte als Objekt-Array.
* @return Array mit allen enthaltenen Werten als Objekte
*/
public Short[] toObjArray()
{
final short[] shortPrmvArr =
toArray();
final Short[] retArr =
new Short[ shortPrmvArr.length ];
for (int i = 0; i < shortPrmvArr.length; i++ )
{
final short s = shortPrmvArr[i];
retArr[ i ] =
new Short( s );
}
return retArr;
}
/**
* Zurückgeben aller enthaltenen
* Werte als Array.
* @return Array mit allen enthaltenen Werten
*/
public short[] toArray()
{
final ShortArrAndIndexVo vo =
new ShortArrAndIndexVo(
this.size );
innerToArray(
vo ,
this.trieArr ,
0 ,
0 );
final short[] retArr =
vo.shortArr;
Arrays.sort( retArr );
return retArr;
}
/**
* @param pVo Value-Objekt zum Sammeln der Werte
* @param pTrieArrNode aktueller zu prüfender Knoten
* @param pBitPos Position des aktuell bearbeiteten Bits
* @param pPreValue bisheriger Wert, der an der aktuellen bit-Position um
1 oder 0 erhöht werden muss
*/
private void innerToArray(
final ShortArrAndIndexVo pVo ,
final Object[] pTrieArrNode ,
final int pBitPos ,
final int pPreValue )
{
if ( pTrieArrNode == null )
// Pfad endet hier
{
return;
}
if ( pBitPos < BIT_COUNT - 2 )
// finales Merker-Array noch nicht erreicht
{
innerToArray(
pVo ,
(Object[]) pTrieArrNode[ 0 ] ,
pBitPos + 1 ,
pPreValue /* + 0 */ );
innerToArray(
pVo ,
(Object[]) pTrieArrNode[ 1 ] ,
pBitPos + 1 ,
pPreValue + (int) Math.pow( 2 , ( pBitPos ) ) );
}
else
// finales Merker-Array erreicht
{
{
final boolean[] finalArr0 =
(boolean[]) pTrieArrNode[ 0 ];
if ( finalArr0 != null )
{
final int preValue =
pPreValue + 0;
if ( finalArr0[ 0 ] )
{
pVo.add(
(short) preValue );
}
if ( finalArr0[ 1 ] )
{
pVo.add(
(short) (
preValue +
Math.pow( 2 , ( BIT_COUNT - 1 ) ) ) );
}
}
}
{
final boolean[] finalArr1 =
(boolean[]) pTrieArrNode[ 1 ];
if ( finalArr1 != null )
{
final int preValue =
pPreValue +
(int) Math.pow( 2 , ( BIT_COUNT - 2 ) );
if ( finalArr1[ 0 ] )
{
pVo.add(
(short) preValue );
}
if ( finalArr1[ 1 ] )
{
pVo.add(
(short) (
preValue +
Math.pow( 2 , BIT_COUNT - 1 ) ) );
}
}
}
}
}
/**
* Value-Objekt mit einem
* short-Array und einem
* Index.
*/
static final class ShortArrAndIndexVo
{
/**
* Array zum Sammeln der Werte
*/
final short[] shortArr;
/**
* aktueller Index
*/
int index;
/**
* Constructor
* @param pSize
*/
public ShortArrAndIndexVo(
final int pSize )
{
super();
this.shortArr =
new short[ pSize ];
}
/**
* Set value at index position
* and increment index.
* @param pValue
*/
public void add(
final short pValue )
{
this.shortArr[ this.index ] =
pValue;
this.index++;
}
}
/**
* Hilfsklasse für ein Element
* des Pfades zu einem Eintrag
* in einem {@link ShortTrieSet}.
*
* Wird benutzt in
* {@link ShortTrieSet#remove(short)}
*/
static final class PathElem
{
/**
* Sub-Array des Pfades
* innerhalb des Baumes
*/
final Object[] trieArr;
/**
* Index zum nächsten
* hierarchisch tiefergelegenen
* Sub-Array des Pfades
*/
final int trieArrIndex;
/**
* Constructor
* @param pTrieArr
* @param pTrieArrIndex
*/
public PathElem(Object[] pTrieArr, int pTrieArrIndex)
{
super();
// TODO Auto-generated constructor stub
this.trieArr = pTrieArr;
this.trieArrIndex = pTrieArrIndex;
}
/**
* debug output
* @see java.lang.Object#toString()
*/
@Override
public String toString()
{
return
"trieArr: " + Arrays.asList( this.trieArr ) +
"trieArrIndex: " + this.trieArrIndex;
}
}
/**
* @param args
*/
public static void main(
String[] args )
{
final ShortTrieSet set = new ShortTrieSet();
/*
* add 1
*/
boolean valPrvContain = ! set.add( (short) 1 );
if ( valPrvContain || set.size() != 1 )
{
throw new TestFailedException();
}
if ( set.contains( (short) 0 ) )
{
throw new TestFailedException();
}
if ( ! set.contains( (short) 1 ) )
{
throw new TestFailedException();
}
String setStr = Arrays.asList( set.toObjArray() ).toString();
System.out.println( setStr );
if ( ! setStr.equals( "[1]" ) )
{
throw new TestFailedException();
}
/*
* add 2
*/
valPrvContain = ! set.add( (short) 2 );
if ( valPrvContain || set.size() != 2 )
{
throw new TestFailedException();
}
if ( set.contains( (short) 0 ) )
{
throw new TestFailedException();
}
if ( ! set.contains( (short) 1 ) )
{
throw new TestFailedException();
}
if ( ! set.contains( (short) 2 ) )
{
throw new TestFailedException();
}
setStr = Arrays.asList( set.toObjArray() ).toString();
System.out.println( setStr );
if ( ! setStr.equals( "[1, 2]" ) )
{
throw new TestFailedException();
}
/*
* remove 1
*/
valPrvContain = set.remove( (short) 1 );
if ( ( ! valPrvContain ) || set.size() != 1 )
{
throw new TestFailedException();
}
if ( set.contains( (short) 0 ) )
{
throw new TestFailedException();
}
if ( set.contains( (short) 1 ) )
{
throw new TestFailedException();
}
if ( ! set.contains( (short) 2 ) )
{
throw new TestFailedException();
}
setStr = Arrays.asList( set.toObjArray() ).toString();
System.out.println( setStr );
if ( ! setStr.equals( "[2]" ) )
{
throw new TestFailedException();
}
/*
* remove 2
*/
valPrvContain = set.remove( (short) 2 );
if ( ( ! valPrvContain ) || set.size() != 0 )
{
throw new TestFailedException();
}
if ( set.contains( (short) 0 ) )
{
throw new TestFailedException();
}
if ( set.contains( (short) 1 ) )
{
throw new TestFailedException();
}
if ( set.contains( (short) 2 ) )
{
throw new TestFailedException();
}
setStr = Arrays.asList( set.toObjArray() ).toString();
System.out.println( setStr );
if ( ! setStr.equals( "[]" ) )
{
throw new TestFailedException();
}
}
}
--
Heiner Kücker
www.heinerkuecker.de
www.control-and-command.de
Heiner Kücker
2007-11-03 10:40:01 UTC
Permalink
Ralf Ullrich schriebPost by Ralf Ullrich
Post by Heiner Kücker
Also das Standard-Java-API ist gar nicht so
Geschwindigkeit auch noch die Stabilität (=Beibehaltung der
Und wie funktioniert Dei Algorithmus ?
Post by Ralf Ullrich
public static class Hashed implements UniqueIntArrayFunction {
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
Post by Ralf Ullrich
public int[] unique(int[] a) {
int cap = 4 * a.length / 3;
Post by Ralf Ullrich
int z = 3;
while (z < cap) {
z =2*z+ 1;
}
Post by Ralf Ullrich
int[] rv = new int[a.length];
Post by Ralf Ullrich
boolean didzero = false;
int[] c = new int[z+1];
Post by Ralf Ullrich
int n = 0;
for (int v : a) {
if (v == 0) {
if (!didzero) {
didzero = true;
n++;
}
Funktioniert der Algorithmus mit Werten kleiner 0 ?
Post by Ralf Ullrich
} else {
int h = hash(v) & z;
Post by Ralf Ullrich
while (true) {
int x = c[h];
if (x == 0) {
c[h] = rv[n++] = v;
break;
}
Post by Ralf Ullrich
if (x == v) {
break;
}
Post by Ralf Ullrich
h = (h + 1) & z;
Post by Ralf Ullrich
}
}
}
return Arrays.copyOf(rv, n);
Post by Ralf Ullrich
}
}
Heiner
Ralf Ullrich
2007-11-03 10:59:15 UTC
Permalink
Post by Heiner Kücker
Ralf Ullrich schrieb
Post by Ralf Ullrich
Post by Heiner Kücker
Also das Standard-Java-API ist gar nicht so
Geschwindigkeit auch noch die Stabilität (=Beibehaltung der
Und wie funktioniert Dei Algorithmus ?
Ist im Prinzip ein IntHashSet und realisiert die Geschwindigkeitsgewinne,
die Trove verpricht, aber nicht liefert.
Post by Heiner Kücker
Post by Ralf Ullrich
public static class Hashed implements UniqueIntArrayFunction {
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
Post by Ralf Ullrich
public int[] unique(int[] a) {
int cap = 4 * a.length / 3;
cap = (Mindest-)Kapazität des Hashs. Im Hash sollten wenigstens 25% der
Plätze frei bleiben. Da ich maximal a.length verschiedene Werte haben
kann, ist dies garantiert, wenn der Hash eine Größe von 4*a.length/3 hat.
Post by Heiner Kücker
Post by Ralf Ullrich
int z = 3;
while (z < cap) {
z =2*z+ 1;
}
z = tatsächliche Hashgröße - 1. Die tatsächliche Hashgröße muss eine
Zweierpotenz sein und größer oder gleich der Mindest-Kapazität aus dem
vorigen Schritt.
Post by Heiner Kücker
Post by Ralf Ullrich
int[] rv = new int[a.length];
Post by Ralf Ullrich
boolean didzero = false;
int[] c = new int[z+1];
Das ist der 'IntHashSet'.
Post by Heiner Kücker
Post by Ralf Ullrich
int n = 0;
for (int v : a) {
if (v == 0) {
if (!didzero) {
didzero = true;
n++;
}
Funktioniert der Algorithmus mit Werten kleiner 0 ?
Ja. Alle int-Werte sind erlaubt.
Die Funktion, so wie sie dasteht würde aber für ein a.length irgendwo
oberhalb von (Integer.MAX_VALUE/8)*3 anderweitig versagen. Der Fall kann
aber praktisch nur auf 64Bit-VMs eintreten, denn 32Bit-VMs geht vorher der
Speicher aus.
Post by Heiner Kücker
Post by Ralf Ullrich
} else {
int h = hash(v) & z;
entspricht: h = ((hash(v) % c.length) + c.length) % c.length;
Post by Heiner Kücker
Post by Ralf Ullrich
while (true) {
int x = c[h];
if (x == 0) {
c[h] = rv[n++] = v;
break;
}
Ist der Platz h im Hash noch unbesetzt? Ja, dann mit dem aktuellen Wert v
besetzen und v in den Rückgabevektor schreiben. Weiter mit dem nächsten
Wert aus a.
Post by Heiner Kücker
Post by Ralf Ullrich
if (x == v) {
break;
}
Post by Ralf Ullrich
h = (h + 1) & z;
Wenn der Platz h schon (für einen anderen Wert) vergeben ist (also eine
Kollision eingetreten ist), dann versuche es mit dem nächsten Platz. Die
Und-Verknüpfung entspricht wieder einem Modulo auf die Zweierpotenz:
h = (h+1) % c.length;
Post by Heiner Kücker
Post by Ralf Ullrich
}
}
}
return Arrays.copyOf(rv, n);
Post by Ralf Ullrich
}
}
Heiner
HTH
cu
Ralf Ullrich
2007-11-03 18:07:57 UTC
Permalink
Post by Holger Hoffstaette
Post by Ralf Ullrich
Ist im Prinzip ein IntHashSet und realisiert die Geschwindigkeitsgewinne,
die Trove verpricht, aber nicht liefert.
(//fastutil.dsi.unimi.it/) mit IntSet oder IntSortedSet laufen
lassen und den Vegleich posten?
Aber nur weil ich gerade in guter Stimmung bin ;-).
public static class Fstutl implements UniqueIntArrayFunction {
@Override
public int[] unique(int[] a) {
return new IntOpenHashSet(a).toIntArray();
}
}
Schneidet deutlich besser als Trove ab, aber meine »Hashed«-Lösung mit dem
integrierten 'IntHashSet' ist immer noch stets zwei- bis dreimal so schnell.
Sorry wegen der langen Zeilen, aber diese tabellarische Darstellung ist
IMHO doch noch die bestmögliche.
cu
### Example 0,486s OK Simple 1,148s OK HKImpl 0,236s OK Hashed 0,697s OK Fstutl 1,249s OK Trove
### 1/15 0,493s OK Simple 1,151s OK HKImpl 0,213s OK Hashed 0,834s OK Fstutl 1,407s OK Trove
### 2/15 0,578s OK Simple 1,223s OK HKImpl 0,276s OK Hashed 0,863s OK Fstutl 1,714s OK Trove
### 5/15 0,883s OK Simple 1,406s OK HKImpl 0,280s OK Hashed 0,940s OK Fstutl 2,053s OK Trove
### 10/15 0,832s OK Simple 1,691s OK HKImpl 0,340s OK Hashed 1,047s OK Fstutl 2,191s OK Trove
### 15/15 0,861s OK Simple 1,836s OK HKImpl 0,345s OK Hashed 1,110s OK Fstutl 2,180s OK Trove
### 1/150 0,215s OK Simple 0,829s OK HKImpl 0,197s OK Hashed 0,663s OK Fstutl 0,866s OK Trove
### 10/150 0,708s OK Simple 0,891s OK HKImpl 0,267s OK Hashed 0,688s OK Fstutl 0,893s OK Trove
### 50/150 1,152s OK Simple 1,177s OK HKImpl 0,344s OK Hashed 0,823s OK Fstutl 0,980s OK Trove
### 100/150 1,255s OK Simple 1,397s OK HKImpl 0,376s OK Hashed 0,934s OK Fstutl 1,069s OK Trove
### 150/150 1,370s OK Simple 1,591s OK HKImpl 0,381s OK Hashed 1,042s OK Fstutl 1,149s OK Trove
### 10/1500 0,670s OK Simple 0,882s OK HKImpl 0,297s OK Hashed 0,638s OK Fstutl 0,808s OK Trove
### 100/1500 1,159s OK Simple 0,954s OK HKImpl 0,304s OK Hashed 0,658s OK Fstutl 0,839s OK Trove
### 500/1500 1,673s OK Simple 1,386s OK HKImpl 0,358s OK Hashed 0,789s OK Fstutl 0,950s OK Trove
### 1000/1500 1,805s OK Simple 1,674s OK HKImpl 0,395s OK Hashed 0,899s OK Fstutl 1,027s OK Trove
### 1500/1500 1,879s OK Simple 1,860s OK HKImpl 0,425s OK Hashed 0,985s OK Fstutl 1,076s OK Trove
### 100/15000 1,086s OK Simple 0,868s OK HKImpl 0,271s OK Hashed 0,633s OK Fstutl 0,807s OK Trove
### 1000/15000 1,704s OK Simple 1,184s OK HKImpl 0,283s OK Hashed 0,665s OK Fstutl 0,867s OK Trove
### 5000/15000 2,218s OK Simple 1,828s OK HKImpl 0,342s OK Hashed 0,815s OK Fstutl 1,001s OK Trove
### 10000/15000 2,373s OK Simple 2,232s OK HKImpl 0,388s OK Hashed 0,924s OK Fstutl 1,084s OK Trove
### 15000/15000 2,386s OK Simple 2,439s OK HKImpl 0,408s OK Hashed 1,011s OK Fstutl 1,118s OK Trove
Stefan Ram
2007-11-03 13:01:26 UTC
Permalink
Post by Ralf Ullrich
Nicht im Rennen, weil keine allgemeine Lösung, sondern nur für
(Es mag sein, daß es eine Java-Implementation geben könnte,
die nicht hierfür ausreichend Speicher addressieren will.
Dies ist aber keine Einschränkung der Programmiersprache Java.)
Eine andere Variante, die beliebig große int-Werte
akzeptieren können soll:
public class Main
{
public static int[] uniq( final int[] values )
{ final boolean[] saw = new boolean[ 65536 ];
final java.util.HashMap<java.lang.Integer,java.lang.Boolean> map
= new java.util.HashMap<java.lang.Integer,java.lang.Boolean>();
final int[] result = new int[ values.length + 1 ];
int top = 0;
for( final int value : values )
{ if( value < 32768 && value > -32768 )
{ if( !saw[ value + 32768 ] )
{ saw[ value + 32768 ]= true;
result[ top++ ]= value; }}
else
{ if( !map.containsKey( value ))
{ map.put( value, java.lang.Boolean.TRUE );
result[ top++ ]= value; }}}
return java.util.Arrays.copyOf( result, top ); }
public static void main( java.lang.String[] args )
{ final int[] result = uniq( new int[]{ 1, 2, 3, 4, 5, 5, 5, 6, 7 });
for( int i = 0; i < result.length; ++i )
java.lang.System.out.println( result[ i ]); }}
1
2
3
4
5
6
7
Die Kopie der Reihung am Ende der Methode »uniq« kann man sich
ersparen, wenn man es akzeptiert, daß »top« (die Begrenzung der
Reihung) noch zusätzlich zur Ergebnisreihung übergeben wird.
Stefan Ram
2007-11-03 13:09:19 UTC
Permalink
Post by Ralf Ullrich
Nicht im Rennen, weil keine allgemeine Lösung, sondern nur für
(Es mag sein, daß es eine Java-Implementation geben könnte,
die nicht hierfür ausreichend Speicher addressieren will.
Dies ist aber keine Einschränkung der Programmiersprache Java.)
Eine andere Variante, die beliebig große int-Werte
akzeptieren können soll:
public class Main
{
public static int[] uniq( final int[] values )
{ final boolean[] saw = new boolean[ 65536 ];
final java.util.HashMap<java.lang.Integer,java.lang.Boolean> map
= new java.util.HashMap<java.lang.Integer,java.lang.Boolean>();
final int[] result = new int[ values.length ];
int top = 0;
for( final int value : values )
{ if( value < 32768 && value > -32768 )
{ if( !saw[ value + 32768 ] )
{ saw[ value + 32768 ]= true;
result[ top++ ]= value; }}
else
{ if( !map.containsKey( value ))
{ map.put( value, java.lang.Boolean.TRUE );
result[ top++ ]= value; }}}
return java.util.Arrays.copyOf( result, top ); }
public static void main( java.lang.String[] args )
{ final int[] result = uniq( new int[]{ 1, 2, 3, 4, 5, 5, 5, 6, 7 });
for( int i = 0; i < result.length; ++i )
java.lang.System.out.println( result[ i ]); }}
1
2
3
4
5
6
7
Die Kopie der Reihung am Ende der Methode »uniq« kann man sich
ersparen, wenn man es akzeptiert, daß »top« (die Begrenzung der
Reihung) noch zusätzlich zur Ergebnisreihung übergeben wird.
Supersedes: <doppelte-***@ram.dialup.fu-berlin.de>
Ralf Ullrich
2007-11-04 17:01:06 UTC
Permalink
Geht es nach der reinen Laufzeit, so ergibt sich bei mir diese Rangfolge1. Platz: »Hashed« Lösung mit integriertem Minimal-HashSet.
Wobei zwischen 1. und 2. Platz mehrere Pferdelängen liegen, während 2., 3.
und 4. Platz nur Nasenspitzen auseinander liegen.
Die untenstehende neue Lösung ist also nur marginal schneller als die
beiden Standard-API-Lösungen, dennoch bietet sie einen in manchen
Situationen entscheidenden Vorteil. Welchen?* (Und wie funktioniert sie
überhaupt?)
cu
*) Diesen Vorteil hat sie übrigens auch gegenüber den Lösungen mit den
3rd-Party-Libs.
public static int[] unique(int[] a) {
int[] c = a.clone();
if (c.length <= 1) {
return c;
}
int n = split(c, 0, c.length, 1, 0);
return Arrays.copyOf(c, n);
}
private static int split(int[] c, int s, int e, int b, int p) {
int m = s;
int a0 = -1;
int o0 = 0;
int a1 = -1;
int o1 = 0;
for (int i = s; i < e; i++) {
int v = c[i];
if ((v & b) == 0) {
a0 &= v;
o0 |= v;
c[i] = c[m];
c[m++] = v;
} else {
a1 &= v;
o1 |= v;
}
}
a0 ^= o0;
if ((a0 &= -a0) == 0) {
c[p++] = c[s];
} else if (s < m) {
p = split(c, s, m, a0 & (-a0), p);
}
a1 ^= o1;
if ((a1 &= -a1) == 0) {
c[p++] = c[m];
} else if (m < e) {
p = split(c, m, e, a1 & (-a1), p);
}
return p;
}
}