Doppelte Elemente aus einem Array effektiv entfernen

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?
Christian

Sortieren und Element n mit n+1 vergleichen, alternativ ein Set nehmen...

Grüße
Bernd

Heiner Kücker

2007-10-31 17:15:49 UTC

Christian Schmelzer schrieb

Du kannst die int-Werte in Integer-Objekte
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).

--
Heiner Kücker
www.heinerkuecker.de
www.control-and-command.de

Christian Schmelzer

2007-10-31 17:55:29 UTC

Post by Heiner Kücker
Christian Schmelzer schrieb

Du kannst die int-Werte in Integer-Objekte
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.

Christian

Stefan Kuhne

2007-10-31 18:24:10 UTC

Post by Heiner Kücker
Christian Schmelzer schrieb

Du kannst die int-Werte in Integer-Objekte
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).

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.

Brauchst Du unbedingt das Array?
Es gibt Datentypen mit contains, oder du schreibst sie Dir selber.

Stefan Kuhne

Heiner Kücker

2007-10-31 19:12:45 UTC

Christian Schmelzer schrieb

Post by Heiner Kücker
Christian Schmelzer schrieb

Du kannst die int-Werte in Integer-Objekte
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
* 
* @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
* 
* @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.
* 
* @param m The map whose mappings are to be placed in this map. Throws:
* 
* @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.
* 
* @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
* 
* @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.
* 
* @return The current capacity for this hash map.
*/

public int getCapacity() {
return capacity;
}

/**
* Return the load factor of the instance.
* 
* @return The load factor for this hash map.
*/

public float getLoadFactor() {
return loadFactor;
}

/**
* Return the keys in the hash map
* 
* @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>).
* 
* @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.
* 
* @param key The key with which the specified value is to be associated.
* @param value The value to be associated with the specified key.
* 
* @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.
* 
* @param key The key whose associated value is to be returned.
* 
* @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.
* 
* @param key The key whose presence in this map is to be tested.
* 
* @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.
* 
* @param key The key whose mapping is to be removed from the map.
* 
* @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.
* 
* @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
* 
* @return The value for the <code>key</code> property
*/

public int getKey() {
return key;
}

/**
* Setter method for <code>value</code> property
* 
* @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
* 
* @return The value for the <code>value</code> property
*/
// public Object getValue() {
// return value;
// }

/**
* Setter method for <code>next</code> property
* 
* @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
* 
* @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

Heiner Kücker

2007-10-31 19:15:13 UTC

Christian Schmelzer schrieb

Post by Heiner Kücker
Christian Schmelzer schrieb

Du kannst die int-Werte in Integer-Objekte
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.

Oder so:

http://commons.apache.org/primitives/

--
Heiner Kücker
www.heinerkuecker.de
www.control-and-command.de

Heiner Kücker

2007-10-31 19:20:31 UTC

Heiner Kücker schrieb

Post by Heiner Kücker
http://commons.apache.org/primitives/

Mann, da ist gar kein Set dabei.
Da habe ich mich geirrt.

Post by Heiner Kücker
--
Heiner Kücker
www.heinerkuecker.de
www.control-and-command.de

Wanja Gayk

2007-11-01 13:45:59 UTC

Christian Schmelzer said...

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.

Das einzig uneffiziente daran ist das Wrappen von int in Integer und 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.

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-

[*] http://trove4j.sourceforge.net/
Siehe: TIntHashSet in http://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

Post by Wanja Gayk
Christian Schmelzer said...

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.

[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.

Hallo Wanja,
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

Bernd Eckenfels

2007-11-01 20:56:26 UTC

Post by Wanja Gayk
if(array.length==0){return array;}
if(array.length==1){return new int[]{array[0]};}

Du kannst auch if (array == null || array.length < 2) return array; machen,
aber es ist problematisch nicht immer eine Kopie zurückzugeben.

Gruss
Bernd

Wanja Gayk

2007-11-01 23:33:34 UTC

Bernd Eckenfels said...

Post by Bernd Eckenfels

Post by Wanja Gayk
if(array.length==0){return array;}
if(array.length==1){return new int[]{array[0]};}

Du kannst auch if (array == null || array.length < 2) return array; machen,
aber es ist problematisch nicht immer eine Kopie zurückzugeben.

dann doch eher:
if(array==null || array.length==0){return array;}
if(array.length==1){return new int[]{array[0]};}

Grund:
Ich gebe bei array.length>1 ein neues Array zurück und das sollte die
Methode dann auch in jedem Fall tun, in dem das Array verändert werden
kann, sonst kommt man in Teufels Küche. Mal ein sinnloses, konstruiertes
Beispiel:

replaceAll(original, magicNumber, 0); //ensures no magicNumber in array
int[] result = withoutDupes(original);
original[0]=magicNumber; //magicNumber must be at first index.
doSomething(original); //expects magicNumber at first index.
assert result[0] != magicNumber : "BOOM!";
doSomethingElse(result);

Wenn withoutDupes das Original zurück gäbe, statt einer Kopie, dann
würde es kallen, wenn original.length == 1 ist, sonst aber
funktionieren. Ich denke das ist nicht so gut.

Gruß,
-Wanja-

Stefan Ram

2007-10-31 23:30:07 UTC

Post by Christian Schmelzer
effektiv

Du meinst wahrscheinlich »laufzeiteffizient«.

Wenn man den Wertebereich etwas eingrenzen kann:

public class Main
{ public static void main( java.lang.String[] args )
{ final boolean[] seen = new boolean[ 8 ];
final int[] values = new int[]{ 1, 2, 3, 4, 5, 5, 5, 6, 7 };
final int[] result = new int[ values.length ];
int top = 0;

for( int value : values )if( !seen[ value ])
{ result[ top++ ]= value; seen[ value ]= true; }

for( int i = 0; i < top; ++i )
java.lang.System.out.println( result[ i ]); }}

Wenn alle int-Werte vorkommen können, kann man auch zwei
boolean-Reihungen oder (um Speicher zu sparen) zwei
java.util.BitSet-Objekte statt »seen« nehmen.

Sven Köhler

2007-11-01 02:41:56 UTC

Post by Christian Schmelzer
Die Sortierung ist unwichtig. Bis jetzt sind mir nur nicht gerade effektive
Wege eingefallen. Hat jemand eine gute Idee?

Welche Wege sind dir denn eingefallen?

Also wenn man Zahlen sortiert, ist es ja ein leichtes, doppelte
herauszufiltern - denn die Duplikate stehen direkt hintereinander.
Sortieren hat Laufzeit O(n log(n)) und das rausfiltern der Duplikate hat
Laufzeit O(n) - insgesamt macht das Also Laufzeit O(n log(n)).

Was ist mit dem Wertebereich der Zahlen. Ist dieser beschränkt? Weil
dann könntest du sowas wie BucketSort machen. Also wenn z.B. nur Zahlen
zwischen 1 und 10 erlaubt sind, gehst du über die Eingabe drüber und
speicherst in 10 boolean variablen, welche Zahlen du schon gesehen hast.
Und dann kannste die Duplikate auch ganz einfach rausfiltern.
Das ganze hat lineare Laufzeit O(n).

Grüße,
Sven

Achim Peters

2007-11-01 09:28:57 UTC

Post by Christian Schmelzer
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?

Merke Dir die ints von vorneherein nicht in einem Array, sondern in
einem Set. Ansonsten wandele sie in eines um. Ab Java 1.5:
int[] test = new int[] {1, 2, 3, 4, 5, 5, 5, 6, 7};

Set<Integer> set = new TreeSet<Integer>();

for (int i=0; i<test.length; i++)
set.add(test[i]);

for (int i: set)
System.out.println(i);

... finde ich sehr effektiv.

Bye
Achim

Sven Köhler

2007-11-01 14:45:01 UTC

Post by Achim Peters
... finde ich sehr effektiv.

Finde ich nicht. Das umwandeln in Integer-Objekte kostet unnötig Zeit.

Ich würde tippen, dass die "Sortieren und rausfiltern" mit einem Array
in etwa die hälfte der Zeit braucht - mindestens.

Ansonsten - wäre noch die Frage zu klären, ob man besser TreeSet oder
HashSet nehmen sollte.

Achim Peters

2007-11-01 18:21:55 UTC

Post by Achim Peters
... finde ich sehr effektiv.

Finde ich nicht.

Die Lösung spart aber sehr effektiv Programmzeilen.

Post by Sven Köhler
Das umwandeln in Integer-Objekte kostet unnötig Zeit.

Ich bezweifle, dass die Umwandlung in Integer-Objekte beim OP einen
relevanten Zeitnachteil mit sich bringt.

"Vorzeitige Optimierung ist die Wurzel allen Übels" sprach Knuth.

Bye
Achim

Wanja Gayk

2007-11-01 19:39:03 UTC

Sven Köhler said...

Post by Achim Peters
... finde ich sehr effektiv.

Finde ich nicht. Das umwandeln in Integer-Objekte kostet unnötig Zeit.
Ich würde tippen, dass die "Sortieren und rausfiltern" mit einem Array
in etwa die hälfte der Zeit braucht - mindestens.
Ansonsten - wäre noch die Frage zu klären, ob man besser TreeSet oder
HashSet nehmen sollte.

Warum sollte das TreeSet schneller sein? Bei kleinen Wertebereichen
vielleicht, aber sonst steht das Einfügen in O(log n) von TreeSet gegen
das O(1) des HashSet.

Gruß,
-Wanja-

Sven Köhler

2007-11-01 19:11:52 UTC

Post by Wanja Gayk

Post by Achim Peters
... finde ich sehr effektiv.

Finde ich nicht. Das umwandeln in Integer-Objekte kostet unnötig Zeit.
Ich würde tippen, dass die "Sortieren und rausfiltern" mit einem Array
in etwa die hälfte der Zeit braucht - mindestens.
Ansonsten - wäre noch die Frage zu klären, ob man besser TreeSet oder
HashSet nehmen sollte.

Warum sollte das TreeSet schneller sein? Bei kleinen Wertebereichen
vielleicht, aber sonst steht das Einfügen in O(log n) von TreeSet gegen
das O(1) des HashSet.

Ja, darauf habe ich angespielt.

Wobei man keinesfalls vergessen sollte, dass das O(1) die amortisierte
Laufzeit ist.

Wanja Gayk

2007-11-01 23:14:13 UTC

Sven Köhler said...

Post by Wanja Gayk

Post by Sven Köhler
Ansonsten - wäre noch die Frage zu klären, ob man besser TreeSet oder
HashSet nehmen sollte.

Warum sollte das TreeSet schneller sein? Bei kleinen Wertebereichen
vielleicht, aber sonst steht das Einfügen in O(log n) von TreeSet gegen
das O(1) des HashSet.

Ja, darauf habe ich angespielt.
Wobei man keinesfalls vergessen sollte, dass das O(1) die amortisierte
Laufzeit ist.

Ein wenig Overhead ist dabei, um den Hash zu berechnen, ein wenig
Overhead ist dabei, wenn die Hashtable zu viele Kollisionen hat,
richtig, aber das sollte in der Regel dennoch schneller sein als ne
TreeMap.

Gruß,
-Wanja-

Ralf Ullrich

2007-11-01 23:34:34 UTC

Post by Achim Peters
... finde ich sehr effektiv.

Finde ich nicht. Das umwandeln in Integer-Objekte kostet unnötig Zeit.
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

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.

"Begrenzte Wertebereiche" ist gut - ein einziger negativer Wert oder ein
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.

Dem kann man nur zustimmen.

Gruß,
-Wanja-

Sven Köhler

2007-11-02 01:21:56 UTC

Post by Ralf Ullrich
Messen nicht Tippen!
Ich dachte auch ein leicht modifizierter Heapsort sei die beste Lösung,

Tja dann!

Kannste vielleicht nochmal messen, mit dem HashSet von trove4j ?
Die haben ja auch so spezielle HashSets extra für ints - ohne
Wrapperobjekte und so.

Ralf Ullrich

2007-11-02 02:45:43 UTC

Post by Ralf Ullrich
Messen nicht Tippen!
Ich dachte auch ein leicht modifizierter Heapsort sei die beste Lösung,

Tja dann!
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.

Yep:

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

Heiner Kücker

2007-11-02 15:22:50 UTC

Ralf Ullrich schrieb

Post by Ralf Ullrich
PS: Hier eine komplette (aufgewärmte) Messreihe, wobei >Simple< die

Könntest Du mal den Main-Code für die Messung posten.

Ich wollte mal mit einen selbstgebastelten Trie-Set
(Patricia-Baum) nachmessen.

Ich melde mich, wenn ich den Code fertig habe.

--
Heiner Kücker
www.heinerkuecker.de
www.control-and-command.de

Ralf Ullrich

2007-11-02 19:01:44 UTC

Post by Heiner Kücker
Könntest Du mal den Main-Code für die Messung posten.

Bitteschön. (Nicht vergessen neueste Trove4J-Jar (äh 2.0.1?) in den
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

Ralf Ullrich schrieb

Post by Heiner Kücker
Könntest Du mal den Main-Code für die Messung posten.

Bitteschön. (Nicht vergessen neueste Trove4J-Jar (äh 2.0.1?) in den
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

Ralf Ullrich

2007-11-03 10:22:06 UTC

Post by Heiner Kücker
Also das Standard-Java-API ist gar nicht so

Yep. Mir ist es bislang auch nur hiermit gelungen, wobei hier zur
Geschwindigkeit auch noch die Stabilität (=Beibehaltung der
Eingabe-Reihenfolge) quasi als Bonus hinzukommt:

public static class Hashed implements UniqueIntArrayFunction {

static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}

public int[] unique(int[] a) {
int cap = 4 * a.length / 3;
int z = 3;
while (z < cap) {
z =2*z+ 1;
}
int[] rv = new int[a.length];
boolean didzero = false;
int[] c = new int[z+1];
int n = 0;
for (int v : a) {
if (v == 0) {
if (!didzero) {
didzero = true;
n++;
}
} else {
int h = hash(v) & z;
while (true) {
int x = c[h];
if (x == 0) {
c[h] = rv[n++] = v;
break;
}
if (x == v) {
break;
}
h = (h + 1) & z;
}
}
}
return Arrays.copyOf(rv, n);
}
}

Heiner Kücker

2007-11-03 10:40:01 UTC

Ralf Ullrich schrieb

Post by Heiner Kücker
Also das Standard-Java-API ist gar nicht so

Yep. Mir ist es bislang auch nur hiermit gelungen, wobei hier zur
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);
}

Ein Hash, ist klar.

Post by Ralf Ullrich
public int[] unique(int[] a) {
int cap = 4 * a.length / 3;

Wofür cap ?

Post by Ralf Ullrich
int z = 3;
while (z < cap) {
z =2*z+ 1;
}

Wofür z.

Post by Ralf Ullrich
int[] rv = new int[a.length];

Ein Ziel-Array mit der Grösse des Quell-Arrays.

Post by Ralf Ullrich
boolean didzero = false;
int[] c = new int[z+1];

Wofür ist das Array c ?

Post by Ralf Ullrich
int n = 0;
for (int v : a) {
if (v == 0) {
if (!didzero) {
didzero = true;
n++;
}

Null wird gesondert vermerkt, ist klar.
Funktioniert der Algorithmus mit Werten kleiner 0 ?

Post by Ralf Ullrich
} else {
int h = hash(v) & z;

Hash UND z , wofür ?

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

Wert war schon vorhanden, klar.

Post by Ralf Ullrich
h = (h + 1) & z;

???

Post by Ralf Ullrich
}
}
}
return Arrays.copyOf(rv, n);

Das Ergebnis, das verstehe ich.

Post by Ralf Ullrich
}
}

Grüsse
Heiner

Heiner Kücker

2007-11-03 10:54:34 UTC

Heiner Kücker schrieb

Post by Heiner Kücker
Ralf Ullrich schrieb

Post by Heiner Kücker
Also das Standard-Java-API ist gar nicht so

Yep. Mir ist es bislang auch nur hiermit gelungen, wobei hier zur
Geschwindigkeit auch noch die Stabilität (=Beibehaltung der

Ich hatte noch die Idee, dass man das Standard
java.util.HashSet (die intern eine HashMap verwendet)
oder die Variante von Dr. Matthias Laux so ändern könnte,
das in den Buckets anstatt der Entry-Objekte int-Arrays
mit schrittweiser Größenanpassung verwendet werden
könnten.

Dann spart man die Entry-Objekte.

Ein Null-Merker wie in Deiner Lösung wäre dann
auch notwendig, da die unbenutzten Array-Einträge
auf Null stehen.

--
Heiner Kücker
www.heinerkuecker.de
www.control-and-command.de

Ralf Ullrich

2007-11-03 10:59:15 UTC

Post by Heiner Kücker
Ralf Ullrich schrieb

Post by Heiner Kücker
Also das Standard-Java-API ist gar nicht so

Yep. Mir ist es bislang auch nur hiermit gelungen, wobei hier zur
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 Ralf Ullrich
public static class Hashed implements UniqueIntArrayFunction {
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}

Ein Hash, ist klar.

Post by Ralf Ullrich
public int[] unique(int[] a) {
int cap = 4 * a.length / 3;

Wofür cap ?

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 Ralf Ullrich
int z = 3;
while (z < cap) {
z =2*z+ 1;
}

Wofür z.

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 Ralf Ullrich
int[] rv = new int[a.length];

Ein Ziel-Array mit der Grösse des Quell-Arrays.

Post by Ralf Ullrich
boolean didzero = false;
int[] c = new int[z+1];

Wofür ist das Array c ?

Das ist der 'IntHashSet'.

Post by Ralf Ullrich
int n = 0;
for (int v : a) {
if (v == 0) {
if (!didzero) {
didzero = true;
n++;
}

Null wird gesondert vermerkt, ist klar.
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 Ralf Ullrich
} else {
int h = hash(v) & z;

Hash UND z , wofür ?

entspricht: h = ((hash(v) % c.length) + c.length) % c.length;

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 Ralf Ullrich
if (x == v) {
break;
}

Wert war schon vorhanden, klar.

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 Ralf Ullrich
}
}
}
return Arrays.copyOf(rv, n);

Das Ergebnis, das verstehe ich.

Post by Ralf Ullrich
}
}

Grüsse
Heiner

HTH

cu

Heiner Kücker

2007-11-03 11:09:42 UTC

Ralf Ullrich schrieb

Post by Heiner Kücker
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
if (x == v) {
break;
}

Wert war schon vorhanden, klar.

Post by Heiner Kücker
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
h = (h+1) % c.length;

Aha, also wenn alle Plätze für einen Hash belegt sind,
könnte es zu einem Fehler kommen.
Das schließt Du durch die 25 % Reserve-Platz aus.

Könnte man das nicht explizit
durch eine Obergrenze ausschließen ?

--
Heiner Kücker
www.heinerkuecker.de
www.control-and-command.de

Ralf Ullrich

2007-11-03 11:23:25 UTC

Post by Heiner Kücker
Aha, also wenn alle Plätze für einen Hash belegt sind,
könnte es zu einem Fehler kommen.
Das schließt Du durch die 25 % Reserve-Platz aus.

Nicht nur das. Die 25% sorgen auch dafür, dass seltener längeren Ketten
aufeinanderfolgender belegter Plätze entstehen, denn die Zeit fürs
Einfügen ist ja nur annähernd O(1). Eigentlich ist sie ja
O(durchschnittlicher Abstand zum nächsten freien Platz) und je mehr und
längere Ketten es gibt, umso größer wird dieser Wert (bis er folgerichtig
unendlich wird, wenn kein Platz mehr frei ist, in welchem Fall mein Code
auch tatsächlich in einer Endlosschleife landen würde). Je voller der Hash
wird, umso größer die Wahrscheinlichkeit, dass er entartet und nur noch
lineare Laufzeit O(n) bietet, was für die unique()-Funktion wiederum
quadratische Laufzeit O(n^2) bedeuten würde.

Post by Heiner Kücker
Könnte man das nicht explizit
durch eine Obergrenze ausschließen ?

???

cu

Heiner Kücker

2007-11-03 11:30:34 UTC

Ralf Ullrich schrieb

Post by Heiner Kücker
Könnte man das nicht explizit
durch eine Obergrenze ausschließen ?

???

Ich meinte
ausschließen, dass der Index in den Bereich des nächsten Hash-Wertes läuft.

--
Heiner Kücker
www.heinerkuecker.de
www.control-and-command.de

Ralf Ullrich

2007-11-03 11:37:38 UTC

Post by Heiner Kücker
Ralf Ullrich schrieb

Post by Heiner Kücker
Könnte man das nicht explizit
durch eine Obergrenze ausschließen ?

???

Ich meinte
ausschließen, dass der Index in den Bereich des nächsten Hash-Wertes läuft.

???

Sorry, ich verstehe die Frage immer noch nicht, liegt aber wohl mehr
daran, dass du eine andere (vor allem engere) Vorstellung von der
Funktionsweise einer Hashtabelle hast, als ich. Vergleiche >offenes
Hashing< und >lineares Sondieren< im Wiki-Artikel
http://de.wikipedia.org/wiki/Hashtabelle , das ist nämlich was ich hier
anwende.

cu

Heiner Kücker

2007-11-03 11:43:05 UTC

Ralf Ullrich schrieb

Post by Ralf Ullrich
Sorry, ich verstehe die Frage immer noch nicht, liegt aber wohl mehr
daran, dass du eine andere (vor allem engere) Vorstellung von der
Funktionsweise einer Hashtabelle hast, als ich. Vergleiche >offenes
Hashing< und >lineares Sondieren< im Wiki-Artikel
http://de.wikipedia.org/wiki/Hashtabelle , das ist nämlich was ich hier
anwende.

Ich lese es mir durch.
Danke.

Heiner

Holger Hoffstaette

2007-11-03 13:50:15 UTC

Post by Ralf Ullrich
Ist im Prinzip ein IntHashSet und realisiert die Geschwindigkeitsgewinne,
die Trove verpricht, aber nicht liefert.

Ralf, kannst Du Deinen Test bitte einmal gegen fastutil
(http://fastutil.dsi.unimi.it/) mit IntSet oder IntSortedSet laufen
lassen und den Vegleich posten?

Holger

Ralf Ullrich

2007-11-03 18:07:57 UTC

Post by Holger Hoffstaette

Post by Ralf Ullrich
Ist im Prinzip ein IntHashSet und realisiert die Geschwindigkeitsgewinne,
die Trove verpricht, aber nicht liefert.

Ralf, kannst Du Deinen Test bitte einmal gegen fastutil
(http://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

Post by Ralf Ullrich
Nicht im Rennen, weil keine allgemeine Lösung, sondern nur für

Mit zwei Reihungen kann man ja /alle/ int-Werte abdecken
(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

Post by Ralf Ullrich
Nicht im Rennen, weil keine allgemeine Lösung, sondern nur für

Mit zwei Reihungen kann man ja /alle/ int-Werte abdecken
(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>

Stefan Ram

2007-11-03 13:11:25 UTC

Post by Stefan Ram
Mit zwei Reihungen kann man ja /alle/ int-Werte abdecken

Wobei dann aber das Initialisieren auf »false« Zeit kostet.

Ralf Ullrich

2007-11-03 18:12:38 UTC

Mit zwei Reihungen kann man ja alle int-Werte abdecken

Nee, kann man nicht. Da braucht man noch etwas mehr. Erklärung zur Übung.

cu

Ralf Ullrich

2007-11-03 18:15:04 UTC

Mit zwei Reihungen kann man ja alle int-Werte abdecken

Nee, kann man nicht. Da braucht man noch etwas mehr. Erklärung zur Übung.

Ähhhm. Peinlich. Ähhhm. Denkfehler meinerseits. Ähhhm. Nix für ungut!

cu

Ralf Ullrich

2007-11-03 18:40:54 UTC

Mit zwei Reihungen kann man ja alle int-Werte abdecken

Nee, kann man nicht. Da braucht man noch etwas mehr. Erklärung zur Übung.

Ist zwar jetzt schon fast nicht mehr witzig, aber nachdem sich mein erster
Gedanke als Denkfehler herausgestellt hat, ist mir inzwischen aufgefallen,
dass ich dennoch recht hatte, wenn auch nicht aus dem Grund, den ich
anfangs dachte. Also obiges stimmt. Zwei Reihungen reichen nicht aus um
alle int-Werte abzudecken. Kann jemand erklären warum?

cu

Stefan Ram

2007-11-03 19:05:54 UTC

Zwei Reihungen reichen nicht aus um alle int-Werte abzudecken.

Das hat vielleicht damit zu tun, daß eine Reihung

new boolean[ java.lang.Integer.MAX_VALUE ]

als Versatz nur die Werte aus dem Intervall

[ 0, java.lang.Integer.MAX_VALUE - 1 ]

akzeptiert, also weniger als die Hälfte der möglichen
int-Werte und

new boolean[ java.lang.Integer.MAX_VALUE + 1 ]

nicht erlaubt ist.

Ralf Ullrich

2007-11-03 19:11:04 UTC

Post by Stefan Ram

Zwei Reihungen reichen nicht aus um alle int-Werte abzudecken.

Das hat vielleicht damit zu tun, daß eine Reihung
new boolean[ java.lang.Integer.MAX_VALUE ]
als Versatz nur die Werte aus dem Intervall
[ 0, java.lang.Integer.MAX_VALUE - 1 ]
akzeptiert, also weniger als die Hälfte der möglichen
int-Werte und
new boolean[ java.lang.Integer.MAX_VALUE + 1 ]
nicht erlaubt ist.

Genau. Zwei Reihungen haben zusammen maximal 2L*Integer.MAX_VALUE
Elemente, es gibt aber 2L*Integer.MAX_VALUE+2 verschiedene Integer-Werte.
Also passen genau zwei Werte nicht in die Reihungen und müssen extra
behandelt werden.

cu

Ralf Ullrich

2007-11-04 17:01:06 UTC

Geht es nach der reinen Laufzeit, so ergibt sich bei mir diese Rangfolge

1. Platz: »Hashed« Lösung mit integriertem Minimal-HashSet.

2. Platz: Die neue Lösung von unten.
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;
}
}

Lesen Sie weiter auf narkive:

Nicht verwandte, aber interessante Themen

Gibt es einen physikalischen Grund dafür, dass sich Farben in einem sehr schmalen Band des EM-Spektrums befinden?

gestartet 2014-11-05 10:48:27 UTC

Ist es falsch zu sagen, dass ein Elektron eine Welle sein kann?

gestartet 2016-02-21 13:50:02 UTC

Warum reinigt heißes Wasser besser als kaltes Wasser?

gestartet 2014-05-27 03:41:22 UTC

Was bedeutet es für einen Hamiltonianer oder ein System, lückenlos oder lückenlos zu sein?

gestartet 2011-02-10 14:54:04 UTC