Collections Was ist schneller - HashMap + Sort v TreeMap?

[fastjack]

Wieso sollten sich Schlüssel ständig ändern, das wäre überhaupt nicht gut. Gerade wenn ich Objekte habe, die Schlüssel darstellen, sollen sie sich nicht ändern können. Aber es gibt bestimmt Anwendungsfälle für...

 

[Spacerat]

Wieso sollten sich Schlüssel ständig ändern, das wäre überhaupt nicht gut. Gerade wenn ich Objekte habe, die Schlüssel darstellen, sollen sie sich nicht ändern können. Aber es gibt bestimmt Anwendungsfälle für...

... sicher doch schliesslich sortiert man ja nicht unbedingt immer nur (besser gesagt eher selten) nach einem Schlüssel (Name, Vorname, usw.). Und genau für solche Geschichten fallen TreeSet und HashMap für mich aus (sind halt beide nicht performant genug).
Ich hatte vor längerer Zeit schon mal versucht Vertices nach X-, Y- und Z-Achse zu sortieren... Die Folge davon, war ein recht langer Thread über "hashCode()" und "equals()" und einer Belehrung darüber, dass man Mutables halt nicht in die API-Maps einpflegen sollte. So hab' ich halt nach 'ner Map gesucht (musste letztendlich selber implementieren) bei der es nichts ausmacht. Heraus kam dieses Interface, welches sich seither als recht nützlich erweist. Nebenbei hat man bei dem Schwachsinn von einst auch noch unheimlich was gelernt würd' ich sagen.

 

[ThreadPool]

[...] Heraus kam dieses Interface, welches sich seither als recht nützlich erweist.

Ich würde gerne die Implementierung sehen.

 

[maki]

Wieso sollten sich Schlüssel ständig ändern, das wäre überhaupt nicht gut. Gerade wenn ich Objekte habe, die Schlüssel darstellen, sollen sie sich nicht ändern können. Aber es gibt bestimmt Anwendungsfälle für...

Eben.
Bei Entities aus der DB ist das auch gar nicht der Fall, wenn man nicht die DB die Schlüssel verteilen lässt.
Dann klappt das auch mit TreeSet/HashMaps.

 

[hüteüberhüte]

@Gregorrr: Also langsam komme ich mir auch etwas vereiert vor...

N einfügen in TreeSet/Map: log(1)+log(2)+..+log(n-1) == log(n)*log(n)/2

Oder täusche ich mich schon wieder?

lg an alle

 

[Spacerat]

Ich würde gerne die Implementierung sehen.

Das ist keine grosse Sache.

package datatypes.utils;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;

public class SortableArrayList<E extends Comparable<E>> extends ArrayList<E> implements SortableList<E> {
	private static final long serialVersionUID = -8181045362616234380L;
	private int sortCount;

	public SortableArrayList() {
		super();
	}

	public SortableArrayList(Collection<? extends E> c) {
		super(c);
	}

	public SortableArrayList(int initialCapacity) {
		super(initialCapacity);
	}

	@Override
	public int indexOf(Object o) {
		sort();
		return super.indexOf(o);
	}

	@Override
	public E get(int index) {
		sort();
		return super.get(index);
	}

	@Override
	public void sort() {
		if(isEmpty() || modCount == sortCount) {
			return;
		}
		Collections.sort(this);
		sortCount = modCount;
	}

	@Override
	public void sort(Comparator<E> comparator) {
		if(isEmpty()) {
			return;
		}
		Collections.sort(this, comparator);
		sortCount = modCount - 1;
	}
}

Im einfachsten Fall, genügt das. Maps und Sets können dieses als ElementListe verwenden und vorm Eintragen neuer Elemente prüfen, ob sie evtl. schon vorhanden sind, dabei wird die Liste ggf. vorher sortiert. Das einzige, was bisher so nicht sehr performant ist, sind die Methoden "keySet()" und "values()" einer Map. "entrySet()" dagegen ist aber relativ einfach: "return elements".

 

[Daassan]

@Gregorrr: Also langsam komme ich mir auch etwas vereiert vor...

N einfügen in TreeSet/Map: log(1)+log(2)+..+log(n-1) == log(n)*log(n)/2

Oder täusche ich mich schon wieder?

lg an alle

also bei dir würde das letzte glied fehlen log(1) + ... + log(n)
aner es müsste letzlich n*log(n) also aufwand rauskommen wenn ich mich nicht irre

aber mal so wie bekommt man aus so nem tree die elemente wieder raus?
find nur first/last aber kein next oder get, etc
da stellt sich mir die frage wie funzt der iterator?
um da was wieder was zu bekommen is der aufwand doch auch n*log(n)

oder?

[OT]
trotzdem versteh ich es immer noch nicht
ok kein hintergrund zu sowas is immernoch irgendwie naja...

dennoch frage:
unter welcher bedingung ist etwas sortiert?
wenn ich nen hashset erstell ist doch der inhalt am ende nach dem hash sortiert
mit dem vorteil das es man eben sofort findet und nicht er mit such algoritmen ran muss

wieso die "hashsortierung" zerstören?
egal ob chaining oder doubhashing

es ist shcon interesant sone frage zu stelle
auch wenn ich so ganz ohne hintergrund es etwas witzlos finde zu klären
[/OT]

 

[Spacerat]

aber mal so wie bekommt man aus so nem tree die elemente wieder raus?
find nur first/last aber kein next oder get, etc
da stellt sich mir die frage wie funzt der iterator?
um da was wieder was zu bekommen is der aufwand doch auch n*log(n)

Sind dir die Methoden "higher(E element)" und "lower(E element)" noch gar nicht aufgefallen? Aufsteigend iteriert man mit

E e = treeSet.first();
while(e != null) {
  e = higher(e);
}

und absteigend

E e = treeSet.last();
while(e != null) {
  e = lower(e);
}

...oder man verwendet den passenden Iterator ("iterator()" aufsteigend, "descendingIterator()" absteigend)
Der Aufwand dabei dürfte in beiden Fällen bei O(1) liegen, weil die Nachbarelemente ja jeweils Member des aktuellen sind.

 

[Daassan]

laut api sind das dann endlosschleifen
denn sie werden wiedergegeben nicht entfernt

und egal welches ich nehm entweder ist das kleinste element root oder das höchste
aber das jeweilige gegenstück sollte doch dann aufwand con log(n) pro zugriff kommen oder?

(bin ein junger entwickler und musste sowas bisher nicht verwenden da meine programme nur wenig datenmengen bearbeiten muss, darum hab ich nicht so die erfahrung mit dem ganzen stuff, ich weis das es da ist wenn es irgendwann mal relevant wird für mich ;D)

halt nun hab ich ich richtig aufgepasst...
wo kommt das lower/higher her?
schwarze magie? D:

verbrennt ihn!

^^ nein bis her nicht
wo kommt das her
sollte nich in der api es irgendwo aufgeführt werden?

 

[andiv]

log(1)+log(2)+..+log(n-1) == log(n)*log(n)/2

Wie kommst du denn auf diese Umrechnung?

Ich würde ja so rechnen, was auf O(n * log(n)) führt:

log(1) + log(2) + ... + log(n-1) + log(n)
= log(1 * 2 * ... * (n-1) * n)
= log(n!)
< log(n * n * ... * n * n)
= log(n^n)
= n * log(n)

 

[Spacerat]

laut api sind das dann endlosschleifen
denn sie werden wiedergegeben nicht entfernt

und egal welches ich nehm entweder ist das kleinste element root oder das höchste
aber das jeweilige gegenstück sollte doch dann aufwand con log(n) pro zugriff kommen oder?

(bin ein junger entwickler und musste sowas bisher nicht verwenden da meine programme nur wenig datenmengen bearbeiten muss, darum hab ich nicht so die erfahrung mit dem ganzen stuff, ich weis das es da ist wenn es irgendwann mal relevant wird für mich ;D)

halt nun hab ich ich richtig aufgepasst...
wo kommt das lower/higher her?
schwarze magie? D:

verbrennt ihn!

^^ nein bis her nicht
wo kommt das her
sollte nich in der api es irgendwo aufgeführt werden?

"lower()" und "higher()" sind zwei Methoden des TreeSets. Die entsprechenden Methoden der TreeMap wären "lowerKey()" oder "lowerEntry()" bzw. "higherKey()" und "higherEntry()".
Endlosschleifen werden es weder bei der TreeMap noch beim -Set, ganz einfach deswegen, weil die Zweige des Baumes oder die Kette des Sets irgendwann mal zu Ende sind (mindestens ein Nachbar ist null). Kreuz-, Quer- und Kreisbezüge werden beim Einfügen in die Map (bzw. in das Set) logischerweise ausgeschlossen.

 

[hüteüberhüte]

So Leute, die Ergebnisse sprechen wohl für sich:

    public static void treeSet(List<Integer> l) {
        long t1 = System.currentTimeMillis();
        SortedSet<Integer> s = new TreeSet<Integer>(l);
        long t2 = System.currentTimeMillis();
        System.out.println("treeSet = " + (t2 - t1));
    }

    public static void treeMap(List<Integer> l) {
        long t1 = System.currentTimeMillis();
        SortedMap<Integer, Integer> m = new TreeMap<Integer, Integer>();
        for (Integer i : l) {
            m.put(i, i);
        }
        long t2 = System.currentTimeMillis();
        System.out.println("treeMap = " + (t2 - t1));
    }

    public static void hashSet(List<Integer> l) {
        long t1 = System.currentTimeMillis();
        Set<Integer> s = new HashSet<Integer>();
        for (Integer i : l) {
            s.add(i);
        }
        Integer[] ia = new Integer[s.size()];
        int i = 0;
        for (Integer elem : s) {
            ia[i] = elem;
            i++;
        }
        Arrays.sort(ia);
        long t2 = System.currentTimeMillis();
        System.out.println("hashSet = " + (t2 - t1));
    }

    public static void hashMap(List<Integer> l) {
        long t1 = System.currentTimeMillis();
        Map<Integer, Integer> m = new HashMap<Integer, Integer>();
        for (Integer i : l) {
            m.put(i, i);
        }
        Integer[][] iaa = new Integer[m.size()][2];
        int i = 0;
        for (Map.Entry<Integer, Integer> e : m.entrySet()) {
            iaa[i][0] = e.getKey();
            iaa[i][1] = e.getValue();
            i++;
        }
        Arrays.sort(iaa, new Comparator<Integer[]>() {

            public int compare(Integer[] o1, Integer[] o2) {
                return o1[0].compareTo(o2[0]);
            }
        });
        long t2 = System.currentTimeMillis();
        System.out.println("hashMap = " + (t2 - t1));
    }

    public static void main(String[] args) {
        List<Integer> l = new ArrayList<Integer>();
        for (int i = 0; i < 2000000; i++) {
            l.add(i);
        }
        Collections.shuffle(l);

        treeSet(l);
        treeMap(l);
        hashSet(l);
        hashMap(l);
    }

Spoiler: Ausgabe/Ergebnis

run:
treeSet = 6271
treeMap = 6911
hashSet = 5023
hashMap = 5788
ERSTELLEN ERFOLGREICH (Gesamtzeit: 0 Minuten 25 Sekunden)

Wie Johannes bereits sagte, hängt der Geschwindigkeitsnachteil wohl mit dem (Höhen)-Ausbalancieren und der Restrukturierung des Trees zusammen, der/die/das aus der asymptotischen Laufzeit (Big O notation) nicht hervorgeht.

Ich bin nur noch nicht sicher, was mit "garantiert" gemeint ist, und ob HashSet(Map) O(1) fürs Einfügen auch garantiert.

Also ich muss mich dann umentscheiden und meine Wahl fällt jetzt auf die erste Antwortmöglichkeit!

PS: Kann jemand das mit der Laufzeit noch einmal aufklären, das wäre super liep von euch!

 

[Spacerat]

Ich bin nur noch nicht sicher, was mit "garantiert" gemeint ist, und ob HashSet(Map) O(1) fürs Einfügen auch garantiert.

Also ich muss mich dann umentscheiden und meine Wahl fällt jetzt auf die erste Antwortmöglichkeit!

PS: Kann jemand das mit der Laufzeit noch einmal aufklären, das wäre super liep von euch!

Nein, die HashMap kann O(1) nicht garantieren. Sobald ein Hashcode bereits vorhanden ist und der gleiche noch mal hinzugefügt wird, ist für diese Elemente aus mit O(1), weil nun die HashGruppe per "equals()" durchiteriert wird (Na? Dämmerts? HashCode- und Equals-Konventionen? Hat bei mir auch länger gedauert).

 

[hüteüberhüte]

Ja, und ab und an muss doch auch das Feld vergrößert werden.. Ich erinnere mich auch, daß z.B. beim Kuckuckshashing eine Endlosschleife passieren kann, aber das kommt hier natürlich nicht infrage.

 

[Bernd Hohmann]

Mal abseits der Theorie: Ich habs jetzt 2 Stunden mit einem Mitarbeiter durchgespielt

Für den von mir angenommenen Fall, dass Key/Data-Pärchen ("Entry") in eine sortierte Reihenfolge gebracht werden müssen gilt:

1) ein Sortieren im Bulk ist etwas schneller als das sortierte Einfügen
2) vieles in der Runtime ist eher ein Notnagel als eine sinnvolle Lösung

10.000.000 Elemente mit Schlüssellänge 10 (mittleres Ergebnis über 50 Durchläufe) brauchen mit der TreeMap ca. 38 Sekunden. Bei der Hashmap ist der Zeitkiller das "hintendurchdiebrustinsauge" herauskopieren der Keys und Umwandlung in was "sortierbares" (mit 32 Sekunden aber trotzdem noch schneller). Leider hat man danach "nur" eine sortierte Liste der Keys, man muss also dann über die sortierte Liste lesen uind auf die Hashmap zugreifen was in der Summe die 6 Sekunden Vorsprung etwas auffressen wird.

Soweit die "nimm doch was fertiges"-Lösung durch Aneinanderreihen von API-Aufrufen.

Zerteilt man das etwas und legt die Keys parallel nochmal in einer ArrayList ab dauert der Bulksort nur noch 16 Sekunden weil das umkopieren der Keys aus der HashMap wegfällt.

Ich habe die oben genannte Konstellation mal auf eine alte Routine aus unserer Toolbox losgelassen und die drückt das nochmal auf < 5 Sekunden (ok, die hat beim Füttern aber auch schon nebenbei eine Vorhersage gemacht wo und wie zu sortieren ist).

Fazit: Wenn man es easy haben möchte, dann nimmt man einfach eine TreeMap, Performance ist für den angenommenen Fall nicht mit der Java API zu erreichen, mit wenigen Handgriffen (Abspaltung der Keys) kann man aber eine Halbierung der Laufzeit bekommen.

Bernd

 

[Spacerat]

Mal abseits der Theorie: Ich habs jetzt 2 Stunden mit einem Mitarbeiter durchgespielt

Für den von mir angenommenen Fall, dass Key/Data-Pärchen ("Entry") in eine sortierte Reihenfolge gebracht werden müssen gilt:

1) ein Sortieren im Bulk ist etwas schneller als das sortierte Einfügen
2) vieles in der Runtime ist eher ein Notnagel als eine sinnvolle Lösung

10.000.000 Elemente mit Schlüssellänge 10 (mittleres Ergebnis über 50 Durchläufe) brauchen mit der TreeMap ca. 38 Sekunden. Bei der Hashmap ist der Zeitkiller das "hintendurchdiebrustinsauge" herauskopieren der Keys und Umwandlung in was "sortierbares" (mit 32 Sekunden aber trotzdem noch schneller). Leider hat man danach "nur" eine sortierte Liste der Keys, man muss also dann über die sortierte Liste lesen uind auf die Hashmap zugreifen was in der Summe die 6 Sekunden Vorsprung etwas auffressen wird.

Soweit die "nimm doch was fertiges"-Lösung durch Aneinanderreihen von API-Aufrufen.

Zerteilt man das etwas und legt die Keys parallel nochmal in einer ArrayList ab dauert der Bulksort nur noch 16 Sekunden weil das umkopieren der Keys aus der HashMap wegfällt.

Ich habe die oben genannte Konstellation mal auf eine alte Routine aus unserer Toolbox losgelassen und die drückt das nochmal auf < 5 Sekunden (ok, die hat beim Füttern aber auch schon nebenbei eine Vorhersage gemacht wo und wie zu sortieren ist).

Fazit: Wenn man es easy haben möchte, dann nimmt man einfach eine TreeMap, Performance ist für den angenommenen Fall nicht mit der Java API zu erreichen, mit wenigen Handgriffen (Abspaltung der Keys) kann man aber eine Halbierung der Laufzeit bekommen.

Bernd

Komisch... das ist doch die ganze Zeit mein Reden... Die Kopierereien halten beide API-Implementationen "gleichermassen" auf. Gegen Datenhaltung in einer Liste oder einem Array und sortieren, wenn es notwendig ist, ist kein Kraut gewachsen. Ich suche für mein Interface allerdings immer noch nach 'ner akzeptablen Lösung für die Map womit man Keys und Values getrennt ausgeben kann, ohne Key- und/oder Valueset immer neu instanzieren zu müssen. Bisher behelfe ich mir da immer indem ich rigoros über das Entryset iteriere und mir erst in der Schleife das hole, was ich haben wollte, also...

for(Entry<K, V> e : mySortableMap.entrySet()) {
  K key = e.getKey();
  // oder
  V value = e.getValue();
}

...wobei das EntrySet natürlich die interne Liste der SortableMap ist.

 

[Bernd Hohmann]

Komisch... das ist doch die ganze Zeit mein Reden...

Du hast es nie Aufmerksamskeitswirkvoll artikuliert :toll:

Ich suche für mein Interface allerdings immer noch nach 'ner akzeptablen Lösung für die Map womit man Keys und Values getrennt ausgeben kann, ohne Key- und/oder Valueset immer neu instanzieren zu müssen.

Wenn Du sowas wie Map.Entry<Key, Value> als Storage nimmst wirst Du immer bei key/value ein neues Duplikat der Daten erstellen müssen.

Es sei denn, Du machst es beinhart und führst zwei Objektarrays für key/value und sortierst die Referenzen auf value parallel zu key (so mach ich das).

Bernd

 

[hüteüberhüte]

Ich muss mich damit auch mal mit einen Kollegen/Mitstudenten/kommilitonen unterhalten.

Aber gilt denn:

O (oder Theta) (log(1)+log(2)+...+log(n-1)) < (echt-kleiner, hoffentlich darf man das so schreiben) O(n*log(n)) ?

Wenn ja, dann wäre die O-Notation hinfällig! Denn, wie gesehen, kann TreeSet niemals so schnell werden wie HashSet + Sort! Das Universum steht kurz vor dem Total-Zusammenfall!

 

[Spacerat]

NOCHMAL: Diese Aussage ist nicht ganz richtig... Die TreeMap hat eine garantierte Laufzeit (die zufällig weitaus langsamer ist, als jene einer ausgewogenen HashMap). Eine HashMap ist spätestens dann nicht mehr 100% ausgewogen, wenn ein hinzuzufügendes Objekt den selben Hashcode hat, wie ein bereits existierendes, sich jedoch per "equals()" von diesem unterscheidet und deswegen in der selben Hashgroup landet. Der Zugriff auf die Hashgroups erfolgt in O(1) garantiert. Hat aber eine Hashgroup mehr als ein Element, muss diese Hashgroup nach dem korrekten Element durchsucht werden und das dauert im Zweifelsfalle O(n). Binärsuche usw. fällt dabei aus, weil man nicht davon ausgehen kann, dass auch nur ein Element weitere Sortierkriterien (Comparable) hat. Je mehr sich also eine HashMap füllt, desto höher ist die "Gefahr", dass Hashcodes in dieser bereits verwendet wurden, desto näher kommt man an die Laufzeit einen LinkedList (ich meine mich dran erinnern zu können, dass das mal 'ne ArrayList war, naja, sei's drum), welche wiederum weitaus langsamer als jene einer TreeMap ist. Die Laufzeit einer HashMap ist damit nicht wirklich berechenbar. Das lässt sich testen, indem man einmal X-Millarden Elemente mit identischem HashCode einfügt und sie ein anderes mal "normal" verwendet.

 

[fastjack]

@Spacerat Deine Implementierung kommt irgendwie abstrus vor... aber naja

 

[Spacerat]

@fastjack: Liegt vllt. daran, dass einem das, was die JVM mitbringt in der Regel den Ansprüchen genügt und man solche Konstukte deswegen nicht braucht. Aber an dynamische Daten wurde weder bei Tree- noch bei HashMap gedacht. Evtl. liegt's aber auch daran, dass es die beiden Sortiermethoden bereits in der Javaumgebung (in der Klasse Collections) gibt und meine Implementation deswegen überflüssig wär. Nun, das ist sie insofern nicht, weil sie die Variable "modCount" mit "sortCount" synchronisiert und nur dann sortiert, wenn beide verschieden sind ("sortCount" wird deswegen auch invalidiert, wenn ein externer Comparator verwendet wird).
Der Nachteil von TreeMap ist, dass sie pro Instanz nur einen Comparator zulässt und die HashMap ist nicht mal irgendwie sortierbar, ohne dass man dauernd irgendwas Kopieren muß. Wollte man eine TreeMap also anders sortieren geht auch da das Umkopieren los, was immerhin viel Zeit kostet. Die Idee eines SortableSet (oder List oder was auch immer) ist deswegen also gar nicht mal so verkehrt, selbst wenn der Code oben nicht ganz so perfekt ist wie er sein sollte (da fehlt so einiges) aber das liegt daran, dass ich das in die Antwort-Box des Forums kopiert und einige Stellen entfernt habe.

 

[The_S]

Und der Fragesteller hat dazu keine näheren Angaben gemacht.

Jo. Und vorher macht hier auch keinerlei Diskussion Sinn. Mal ist das eine schneller, mal ist das andere schneller ... eigentlich vermute ich ja etwas ganz anderes, was ich etwas zurück gehalten habe, da der Hut noch nicht mit seinem konkreten Problem rausrückt (warum auch immer), aber was solls: Warum überhaupt der Umweg über eine HashMap? Ich könnte mir vorstellen, dass die Daten - je nach dem wie sie beschaffen sind, wo sie herkommen, wie sie sortiert werden sollen, ... - direkt in einer anderen Struktur besser aufgehoben sind. Zumal sie am Ende ja auch in einem Array stehen können.

 

[hüteüberhüte]

Thema [erledigt].

Ich entscheide mich für HashMap. Schlüssel / Keys sollen nicht verändert werden. Ein Beispiel kann z.B. das Zählen von Buchstaben / Zeichen einer Zeichenkette sein und die anschließende Sortierung nach Häufigkeit.

Vielen Dank für die vielen(!) Antworten fon Euch!

Grüßle lg LIIII

 

[dfahlsdhflasd]

[...]Ein Beispiel kann z.B. das Zählen von Buchstaben / Zeichen einer Zeichenkette sein und die anschließende Sortierung nach Häufigkeit.

Wenn es um primitive Datentypen geht würde ich Ausschau nach speichereffizienteren Implementierungen wie Trove schauen. Die HashMap verbraucht durch die internen Entry-Objekte doch recht viel.

 

[The_S]

Man könnte jetzt noch anmerken, für die Buchstabenhäufigkeit verwendet man ein Array anstatt einer HashMap, merkt sich/ermittelt die höchste Häufigkeit und sortiert dann in Eimern ...

Aber mal ehrlich, der ganze Aufwand für 26 (oder lass es meinetwegen auch 256 sein) Elemente? Das ist sogar mit dem Bubblesort auf einem 10 Jahre alten Handy schneller sortiert als du mit dem Finger schnippen kannst

 

[hüteüberhüte]

Aber mal ehrlich, der ganze Aufwand für 26 (oder lass es meinetwegen auch 256 sein) Elemente? Das ist sogar mit dem Bubblesort auf einem 10 Jahre alten Handy schneller sortiert als du mit dem Finger schnippen kannst

Stimmt auch wieder Trotzdem: Wenn es ein sehr langer Text ist (lass es 2 Mio. Zeichen sein), dann würde sich das permanente lesen und einfügen in eine TreeMap hinziehen! Ggf. kann aber sogar mit einem simplen Array umgegangen werden, wenn es wirklich nur die Zeichen 0-255 sind. Ich hatte mal zufällig Wikipedia - Artikel gelesen, um die Häufigkeit von Buchstaben in en und de zu berechnen.
Grüßle