Collections Was ist schneller - HashMap + Sort v TreeMap?

Umfrage


  • Anzahl der Umfrageteilnehmer
    7
H

hüteüberhüte

Gast
Hallo liebe Leute,

Szenario 1: Viele Elemente werden in eine HashMap gesteckt, danach in ein Array übertragen, welches anschließend sortiert wird.

Oder

Szenario 2: Viele Elemente werden direkt in eine TreeMap gesteckt.

Danke für Eure Antworten.. :)
 
N

nillehammer

Gast
Definitiv TreeMap. Das ist schneller und Du sparst Dir am Ende einmal den Aufruf von
Code:
Arrays.sort(...)
 
H

hüteüberhüte

Gast
10 wäre heavy, unter 10 geht glaub ich nicht. Vor Beweisen schrecke ich halt manchmal zurücl. Probiere es morgen mal. - lg
 
Gregorrr

Gregorrr

Bekanntes Mitglied
Theoretisch:
HashMap mit N Elementen: Laufzeit: N * O(1) = N, danach Sortier-Algorithmus: LOG(N) => N + LOG(N)
TreeMap mit N Elementen: Laufzeit LOG(N)
 
H

hüteüberhüte

Gast
Jo, wenn man bei der asymptotischen Laufzeit alles weg lassen würde, aber kann man nicht auch noch etwas genauer rechnen/beweisen? Sry nochmal..
 
J

JohannisderKaeufer

Gast
Hab dann mal nachgemessen. Sind zwar ein paar Zeilen mehr geworden als erwartet, aber dennoch im überschaubaren Rahmen.

Java:
import java.util.*;
public class MapVergleich {
  public static void treeSet(List<Integer> list){
    long start = System.currentTimeMillis();
    SortedSet<Integer> set = new TreeSet<>(list);
    long ende = System.currentTimeMillis();
    System.out.println("TreeSet\t"+(ende-start));
  }

  public static void map(List<Integer> list){
    Map<Integer,Integer> map = new HashMap<>();
    long start2 = System.currentTimeMillis();
    int[] array = new int[list.size()];
    for(int i = 0; i<list.size();i++){
      map.put(i,list.get(i));
    }
    for(int i = 0; i<array.length ; i++){
      array[i] = map.get(i);
    }
    Arrays.sort(array);
    long ende2 = System.currentTimeMillis();
    System.out.println("Map\t"+(ende2-start2));
  }


  public static void main(String[] args){
    int size = Integer.parseInt(args[0]);
    List<Integer> list = new ArrayList<>();
    for(int i = 0; i<size; i++){
      list.add(i);
    }
    for(int i = 0; i<10; i++){
      Collections.shuffle(list);
      treeSet(list);
      map(list);
    }
  }
}

Code:
$ java MapVergleich 2000000
Code:
TreeSet	6173
Map	4262
TreeSet	6415
Map	3851
TreeSet	4889
Map	3879
TreeSet	4776
Map	1455
TreeSet	6080
Map	3963
TreeSet	4633
Map	1514
TreeSet	6079
Map	1949
TreeSet	5922
Map	1948
TreeSet	5918
Map	1951
TreeSet	6083
Map	1905

Code:
$ java MapVergleich 1000000

Code:
TreeSet	3998
Map	1189
TreeSet	2264
Map	1136
TreeSet	2290
Map	654
TreeSet	2137
Map	681
TreeSet	2159
Map	693
TreeSet	2039
Map	511
TreeSet	2129
Map	807
TreeSet	2043
Map	564
TreeSet	2075
Map	470
TreeSet	2027
Map	694

Ich vermute, dass das ausbalancieren des Trees, gewisse Nachteile mit sich bringen kann.

BigO Notation ist schön, wichtig ist allerdings was tatsächlich hinten raus kommt.
 
S

Spacerat

Gast
Kann man so etwas überhaupt benchmarken? Ist das nicht so, als würde man Birnen und Äpfel miteinander vergleichen?
1. Bei einer TreeMap dauert das Einfügen evtl. geringfügig länger, dafür ist sie aber auch stets sortiert (zumindest wenn ihre Keys immutable sind).
2. Bei Listen ist der Einfügevorgang schneller, sie müssen aber dafür nach jedem neuen Eintrag (oder zumindest bei Bedarf) neu sortiert werden.

Kurz und bündig: Wenn sich die Datenhaltung nicht allzu oft ändert (inkl. und vor allem die Keys) und man die Daten eigentlich nur lesen will eignet sich die TreeMap hervorragend. Sind die Daten dagegen eher dynamisch (bedeutet, Keys sind mutable und die Zahl der Einfüge- bzw. Entfernenvorgänge überwiegt) ist die List besser geeignet.
 
xehpuk

xehpuk

Top Contributor
Code:
[/quote]
Du verwendest ein TreeSet und keine TreeMap. Du sortierst nach Values und nicht nach Keys.

Oder habe ich hier etwas falsch verstanden?

Hier dann der auf TreeMap angepasste Code:
[code=Java]import java.util.*;

public class MapVergleich {
	public static void treeMap(List<Integer> list) {
		Map<Integer, Integer> map = new TreeMap<>();
		long start2 = System.currentTimeMillis();
		for (int i = 0; i < list.size(); i++) {
			map.put(list.get(i), i);
		}
		Set<Integer> set = map.keySet();
		long ende2 = System.currentTimeMillis();
		System.out.println("TreeMap\t" + (ende2 - start2));
	}

	public static void hashMap(List<Integer> list) {
		Map<Integer, Integer> map = new HashMap<>();
		long start2 = System.currentTimeMillis();
		for (int i = 0; i < list.size(); i++) {
			map.put(list.get(i), i);
		}
		Integer[] array = map.keySet().toArray(new Integer[list.size()]);
		Arrays.sort(array);
		long ende2 = System.currentTimeMillis();
		System.out.println("HashMap\t" + (ende2 - start2));
	}

	public static void main(String[] args) {
		int size = Integer.parseInt(args[0]);
		List<Integer> list = new ArrayList<>();
		for (int i = 0; i < size; i++) {
			list.add(i);
		}
		for (int i = 0; i < 10; i++) {
			Collections.shuffle(list);
			treeMap(list);
			hashMap(list);
		}
	}
}
Eine Million Elemente:
Code:
TreeMap	1872
HashMap	1263
TreeMap	1716
HashMap	1326
TreeMap	1981
HashMap	780
TreeMap	2184
HashMap	811
TreeMap	1826
HashMap	858
TreeMap	2200
HashMap	796
TreeMap	2121
HashMap	843
TreeMap	1576
HashMap	1201
TreeMap	1669
HashMap	1357
TreeMap	1794
HashMap	1154
 
Zuletzt bearbeitet:
T

The_S

Top Contributor
Du verwendest ein TreeSet und keine TreeMap. Du sortierst nach Values und nicht nach Keys.

Oder habe ich hier etwas falsch verstanden?

Eine TreeSet ist in der Regel eine TreeMap ;) . Ob jetzt nach Values oder Keys sortiert werden soll geht aus der Fragestellung nicht hervor. Generell frage ich mich, wie Key-Value-Paare von einer TreeMap/HashMap einfach so auf ein Array übertragen werden können. #

Bevor man hier irgendetwas beantworten kann muss man ein paar Eckdaten kennen:

Wie wird später auf die Daten zugegriffen (Szenario TreeSet vs. HashMap + Copy in Array + Array Sort)?
Wie oft werden neue Daten eingefügt?
Wie oft muss auf die sortierte Reihenfolge zugegriffen werden?
Wird immer sortiert zugegriffen?
Kann man absehen in welcher Reihenfolge die Elemente meistens ankommen (teilweise sortiert, komplett durcheinander, ...)?
Um wie viele Elemente handelt es sich eigentlich (wenn es sich nicht um sehr viele Elemente handelt, sollte man eine Wartezeit von einer Sekunde in Kauf nehmen, um die Lesbarkeit zu erhöhen => Logik wird deutlicher)?
 
H

hüteüberhüte

Gast
Also ist ein(e) Tree(Map/Set) immer dann besser, wenn die Datenstruktur permanent sortiert sein soll, ansonsten eine HashMap.

Mit der Laufzeit denke ich ungefähr so:
HashMap: Einfügen: n, Übertragen ins Array: n, Sortieren: n*log(n), zusammen: 2n+n*log(n)
TreeMap: Irgendetwas zwischen n und n*log(n) und n*n

Korrigiert mich, falsch ich falsch liegen sollte.

Vielen Dank nochmals für eure Antworten.
 
J

JRussian

Mitglied
Eine TreeMap basiert in Java auf einem Rot-Schwarz-Baum ? Wikipedia. Diese Datenstruktur hat einen garantierten Aufwand von O(log n) für einfügen, löschen und suchen.

Wenn du eine HashMap anlegst und selbst sortierst, kommst du nicht ansatzweise an diesen geringen Aufwand heran, da gute Sortieralgorithmen selbst einen Aufwand von n log n aufweisen, plus einfügen löschen suchen in der HashMap.

Somit wenn du auf permanent sortierte Daten wert legst -> TreeMap
 
T

The_S

Top Contributor
Also ist ein(e) Tree(Map/Set) immer dann besser, wenn die Datenstruktur permanent sortiert sein soll, ansonsten eine HashMap.

HashMap und TreeMap kann man nicht vergleichen. Bitte beantworte meine Fragen, dann kann man dir auch konkrete Ratschläge geben.

Also ist ein(e) Tree(Map/Set) immer dann besser, wenn die Datenstruktur permanent sortiert sein soll, ansonsten eine HashMap.

Mit der Laufzeit denke ich ungefähr so:
HashMap: Einfügen: n, Übertragen ins Array: n, Sortieren: n*log(n), zusammen: 2n+n*log(n)
TreeMap: Irgendetwas zwischen n und n*log(n) und n*n

Korrigiert mich, falsch ich falsch liegen sollte.

Vielen Dank nochmals für eure Antworten.

Einfügen in eine HashMap kommt drauf an. Im Idealfall 1. Übertragen ins Array: Kommt drauf an wie du das machst. Sortieren n*log(n) passt.
TreeMap: Einfügen: Pro Einfügeoperation log(n). Wenn du also n Elemente hintereinander einfügst, dann wird für jedes Element log(n) fällig, wobei n die Anzahl der jeweils eingefügten Elemente ist.

Aber beschreib doch dein konkretes Szenario. Das hängt von so vielen Parametern ab und ist sicherlich nicht pauschal zu beantworten.
 
Zuletzt bearbeitet:
M

Marco13

Gesperrter Benutzer
Ja, die Frage hatte ich mir indirekt auch gelegentlich gestellt. Es kommt wohl darauf an, was man macht und was man mißt.

Für 'n Elemente einfügen' ist die Laufzeit beim Hash natürlich O(n). Beim TreeSet ist es nicht so einfach: Das Einfügen eines Elements in ein TreeSet, das schon n Elemente HAT, dauert log(n). Also wäre die Zeit für das Einfügen von n Elementen
1 + log(1) + log(2) + log(3) + ... + log(n-1) = Kein Plan :oops: (und zuwenig Koffein im Blut) ... wird vielleicht sowas wie log(n^2) sein? :bahnhof:

Für Sortieren eines Arrays ist es n*log(n). Beim TreeSet fällt das weg.

Da es um die asymptotische Zeit geht ist alles, was man messen kann, prinzipbedingt falsch, aber beim Plotten für 50000-1000000 Elemente sieht es zumindest so aus, als wäre die HashMap schneller (und es würde mich wundern, wenn die Kurven sich später noch schneiden würden ;) )


@The_S: Ich hate das so verstanden, dass es wirklich darum geht, eine TreeMap als einen "Sortierer" zu verwenden. Natürlich hängt es ansonsten nur davon ab, welche Operationen sonst durchgeführt werden.
 

Anhänge

  • MapTest.png
    MapTest.png
    9 KB · Aufrufe: 53
B

Bernd Hohmann

Top Contributor
Kann man so etwas überhaupt benchmarken? Ist das nicht so, als würde man Birnen und Äpfel miteinander vergleichen?

Den Fall habe ich eigentlich recht häufig: Aus einer Liste A werden Daten in eine Liste B extrahiert und nach Schlüssel X sortiert.

Die Erfahrung sagt, dass in diesem Fall eine Verarbeitung im Batch (erst wegschreiben und dann sortieren) immer schneller ist als ein sortiertes einfügen eines jeden Elementes. Aus diesem Grund bieten viele SQL-Datenbanken einen Batch-Insert an.

Bernd
 
T

ThreadPool

Bekanntes Mitglied
Also ist ein(e) Tree(Map/Set) immer dann besser, wenn die Datenstruktur permanent sortiert sein soll, ansonsten eine HashMap.

Naja, eine TreeMap bedient sich in der Standardimplementierung eines Rot-Schwarz-Baums der für alle Operationen O(log n) benötigt. Aber mit der Groß-O-Notation muss man ja vorsichtig sein, da zwei Algorithmen zwar in der selben Komplexitätsklasse liegen können einer jedoch auch merklich schneller sein kann als der Andere.

Allgemein stellen sich bei der Auswahl der "richtigen" Datenstruktur aber auch weitere Fragen. Z.B. Wird eine garantierbares Laufzeitverhalten benötigt? Wie hoch ist das Datenvolumen? Wie ist die Einfügereihenfolge der Daten, zufällig, teilweise sortiert, sortiert? Wie ist die Verteilung der Daten? Können die Daten nach räumlichen oder zeitlichen Faktoren geordnet werden? D.h. wenn ich A benötige lohnt es sich ein gewisses Umfeld von A im Zugriff zu haben? Wie ist das Abfrage/Einfügeverhältnis? Wird eine effiziente Implementierung der Datenstruktur zur Verfügung gestellt, gibt es vll. Libaries mit effizienteren Implementierungen?
 
Zuletzt bearbeitet:
C

Crian

Top Contributor
Generell finde ich es etwas gewagt, so eine Frage per Umfrage in einem Forum entscheiden zu wollen.
 
Gregorrr

Gregorrr

Bekanntes Mitglied
OK, log(N) zum Sortieren ist natürlich Bullshit... sorry war schon spät gestern ;)


Meiner Meinung nach müsste es bei der asymptotischen Laufzeit doch eher so aussehen:

Szenario 1: N Einfügeoperationen in konstanter Zeit ergibt N * O(1) = N, danach Sortierung mit O(N * log(N)), so kommen wir auf O(N) + O(N * log(N))

Szenario 2: N Einfügeoperationen, welche immer sortiert wird, dabei hat die TreeMap-Implementierung eine Laufzeit für put von: log(N), wobei jedesmal log(N) ausgeführt wird. Das ist die Reihe:

sum(i+log(i)) für i=1 bis unendlich. Aufgelöst ist das 1/2 (n² + 2log([1]_n) + n), [siehe 1] wobei [1]_n das Pochhammer symbol von 1 ist [siehe 2], was schon relativ komplex aussieht und einen quadratischen Term auffweist (siehe auch Post von Marco13).

Also ist HashMap mit O(N*log(N)) < TreeMap mit O(N²).

Lange Rede, kurzer Sinn: HashMap müsste um einiges schneller sein. (Falls ich nicht komplett daneben liege mit meiner asympt. Analyse).

Wenn man sich das überlegt ist das auch sinnig: Die TreeMap liegt immer in einem sortierten Zustand vor, während die HashMap ja nur einmal (am Ende) sortiert wird. Der zusätzliche Sortieraufwand (auch wenn es durch die Datenstruktur bedingt ist), muss sich irgendwie widerspiegeln.

Im Grunde läuft das darauf hinaus: 1 Sortierung, vs. N-Sortierungen, da Sortierung die teure Operation ist.


[1] sum(i+log(i)), i=1 to infinity - Wolfram|Alpha
[2] pochhammer of 1 - Wolfram|Alpha
 
S

Spacerat

Gast
Muss die HashMap beim Einfügen und Auffinden der Elemente nicht blos HashGruppen durchsuchen? Ist die Laufzeit für Einfüge- und Suchoperationen dann nicht auch so ungefähr O(log(n)), zumindest wenn die HashMap ausgewogen ist, also nur verschiedene Hashes enthält? Wird die Einfüge-Laufzeit zu Lasten der Such-Laufzeit bei der HashMap nicht zunehmend geringer, je unausgewogener sie wird, sprich je mehr gleiche Hashes verwendet werden?
Wäre die Sortierzeit einer Hashmap demnach dann nicht auch nur geringfügig über O(log(n))?

Wie gesagt, die beiden Maps geben sich nicht viel, nur die Dynamik der Daten entscheidet, was man verwenden sollte. Ihr könnt ja mal 'ne TreeMap mit mutable Keys verwenden, diese Keys ändern während sie in der TreeMap sind und euch die Reihenfolge in dieser Map anschliessend mal ansehen, soviel zum Thema "immer sortiert".
Das schnellste in dieser Hinsicht dürfte dann die IdentityHashMap sein, weil sie am besten mit mutable Keys klar kommt.
 
Zuletzt bearbeitet von einem Moderator:
M

Marco13

Gesperrter Benutzer
Die Keys bei einer HashMap zu ändern macht auch keinen Sinn. Und bezüglich der Geschwindigkeit und so... natürlich hängt alles von der Hashfunktion ab. hash(x)=1 ist auch eine gültige Hashfunktion, aber dann hätte man im Prinzip eine linked list. Man geht bei einer HashMap eben davon aus, dass die Hashfunktion "perfekt" und damit die Laufzeit der wichtigsten Operationen O(1) ist, auch wenn sie mal O(2) oder O(10) sein kann, das ist schließlich alles das gleiche ;)
 
S

Spacerat

Gast
Mensch klar... die Hashgruppen kann man ja in eine List (oder Array) packen und der Hashcode ist der Index. Und siehe da... wenn man einen Blick in die API wirft...
[JAVA=149]
transient Entry<K, V>[] table;[/code]... wird's genau so gemacht. Naja, fast, es fehlen die Hashgruppen (also jene, wo nach Übereinstimmung des Hashcodes zusätzlich per "equals()" verlichen wird) ???:L... wo hatte man die doch gleich noch verwendet? War das nicht in der HashMap?
 
Zuletzt bearbeitet von einem Moderator:
M

Marco13

Gesperrter Benutzer
Java:
    static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next; // <- Da... jeder Entry ist der Anfang einer Linked List
...
 
H

hüteüberhüte

Gast
Generell finde ich es etwas gewagt, so eine Frage per Umfrage in einem Forum entscheiden zu wollen.

Jetzt fehlt nur noch ein Philosoph und seine Meinung :D

Meint ihr, das Thema würde sich für eine Bachelorarbeit eigne, wenn man noch Sortierverfahren (Quicksort u. Mergesort z.B.) und ein paar Anwendungsbeispiele mit rein nimmt? (Aber warhsceinlich nehme ich eh etwas anderes.)

Thanks a lot until now.
 
T

ThreadPool

Bekanntes Mitglied
[...]
Also ist HashMap mit O(N*log(N)) < TreeMap mit O(N²).[...]

Da die TreeMap auf einem Rot-Schwarz-Baum basiert zweifle ich stark daran das beim Einfügen etwas derartig quadratisches herauskommt, zumal sich das O(log N) beim Einfügen auf die Höhe des Baumes bezieht die im schlechtesten Fall maximal 2 * log N ist, was immernoch in O(log N) liegt.
 
G

gasssssst

Gast
[...]
Also ist HashMap mit O(N*log(N)) < TreeMap mit O(N²).

Willst du uns vergackeiern? Wenn eine Einfügeoperation in eine TreeMap O(log(n)) dauert, dann dauern n Einfügeoperationen natürlich O(n * log(n)) und nicht irgendwas quadratisches... Zumal das "zweite" n wie ThreadPool schon gesagt hat die Höhe des Baumes ist, und daher ebenfalls nur logarithmisch und nicht linear wächst.
 
M

Marco13

Gesperrter Benutzer
Öhm... auch wenn die Diskussion ein Mißverständis-anfälliges Niewoh hat (nicht wertend gemeint: Man könnte auch einen Mathematiker fragen, der einem als Antwort dann einen Beweis liefert, den man nicht ohne LaTex aufschreiben kann) : Beim "log(n)" bezieht sich das 'n' schon auf die Anzahl der Elemente. Die Höhe ist ja gerade das "log" ... :bahnhof:
 
S

Spacerat

Gast
[OT]
...auch wenn die Diskussion ein Mißverständis-anfälliges Niewoh...
"Niveau" schreibt man im Zweifelsfalle ohne "h"... Man weis "nie wo" man sich hinflüchten kann, wenn man die Rechtschreibung nicht mehr erträgt. Man weis "nie wo" man die korrekte Lösung für ein Problem (ausser bei Google vllt.) auf die Schnelle herbekommt. :lol:[/OT]
 
fastjack

fastjack

Top Contributor
Als formaler Beweis reicht eine reine Messung nicht, trotzdem hier mal ein paar Benches. Du musst die Dokus lesen und einen formalen Beweis mit TheBigO machen ;)

Nebenbei: Es kommt stark darauf an, wie das alles implementiert wird, bzw. welcher Sortieralgo benutzt wird. Collections.sort() nutzt z.B. MergeSort, um besonders stabil zu sein.

Code:
    private static Random RANDOM = new Random();

    public static void main(String[] args) {
        Bench treeMapBench = new Bench() {
            Map<Integer, Integer> map = null;

            @Override
            public String getName() {
                return "TreeMap";
            }

            @Override
            public void reset() {
                map = new TreeMap<Integer, Integer>();
            }

            @Override
            public void prepare(long lm) {
            }

            @Override
            public void execute(long lm) {
                // put
                for (int i = 0; i < lm; i++) {
                    map.put(RANDOM.nextInt(), RANDOM.nextInt() * 2);
                }

                // get
                Collection<Integer> list = map.values();
            }
        };

        Bench hashMapBench = new Bench() {
            Map<Integer, Integer> map = null;

            @Override
            public String getName() {
                return "HashMap";
            }

            @Override
            public void reset() {
                map = new HashMap<Integer, Integer>();
            }

            @Override
            public void prepare(long lm) {
            }

            @Override
            public void execute(long lm) {
                // put
                for (int i = 0; i < lm; i++) {
                    map.put(RANDOM.nextInt(), RANDOM.nextInt() * 2);
                }

                // get
                List<Integer> list = new ArrayList<Integer>(map.keySet());
                Collections.sort(list);
            }
        };

        Bench hashMapBench2 = new Bench() {
            Map<Integer, Integer> map = null;

            @Override
            public String getName() {
                return "HashMap-TreeSet";
            }

            @Override
            public void reset() {
                map = new HashMap<Integer, Integer>();
            }

            @Override
            public void prepare(long lm) {
            }

            @Override
            public void execute(long lm) {
                // put
                for (int i = 0; i < lm; i++) {
                    map.put(RANDOM.nextInt(), RANDOM.nextInt() * 2);
                }

                // get
                Set<Integer> set = new TreeSet<Integer>(map.keySet());
            }
        };

        QuickBench.benchNxM(10, 50000, new long[] { 10, 100, 1000 }, new long[] { 10000, 100000},
                new Bench[] { treeMapBench, hashMapBench, hashMapBench2 });
    }

Code:
+---------------------------+----------+------------+----------+----------+-----------------+-----------------+
| Bench                     |   Rounds |    Objects |       ms | ms (avg) |              nt |        nt (avg) |
+---------------------------+----------+------------+----------+----------+-----------------+-----------------+
| TreeMap                   |       10 |     10.000 |       35 |        3 |             ... |             ... |
| TreeMap                   |      100 |     10.000 |      160 |        1 |             ... |             ... |
| TreeMap                   |    1.000 |     10.000 |    1.536 |        1 |             ... |             ... |
| TreeMap                   |       10 |    100.000 |      268 |       26 |             ... |             ... |
| TreeMap                   |      100 |    100.000 |    2.698 |       26 |             ... |             ... |
| TreeMap                   |    1.000 |    100.000 |   26.668 |       26 |             ... |             ... |
| HashMap                   |       10 |     10.000 |       42 |        4 |             ... |             ... |
| HashMap                   |      100 |     10.000 |      277 |        2 |             ... |             ... |
| HashMap                   |    1.000 |     10.000 |    2.713 |        2 |             ... |             ... |
| HashMap                   |       10 |    100.000 |      482 |       48 |             ... |             ... |
| HashMap                   |      100 |    100.000 |    4.796 |       47 |             ... |             ... |
| HashMap                   |    1.000 |    100.000 |   48.337 |       48 |             ... |             ... |
| HashMap-TreeSet           |       10 |     10.000 |       35 |        3 |             ... |             ... |
| HashMap-TreeSet           |      100 |     10.000 |      263 |        2 |             ... |             ... |
| HashMap-TreeSet           |    1.000 |     10.000 |    2.479 |        2 |             ... |             ... |
| HashMap-TreeSet           |       10 |    100.000 |      578 |       57 |             ... |             ... |
| HashMap-TreeSet           |      100 |    100.000 |    5.740 |       57 |             ... |             ... |
| HashMap-TreeSet           |    1.000 |    100.000 |   57.704 |       57 |             ... |             ... |
+---------------------------+----------+------------+----------+----------+-----------------+-----------------+
java version 1.6.0_38
Java(TM) SE Runtime Environment(build 1.6.0_38-b05)
Java HotSpot(TM) 64-Bit Server VM(build 20.13-b02, mixed mode)
Linux(3.2.0-36-generic) amd64
Max memory: 3550MB
16GB RAM, 8 Cores, 3.2Ghz
Ubuntu 12.04, Start aus Eclipse

also bei den Ergebnissen kaufe ich die TreeMap ;)
 
T

ThreadPool

Bekanntes Mitglied
[...] Collections.sort() nutzt z.B. MergeSort, um besonders stabil zu sein.

D.h. es gibt stabiler als stabil? ;) IMHO, neben dem Kriterium der Stabilität wurde MergeSort hauptsächlich deshalb gewählt, weil der beste, durchschnittliche und schlechteste Fall (also Omega, Theta, Omicron) immer n log n beträgt. HeapSort weist diese Eigenschaften auch auf fällt aber raus wg. der fehlenden Stabilität und dem IMHO schlechten Zugriffsverhalten bei den heutigen Architekturen, obwohl man HS ziemlich nahe an das Optimum bringen kann. [1]

[1] Heapsort, Quicksort, and Entropy
 
Zuletzt bearbeitet:
J

JohannisderKaeufer

Gast
[OT]
Meint ihr, das Thema würde sich für eine Bachelorarbeit eigne, wenn man noch Sortierverfahren (Quicksort u. Mergesort z.B.) und ein paar Anwendungsbeispiele mit rein nimmt? (Aber wahrscheinlich nehme ich eh etwas anderes.)

Letzthin habe ich einen Interessanten Blog-Post gelesen. Dort hatte ein Entwickler einen neuen Rechner bekommen und stand dann vor der Entscheidung was er mit dem alten machen soll.

Da er in C++ entwickelt hat und es dort Gang und Gebe ist einfach mal Gott und die Welt zu importieren (using boost, etc.), wollte er damit aufräumen.

Also hat er sich was geschrieben, dass die sourcen auscheckt, eines dieser import Statements eliminiert und dann das ganze versucht zu bauen. Und wenn alles gut geht, das ganze eincheckt, und dann mit dem nächsten weitermacht. Erinnert ein wenig an Continuous Integration.


In Java könnte man etwas ähnliches machen. Man könnte für einen CI-Server (Hudson, Jenkins) ein Plugin schreiben, welches nach
Code:
List list = new ArrayList()
sucht, und dann alle implementierenden Subklassen von List durchprobiert.
Das ganze baut, testet und dann anhand geeigneter Tests, der späteren Verwendung entsprechende Benchmarks erstellt. Also ähnlich dem Beispiel von dem C++ Entwickler.

Oft ist es ja so, dass man einfach eine Liste braucht und es einem prinzipiell egal ist was genommen wird, so dass man am liebsten einfach nur ein
Code:
new List();
schreiben wollte. Soll sich die JVM doch mit dem HotSpot-Compiler die beste Implementierung suchen.


Da hat man zum einen etwas praktisches und kann auch den einen oder anderen wissenschaftlichen Aspekt ausarbeiten.[/OT]
 
B

Bernd Hohmann

Top Contributor
Oft ist es ja so, dass man einfach eine Liste braucht und es einem prinzipiell egal ist was genommen wird, so dass man am liebsten einfach nur ein
Code:
new List();
schreiben wollte. Soll sich die JVM doch mit dem HotSpot-Compiler die beste Implementierung suchen.

Wenn Du ein Händchen dafür hast, aus den Unmegen von Tools genau das herauszusuchen, was im geannnten Anwendungsfall die schlechteste Performance hat, solltest Du 4GL Sprachen einsetzen - die können das von Dir geforderte schon ganz gut aus dem Programmkontext ableiten und entsprechend kompilieren.

Bernd
 
T

The_S

Top Contributor
Meint ihr, das Thema würde sich für eine Bachelorarbeit eigne, wenn man noch Sortierverfahren (Quicksort u. Mergesort z.B.) und ein paar Anwendungsbeispiele mit rein nimmt? (Aber warhsceinlich nehme ich eh etwas anderes.)

Nö. Das sind alles Dinge, die man in allgemeiner Form eigentlich im Grundstudium lernt.
 
H

hütte

Gast
@fast, das Problem dürften bei dir die Runden sein (oder vm), ich sprach davon, einmal viele Elemente hinzuzufügen.

@thes: Das ist mir schon klar, deshalb schrieb ich ja Anwendungsbeispiele. ich glaub, johannes hat auch schon eine potentiell brauchbare antwort geliefert, also danke für deine bemühungen (falls man das so nennen kann).t
 
fastjack

fastjack

Top Contributor
@ThreadPool Stabil bedeutet: Die Reihenfolge der Elemente mit gleichem Sortierschlüssel wird bewahrt ;)
 
fastjack

fastjack

Top Contributor
Code:
+---------------------------+----------+------------+----------+----------+-----------------+-----------------+
| Bench                     |   Rounds |    Objects |       ms | ms (avg) |              nt |        nt (avg) |
+---------------------------+----------+------------+----------+----------+-----------------+-----------------+
| TreeMap                   |        1 |  1.000.000 |      689 |      689 |             ... |             ... |
| HashMap                   |        1 |  1.000.000 |      837 |      837 |             ... |             ... |
| HashMap-TreeSet           |        1 |  1.000.000 |    1.552 |    1.552 |             ... |             ... |
+---------------------------+----------+------------+----------+----------+-----------------+-----------------+
java version 1.6.0_38
Java(TM) SE Runtime Environment(build 1.6.0_38-b05)
Java HotSpot(TM) 64-Bit Server VM(build 20.13-b02, mixed mode)
Linux(3.2.0-36-generic) amd64
Max memory: 3550MB

und jetzt? Ich kaufe immer noch die TreeMap ;)
 
fastjack

fastjack

Top Contributor
Code:
    private static Random RANDOM = new Random();

    enum Mode {
        ASC,
        DESC,
        RND,
        EQ;
    }

    private static Mode mode = Mode.EQ;

    private static int getNext(int i) {
        if (mode == Mode.RND) {
            return RANDOM.nextInt();
        } else if (mode == Mode.ASC) {
            return i;
        } else  if (mode == Mode.DESC) {
            return -i;
        } else {
            return 42;
        }
    }

    public static void main(String[] args) {
        Bench treeMapBench = new Bench() {
            Map<Integer, Integer> map = null;

            @Override
            public String getName() {
                return "TreeMap-" + mode;
            }

            @Override
            public void reset() {
                map = new TreeMap<Integer, Integer>();
            }

            @Override
            public void prepare(long lm) {
            }

            @Override
            public void execute(long lm) {
                // put
                for (int i = 0; i < lm; i++) {
                    map.put(getNext(i), getNext(i) * 2);
                }

                // get
                Collection<Integer> list = map.values();
            }
        };

        Bench hashMapBench = new Bench() {
            Map<Integer, Integer> map = null;

            @Override
            public String getName() {
                return "HashMap-" + mode;
            }

            @Override
            public void reset() {
                map = new HashMap<Integer, Integer>();
            }

            @Override
            public void prepare(long lm) {
            }

            @Override
            public void execute(long lm) {
                // put
                for (int i = 0; i < lm; i++) {
                    map.put(getNext(i), getNext(i) * 2);
                }

                // get
                List<Integer> list = new ArrayList<Integer>(map.keySet());
                Collections.sort(list);
            }
        };

        Bench hashMapBench2 = new Bench() {
            Map<Integer, Integer> map = null;

            @Override
            public String getName() {
                return "HashMap-TreeSet-" + mode;
            }

            @Override
            public void reset() {
                map = new HashMap<Integer, Integer>();
            }

            @Override
            public void prepare(long lm) {
            }

            @Override
            public void execute(long lm) {
                // put
                for (int i = 0; i < lm; i++) {
                    map.put(getNext(i), getNext(i) * 2);
                }

                // get
                Set<Integer> set = new TreeSet<Integer>(map.keySet());
            }
        };

        mode = Mode.RND; # hier halt einsetzen, was man moechte

        QuickBench.benchNxM(10, 50000, new long[] { 1 }, new long[] { 100, 1000, 10000, 100000, 1000000, 10000000 },
                new Bench[] { treeMapBench, hashMapBench, hashMapBench2 });
    }

ASC- bedeutet aufsteigende Zahlen
DESC- absteigende Zahlen
EQ- identische Zahl, immer 42
RND- Random

Code:
+---------------------------+----------+------------+----------+----------+-----------------+-----------------+
| Bench                     |   Rounds |    Objects |       ms | ms (avg) |              nt |        nt (avg) |
+---------------------------+----------+------------+----------+----------+-----------------+-----------------+
| TreeMap-ASC               |        1 |        100 |        0 |        0 |         478.553 |         478.553 |
| TreeMap-ASC               |        1 |      1.000 |        5 |        5 |       4.882.085 |       4.882.085 |
| TreeMap-ASC               |        1 |     10.000 |       10 |       10 |             ... |             ... |
| TreeMap-ASC               |        1 |    100.000 |       18 |       18 |             ... |             ... |
| TreeMap-ASC               |        1 |  1.000.000 |      213 |      213 |             ... |             ... |
| TreeMap-ASC               |        1 | 10.000.000 |    5.037 |    5.037 |             ... |             ... |
| HashMap-ASC               |        1 |        100 |        0 |        0 |         173.288 |         173.288 |
| HashMap-ASC               |        1 |      1.000 |        1 |        1 |         775.748 |         775.748 |
| HashMap-ASC               |        1 |     10.000 |        8 |        8 |       7.897.377 |       7.897.377 |
| HashMap-ASC               |        1 |    100.000 |       33 |       33 |             ... |             ... |
| HashMap-ASC               |        1 |  1.000.000 |      227 |      227 |             ... |             ... |
| HashMap-ASC               |        1 | 10.000.000 |    7.978 |    7.978 |             ... |             ... |
| HashMap-TreeSet-ASC       |        1 |        100 |        0 |        0 |         156.252 |         156.252 |
| HashMap-TreeSet-ASC       |        1 |      1.000 |        1 |        1 |         524.748 |         524.748 |
| HashMap-TreeSet-ASC       |        1 |     10.000 |        4 |        4 |       4.571.445 |       4.571.445 |
| HashMap-TreeSet-ASC       |        1 |    100.000 |       30 |       30 |             ... |             ... |
| HashMap-TreeSet-ASC       |        1 |  1.000.000 |      591 |      591 |             ... |             ... |
| HashMap-TreeSet-ASC       |        1 | 10.000.000 |   11.688 |   11.688 |             ... |             ... |
+---------------------------+----------+------------+----------+----------+-----------------+-----------------+
java version 1.6.0_38
Java(TM) SE Runtime Environment(build 1.6.0_38-b05)
Java HotSpot(TM) 64-Bit Server VM(build 20.13-b02, mixed mode)
Linux(3.2.0-36-generic) amd64
Max memory: 3550MB

+---------------------------+----------+------------+----------+----------+-----------------+-----------------+
| Bench                     |   Rounds |    Objects |       ms | ms (avg) |              nt |        nt (avg) |
+---------------------------+----------+------------+----------+----------+-----------------+-----------------+
| TreeMap-DESC              |        1 |        100 |        0 |        0 |         462.860 |         462.860 |
| TreeMap-DESC              |        1 |      1.000 |        5 |        5 |       4.846.570 |       4.846.570 |
| TreeMap-DESC              |        1 |     10.000 |       10 |       10 |             ... |             ... |
| TreeMap-DESC              |        1 |    100.000 |       18 |       18 |             ... |             ... |
| TreeMap-DESC              |        1 |  1.000.000 |      219 |      219 |             ... |             ... |
| TreeMap-DESC              |        1 | 10.000.000 |    5.092 |    5.092 |             ... |             ... |
| HashMap-DESC              |        1 |        100 |        0 |        0 |         200.930 |         200.930 |
| HashMap-DESC              |        1 |      1.000 |        1 |        1 |         765.414 |         765.414 |
| HashMap-DESC              |        1 |     10.000 |       13 |       13 |             ... |             ... |
| HashMap-DESC              |        1 |    100.000 |       32 |       32 |             ... |             ... |
| HashMap-DESC              |        1 |  1.000.000 |      222 |      222 |             ... |             ... |
| HashMap-DESC              |        1 | 10.000.000 |    8.140 |    8.140 |             ... |             ... |
| HashMap-TreeSet-DESC      |        1 |        100 |        1 |        1 |         158.125 |         158.125 |
| HashMap-TreeSet-DESC      |        1 |      1.000 |        1 |        1 |         475.822 |         475.822 |
| HashMap-TreeSet-DESC      |        1 |     10.000 |        5 |        5 |       4.927.499 |       4.927.499 |
| HashMap-TreeSet-DESC      |        1 |    100.000 |       28 |       28 |             ... |             ... |
| HashMap-TreeSet-DESC      |        1 |  1.000.000 |    3.726 |    3.726 |             ... |             ... |
| HashMap-TreeSet-DESC      |        1 | 10.000.000 |    7.503 |    7.503 |             ... |             ... |
+---------------------------+----------+------------+----------+----------+-----------------+-----------------+
java version 1.6.0_38
Java(TM) SE Runtime Environment(build 1.6.0_38-b05)
Java HotSpot(TM) 64-Bit Server VM(build 20.13-b02, mixed mode)
Linux(3.2.0-36-generic) amd64
Max memory: 3550MB


+---------------------------+----------+------------+----------+----------+-----------------+-----------------+
| Bench                     |   Rounds |    Objects |       ms | ms (avg) |              nt |        nt (avg) |
+---------------------------+----------+------------+----------+----------+-----------------+-----------------+
| TreeMap-EQ                |        1 |        100 |        0 |        0 |          74.119 |          74.119 |
| TreeMap-EQ                |        1 |      1.000 |        0 |        0 |         355.154 |         355.154 |
| TreeMap-EQ                |        1 |     10.000 |        3 |        3 |       3.652.869 |       3.652.869 |
| TreeMap-EQ                |        1 |    100.000 |        7 |        7 |       7.037.841 |       7.037.841 |
| TreeMap-EQ                |        1 |  1.000.000 |        6 |        6 |       5.300.106 |       5.300.106 |
| TreeMap-EQ                |        1 | 10.000.000 |       54 |       54 |             ... |             ... |
| HashMap-EQ                |        1 |        100 |        0 |        0 |          87.743 |          87.743 |
| HashMap-EQ                |        1 |      1.000 |        0 |        0 |         216.350 |         216.350 |
| HashMap-EQ                |        1 |     10.000 |        2 |        2 |       2.452.591 |       2.452.591 |
| HashMap-EQ                |        1 |    100.000 |       11 |       11 |             ... |             ... |
| HashMap-EQ                |        1 |  1.000.000 |       13 |       13 |             ... |             ... |
| HashMap-EQ                |        1 | 10.000.000 |      214 |      214 |             ... |             ... |
| HashMap-TreeSet-EQ        |        1 |        100 |        0 |        0 |          47.819 |          47.819 |
| HashMap-TreeSet-EQ        |        1 |      1.000 |        1 |        1 |         127.031 |         127.031 |
| HashMap-TreeSet-EQ        |        1 |     10.000 |        1 |        1 |       1.231.750 |       1.231.750 |
| HashMap-TreeSet-EQ        |        1 |    100.000 |        5 |        5 |       4.476.226 |       4.476.226 |
| HashMap-TreeSet-EQ        |        1 |  1.000.000 |       22 |       22 |             ... |             ... |
| HashMap-TreeSet-EQ        |        1 | 10.000.000 |      212 |      212 |             ... |             ... |
+---------------------------+----------+------------+----------+----------+-----------------+-----------------+
java version 1.6.0_38
Java(TM) SE Runtime Environment(build 1.6.0_38-b05)
Java HotSpot(TM) 64-Bit Server VM(build 20.13-b02, mixed mode)
Linux(3.2.0-36-generic) amd64
Max memory: 3550MB

+---------------------------+----------+------------+----------+----------+-----------------+-----------------+
| Bench                     |   Rounds |    Objects |       ms | ms (avg) |              nt |        nt (avg) |
+---------------------------+----------+------------+----------+----------+-----------------+-----------------+
| TreeMap-RND               |        1 |        100 |        0 |        0 |         319.148 |         319.148 |
| TreeMap-RND               |        1 |      1.000 |        3 |        3 |       3.124.517 |       3.124.517 |
| TreeMap-RND               |        1 |     10.000 |       11 |       11 |             ... |             ... |
| TreeMap-RND               |        1 |    100.000 |       37 |       37 |             ... |             ... |
| TreeMap-RND               |        1 |  1.000.000 |      676 |      676 |             ... |             ... |
| TreeMap-RND               |        1 | 10.000.000 |   14.178 |   14.178 |             ... |             ... |
| HashMap-RND               |        1 |        100 |        0 |        0 |         197.558 |         197.558 |
| HashMap-RND               |        1 |      1.000 |        1 |        1 |         821.147 |         821.147 |
| HashMap-RND               |        1 |     10.000 |       16 |       16 |             ... |             ... |
| HashMap-RND               |        1 |    100.000 |       62 |       62 |             ... |             ... |
| HashMap-RND               |        1 |  1.000.000 |      761 |      761 |             ... |             ... |
| HashMap-RND               |        1 | 10.000.000 |   17.656 |   17.656 |             ... |             ... |
| HashMap-TreeSet-RND       |        1 |        100 |        0 |        0 |         114.174 |         114.174 |
| HashMap-TreeSet-RND       |        1 |      1.000 |        0 |        0 |         402.736 |         402.736 |
| HashMap-TreeSet-RND       |        1 |     10.000 |        5 |        5 |       5.010.295 |       5.010.295 |
| HashMap-TreeSet-RND       |        1 |    100.000 |       68 |       68 |             ... |             ... |
| HashMap-TreeSet-RND       |        1 |  1.000.000 |    1.110 |    1.110 |             ... |             ... |
| HashMap-TreeSet-RND       |        1 | 10.000.000 |   18.232 |   18.232 |             ... |             ... |
+---------------------------+----------+------------+----------+----------+-----------------+-----------------+
java version 1.6.0_38
Java(TM) SE Runtime Environment(build 1.6.0_38-b05)
Java HotSpot(TM) 64-Bit Server VM(build 20.13-b02, mixed mode)
Linux(3.2.0-36-generic) amd64
Max memory: 3550MB

Interessanterweise schlägt die HashMap mit anschließendem Collections.sort() alle anderen bei bis zu 1000 Elementen, was bei mir so ungefähr der Alltag ist. Darüber ist die TreeMap im Vorteil.
 
M

Marco13

Gesperrter Benutzer
Zugegeben: Das jetzt so zurechzumurksen, dass DOCH wieder die HashMap schneller ist (ich mag es nicht, wenn jemand mich widerlegt :oops: :D) hat länger gedauert, als ich vorher vermutet hatte...
Java:
public class QBTest
{
    private static Random RANDOM = new Random();

    private static int use = 0;
    
    public static void main(String[] args) {
        Bench treeMapBench = new Bench() {
            Map<Integer, Integer> map = null;
            private List<Integer> keys = new ArrayList<Integer>();
            private List<Integer> vals = new ArrayList<Integer>();

            @Override
            public String getName() {
                return "TreeMap";
            }

            @Override
            public void reset() {
                map = new TreeMap<Integer, Integer>();
                keys.clear();
                vals.clear();
            }

            @Override
            public void prepare(long lm) {
                for (int i = 0; i < lm; i++) {
                    keys.add(RANDOM.nextInt());
                    vals.add(RANDOM.nextInt()*2);
                }
            }

            @Override
            public void execute(long lm) {
                // put
                for (int i = 0; i < lm; i++) {
                    map.put(keys.get(i), vals.get(i));
                }

                // get
                Collection<Integer> list = map.values();
                use += list.iterator().next();
            }
        };

        Bench hashMapBench = new Bench() {
            Map<Integer, Integer> map = null;
            private List<Integer> keys = new ArrayList<Integer>();
            private List<Integer> vals = new ArrayList<Integer>();

            @Override
            public String getName() {
                return "HashMap";
            }

            @Override
            public void reset() {
                map = new HashMap<Integer, Integer>();
                keys.clear();
                vals.clear();
            }

            @Override
            public void prepare(long lm) {
                map = new HashMap<Integer, Integer>((int)(lm * 1.5));
                for (int i = 0; i < lm; i++) {
                    keys.add(RANDOM.nextInt());
                    vals.add(RANDOM.nextInt()*2);
                }
            }

            @Override
            public void execute(long lm) {
                // put
                for (int i = 0; i < lm; i++) {
                    map.put(keys.get(i), vals.get(i));
                }
                Integer[] array = map.keySet().toArray(new Integer[map.keySet().size()]);
                Arrays.sort(array);
                use += array[0];
                
            }
        };

        QuickBench.benchNxM(10, 50000, new long[] { 10, 50 }, new long[] { 5000, 50000, 500000 },
            new Bench[] { treeMapBench, hashMapBench });
    }
}
Code:
+---------------------------+----------+------------+----------+----------+-----------------+-----------------+
| Bench                     |   Rounds |    Objects |       ms | ms (avg) |              nt |        nt (avg) |
+---------------------------+----------+------------+----------+----------+-----------------+-----------------+
| TreeMap                   |       10 |      5.000 |       31 |        3 |             ... |             ... |
| TreeMap                   |       50 |      5.000 |       16 |        0 |             ... |             ... |
| TreeMap                   |       10 |     50.000 |      125 |       12 |             ... |             ... |
| TreeMap                   |       50 |     50.000 |      594 |       11 |             ... |             ... |
| TreeMap                   |       10 |    500.000 |    2.888 |      288 |             ... |             ... |
| TreeMap                   |       50 |    500.000 |   14.664 |      293 |             ... |             ... |
| HashMap                   |       10 |      5.000 |      101 |       10 |             ... |             ... |
| HashMap                   |       50 |      5.000 |      187 |        3 |             ... |             ... |
| HashMap                   |       10 |     50.000 |      126 |       12 |             ... |             ... |
| HashMap                   |       50 |     50.000 |      687 |       13 |             ... |             ... |
| HashMap                   |       10 |    500.000 |    2.105 |      210 |             ... |             ... |
| HashMap                   |       50 |    500.000 |   10.312 |      206 |             ... |             ... |
+---------------------------+----------+------------+----------+----------+-----------------+-----------------+
java version 1.7.0_01
Java(TM) SE Runtime Environment(build 1.7.0_01-b08)
Java HotSpot(TM) 64-Bit Server VM(build 21.1-b02, mixed mode)
Windows 7(6.1) amd64
Max memory: 888MB

Es ist schwer, da eine verläßliche, "objektive" Aussagen zu machen...
 
M

maki

Gast
Interessanterweise schlägt die HashMap mit anschließendem Collections.sort() alle anderen bei bis zu 1000 Elementen, was bei mir so ungefähr der Alltag ist. Darüber ist die TreeMap im Vorteil.
Ich wette dass bei weniger als 10 Elementen es so ziemlich egal ist, welche Datenstruktur man nimmt.

Allgemeine Fragen wie "Was ist schneller? XXX oder YYY" führen zu so allgemeinen Antworten wie "Mal so und mal so.."

Grundsätzlich gilt ja noch die Regel, dass "Performance Verbesserungen" belegt werden müssen durch Benchmarks des Systems, sonst hat man nicht optimiert, sondern meist nur den Code verschlechtert, nicht selten ist das System langsamer...
 
fastjack

fastjack

Top Contributor
@Marco so war das nicht gemeint.

Bei mehreren Durchläufen ist die TreeMap schneller. Es ging aber jetzt irgendwie doch nur um einen einzigen Durchlauf...

P.S. und um eine Million Elemente
 
Zuletzt bearbeitet:
Gregorrr

Gregorrr

Bekanntes Mitglied
Jaja, Microbenchmarks, oha eine Operation O(log n) ist also schneller als O(1) :eek:

Lasst mal Bruce Eckel dran:

[1] The Final Performance Testing Example

[PRE]---------- TreeMap ----------
size put get iterate
10 748 168 100
100 506 264 76
1000 771 450 78
10000 2962 561 83
---------- HashMap ----------
size put get iterate
10 281 76 93
100 179 70 73
1000 267 102 72
10000 1305 265 97
------- LinkedHashMap -------
size put get iterate
10 354 100 72
100 273 89 50
1000 385 222 56
10000 2787 341 56
------ IdentityHashMap ------
size put get iterate
10 290 144 101
100 204 287 132
1000 508 336 77
10000 767 266 56
-------- WeakHashMap --------
size put get iterate
10 484 146 151
100 292 126 117
1000 411 136 152
10000 2165 138 555
--------- Hashtable ---------
size put get iterate
10 264 113 113
100 181 105 76
1000 260 201 80
10000 1245 134 77[/PRE]
 
fastjack

fastjack

Top Contributor
Na und jetzt? Lese doch erstmal worum es ging. Es ging darum, wie sich das nachträgliche Sortieren im Gegensatz zum sortierten Einfügen verhält, und zwar bei 1M Elementen und auch nur bei einem Durchgang.
 
Zuletzt bearbeitet:
S

Spacerat

Gast
Komisch, dass ihr bei euren Durchläufen die Vorgänge immer nur einmalig betrachtet... Wenn ich ein SortedSet (oder -Map) habe, ist das immer sortiert. Den Grund aber, warum sich Mutables bei beiden nicht als Key eignen, lasst ihr stets ausser Acht. Mal abgesehen davon, dass HashSets (bzw. -Maps) ohnehin nicht ohne weiteres sortierbar sind, kann man sich den Sortiervorgang am Ende der Einfügeoperationen auch sparen, dann ist die HashMap wieder schneller nur leider nicht sortiert.
Und nun zu dynamischen Daten (Keys). Beide Maps haben genau da ihre Schwachpunkte. Um solche Daten zu sortieren, müssen die Daten beider Sets bzw. Maps in jeweils andere Collections überführt (kopiert) werden. Bei der HashMap wär's 'ne List<Entry<K, V>>, bei TreeMap eine neue TreeMap<K, V>. Bei der HashMap hätte ich nun die Möglichkeit die Map wegzuwerfen und stattdessen die List weiter zu verwenden, welche ich nach belieben sortieren kann (ohne ständig die Daten überführen zu müssen). Nun scheitert's wiederum gerade daran, dass man keine neuen Einträge hinzufügen kann, aber irgendwas ist immer. Was fehlt, wäre also...
Java:
public interface SortableMap<K, V> extends Map<K, V> {
  public void sort();
  public void sort(Comparator<K> comparator);
}
... Bei korrekter Implementation, würden HashMap (okay, diese vllt. nicht ;)) und TreeMap gnadenlos abstinken... jede Wette.
PS.: Der Text endstand, bevor Gregor geposted hat und da steht ja irgendwie auch das, was ich meine (die HashMap ist schneller). -> Vergleich von Birnen mit Äpfeln.
 
Zuletzt bearbeitet von einem Moderator:
fastjack

fastjack

Top Contributor
Nein. Bei einer TreeMap sind die Keys sortiert, denn über die greifst Du ja letztendlich auf die Daten zu. Der Knackpunkt ist, das die Liste der Keys bei einer TreeMap nicht immer neu erzeugt/sortiert wird, sondern gleich beim Einfügen entsprechend geändert wird.
Bei ner normalen Map ist das genauso, bis auf die Sortierung. Deswegen müßte man die Liste der Keys nachsortieren.

Dein Interface wird nicht benötigt, sie mal hier:

Code:
TreeMap(Comparator<? super K> comparator)

Das mit den Mutables stimmt, aber es ja auch bereits in den Javadocs.
 
D

Daassan

Mitglied
ich hab nur überflogen und weis nicht was alles geschrieben wurde
aber grob ist in jeder aussage nur aufwand und bla drin (falls nicht post ignorieren ^^)


aber ne ganz doofe frage... wieso eine hashmap sortieren?
das wiederspricht zu absolut 1000% dessen sinn

man erzeugt ne hash map nich das sie sortiert ist...
mein prof sagt bei einer HashMap ist es so wenn man sucht findet man
im tree hingegen musst erstmal 1000 ästchen entlang huschen
in nem sortierten array im endeffekt auch

also wieso überhaubt ne aufwandsbetrachtung von dem sortieren einer hashmap?
 
T

ThreadPool

Bekanntes Mitglied
Jaja, Microbenchmarks, oha eine Operation O(log n) ist also schneller als O(1) :eek:

Das ist überhaupt nichts worüber man staunen müsste. Groß-O bedeutet nur das der Algorithmus nicht langsamer als O(...) läuft, das ist eine obere Grenze. Theoretisch könntest du auch sagen das konstante Einfügen in eine HashMap läuft in O(log n) oder O(N²), das ist nicht falsch bringt aber nur wenig Erkenntnisgewinn. Genauso sagt O(1) nichts zu den wirklichen Kosten sondern nur das die obere Grenze ein konstanter Wert ist. Eigentlich müssten bei einem Vergleich von Algorithmen alle bekannten Konstanten, Faktoren sowie untere (Omega) und durchschnittliche (Theta) Laufzeitbetrachtungen angegeben werden. Die sind aber oft sehr viel schwieriger zu ermitteln als die obere Grenze.
 
N

nillehammer

Gast
aber ne ganz doofe frage... wieso eine hashmap sortieren?
das wiederspricht zu absolut 1000% dessen sinn

man erzeugt ne hash map nich das sie sortiert ist...
mein prof sagt bei einer HashMap ist es so wenn man sucht findet man
im tree hingegen musst erstmal 1000 ästchen entlang huschen
in nem sortierten array im endeffekt auch

also wieso überhaubt ne aufwandsbetrachtung von dem sortieren einer hashmap?
Das Beispiel mit der Map ist unnötig kompliziert, weil das Ziel ein sortiertes Array ist. Da hätte man bei der Map ja immer drei Kandidaten zur Auswahl, die keys und die values und die entries. Das hätte natürlich Auswirkungen auf die Implementierung. Und der Fragesteller hat dazu keine näheren Angaben gemacht. Deswegen haben hier viele es zur Gegenüberstellung von HashSet/TreeSet vereinfacht. Da die dahinterliegenden Datenstrukturen die gleichen sind, kann man das zum Vergleich tatsächlich heranziehen.

Und die Fragestellung macht durchaus Sinn. Ziel ist ein sortiertes Array. Frage ist: "Wie komme ich da möglichst schnell hin? Varianten:
- HashSet für unsortiertes Einfügen , dann Array draus, dann genau einmal sortieren
- TreeSet es wird immer sortiert eingefügt, dann Array draus.
Du musst hier wie gesagt, das Endziel sortiertes Array im Auge behalten, die Sets sind nur Zwischenschritte
 
S

Spacerat

Gast
Nein. Bei einer TreeMap sind die Keys sortiert, denn über die greifst Du ja letztendlich auf die Daten zu. Der Knackpunkt ist, das die Liste der Keys bei einer TreeMap nicht immer neu erzeugt/sortiert wird, sondern gleich beim Einfügen entsprechend geändert wird.
Bei ner normalen Map ist das genauso, bis auf die Sortierung. Deswegen müßte man die Liste der Keys nachsortieren.

Dein Interface wird nicht benötigt, sie mal hier:

Code:
TreeMap(Comparator<? super K> comparator)

Das mit den Mutables stimmt, aber es ja auch bereits in den Javadocs.
:bae: Reingefallen! (nicht ich, sondern du ;)). Dieser TreeDingens-Konstruktor ist mir nicht unbekannt, wofür benötigt man also mein Interface? Wie war das? Maps sind für mutable Keys (gilt für Sets bei den Values) ungeeignet, nicht selten aber hat man eben genau solche (z.B. Datensätze einer Datenbank mit X Zeilen und Y Spalten). Wer diese bei sich ständig ändernden Schlüsseln so wie in den Beispielen hier mit HashMaps oder TreeSets sortiert, ist selber Schuld. Da lob' ich mir 'ne Map, die ihre Daten in einem Array oder einer List hält (ähnlich wie die HashMap) welches man per übergebenen Comparator sortieren kann. Dadurch spart man nicht nur extrem viel Zeit (weil das Umkopieren entfällt) sondern entlastet auch noch den GC ungemein, weil man nicht ewig irgendwelche Kopien erzeugen muss. In einer solchen Map (bzw. Set) dürfte man (im Gegensatz zu dem, was in den Docs steht) logischerweise auch Mutables entsprechend verwenden.
@nillehammer: Das Ziel ist nicht unbedingt ein sortiertes Array, sondern lediglich sortierte Daten.
 
Zuletzt bearbeitet von einem Moderator:
Ähnliche Java Themen
  Titel Forum Antworten Datum
S Was ist schneller: direkte Sortierung oder indirekt ueber eine SortedMap..? Java Basics - Anfänger-Themen 10
M Schneller Timer Java Basics - Anfänger-Themen 2
P Schneller Quadratzahltest für beliebig große natürliche Zahlen Java Basics - Anfänger-Themen 2
H Operatoren Was ist schneller: <, <=, ==, >, >=? Java Basics - Anfänger-Themen 46
P schneller Sort ? Java Basics - Anfänger-Themen 2
V Double schneller als Float? Java Basics - Anfänger-Themen 13
R ArrayList sehr viel schneller als Array? Java Basics - Anfänger-Themen 2
Dit_ Was ist schneller | < oder >= Java Basics - Anfänger-Themen 6
M Java URLConnection schneller bekommen Java Basics - Anfänger-Themen 3
M schneller Klassenvergleich Java Basics - Anfänger-Themen 2
A Datein kopieren: File oder xcopy? Was ist schneller? Java Basics - Anfänger-Themen 10
R java-programme schneller laufen lassen Java Basics - Anfänger-Themen 41
M Mehrere Threads nutzen --> run() schneller als start(), Warum? Java Basics - Anfänger-Themen 3
ruerob Warum ist Timer schneller als While? Java Basics - Anfänger-Themen 9
J Wie java programm noch schneller machen? Java Basics - Anfänger-Themen 30
S LinkedList indexOf() - geht des irgendwie schneller? Java Basics - Anfänger-Themen 23
O String-Prüfung: Was ist besser/schneller? Java Basics - Anfänger-Themen 15
S Schneller Zugriff auf Liste mit sortierten Flaechen..? Java Basics - Anfänger-Themen 7
G Arraysuche schneller ausführen? Java Basics - Anfänger-Themen 14
H Serialization: Was ist besser(schneller) Binary <-> XM Java Basics - Anfänger-Themen 2
N Schneller als FileWriter? Java Basics - Anfänger-Themen 28
G Bessere Lösung für SQL STMNT ? (Schneller?) Java Basics - Anfänger-Themen 4
C was is schneller Vector oder double Array Java Basics - Anfänger-Themen 5
G java optimieren. wie daten schneller in mysqlDB schreiben? Java Basics - Anfänger-Themen 15
C Hashmap zickt Java Basics - Anfänger-Themen 9
S HashMap contains() Methode Java Basics - Anfänger-Themen 1
Z Satz aufteilen und die Wörter zählen (HashMap) Java Basics - Anfänger-Themen 15
N enum Attribut von Objekten einer Hashmap ausgeben Java Basics - Anfänger-Themen 6
P Verschachtelte Hashmap Java Basics - Anfänger-Themen 6
I Sortiert eine HashMap nicht gleich wie eine ArrayList? Java Basics - Anfänger-Themen 1
B HashMap alphabetisch sortieren Java Basics - Anfänger-Themen 2
J HashMap Java Basics - Anfänger-Themen 5
M Enum-Variable HashMap zuweisen Java Basics - Anfänger-Themen 5
U Hashmap Iterator selbst implementieren Java Basics - Anfänger-Themen 10
N HashMap in List good practice? Java Basics - Anfänger-Themen 2
K Value eines HashMaps in einer HashMap wiedergeben. Java Basics - Anfänger-Themen 5
O Hashmap, ArrayList, LinkedList Java Basics - Anfänger-Themen 7
O HashMap - ArrayList Java Basics - Anfänger-Themen 29
J Hashmap langsamer als compareTo? Java Basics - Anfänger-Themen 23
E HashMap+Vererbung Java Basics - Anfänger-Themen 11
J Erhöhen eines Values als Integer bei gleichen Keys in HashMap Java Basics - Anfänger-Themen 12
N Methoden HashMap interne Werte miteinander vergleichen Java Basics - Anfänger-Themen 7
W The type Long is not visible HashMap Java Basics - Anfänger-Themen 4
M Objekt mit Hashmap vergleichen Java Basics - Anfänger-Themen 22
S Gibt es für die Klasse HashMap Generic Implementierungen? Java Basics - Anfänger-Themen 11
C HashMap - alle keys haben values der letzten put-Anweisung Java Basics - Anfänger-Themen 3
J Hashmap auslesen Java Basics - Anfänger-Themen 7
F HashMap sortieren <String, Long> Java Basics - Anfänger-Themen 3
GreenTeaYT HashMap dupliziert meine Elemente? Java Basics - Anfänger-Themen 2
shiroX Methoden Morse-Code Übersetzer mit HashMap Java Basics - Anfänger-Themen 5
E HashMap Problem Java Basics - Anfänger-Themen 5
P Hashmap anstatt LinkedList? Java Basics - Anfänger-Themen 6
T HashMap und die Methoden Java Basics - Anfänger-Themen 13
N Methoden Interaktives PDF mit HashMap befüllen Java Basics - Anfänger-Themen 0
Z Hashmap auseinandernehmen und analysieren Java Basics - Anfänger-Themen 7
B Durchlaufen von Hashmap und Arraylist Java Basics - Anfänger-Themen 8
F HashMap oder welches Array? Java Basics - Anfänger-Themen 4
T HashMap Java Basics - Anfänger-Themen 24
L Hashmap mit variablem Key Java Basics - Anfänger-Themen 9
M Collections Probleme mit Hashmap Java Basics - Anfänger-Themen 4
N Collections String in HashMap umwandeln Java Basics - Anfänger-Themen 3
Z HashMap richtig benutzen Java Basics - Anfänger-Themen 2
lgund HashMap // TS3 Query Java Basics - Anfänger-Themen 7
Z Hashmap Iterator löscht nicht Java Basics - Anfänger-Themen 8
E Hashmap Wert auslesen Java Basics - Anfänger-Themen 2
S Printstream für einen Hashmap Loop Java Basics - Anfänger-Themen 1
dat_vin OOP Hashmap und Attribute Java Basics - Anfänger-Themen 7
C Check ob eine HashMap schon existiert Java Basics - Anfänger-Themen 16
P Vererbung Eigene HashMap Variante Java Basics - Anfänger-Themen 2
R Hashmap in anderer Klasse nicht benutzbar Java Basics - Anfänger-Themen 1
T Java Hashmap Java Basics - Anfänger-Themen 3
L Gibt es etwas wie "HashMap <String, String, String> Java Basics - Anfänger-Themen 9
K HashMap mit Daten aus ArrayList befüllen Java Basics - Anfänger-Themen 14
S OOP Klasse mit static-Eigenschaften - HashMap füllen Java Basics - Anfänger-Themen 6
O HashMap Fragen Java Basics - Anfänger-Themen 8
T HashMap Werte einfügen, durchsuchen und auslesen Java Basics - Anfänger-Themen 17
M Semantisches Problem HashMap/Netzwerk Java Basics - Anfänger-Themen 4
D HashMap Keys durchlaufen Java Basics - Anfänger-Themen 2
B Zugriff auf csv-Datei per hashmap Java Basics - Anfänger-Themen 5
M HashMap keys ausgeben Java Basics - Anfänger-Themen 2
S In einer Hashmap Klassen regestrieren Java Basics - Anfänger-Themen 2
F HashMap nach kleinstem Value durchsuchen Java Basics - Anfänger-Themen 11
G HashMap Java Basics - Anfänger-Themen 6
F Wortpaare - HashMap - ArrayList Java Basics - Anfänger-Themen 6
M HashMap Frage Java Basics - Anfänger-Themen 3
M HashMap - put() reagiert nicht? Java Basics - Anfänger-Themen 8
N Cast eines Objektes in eine Hashmap Java Basics - Anfänger-Themen 13
A CSV Zeilenweise einlesen und in einer HashMap speichern Java Basics - Anfänger-Themen 12
A Input/Output Hashmap in einem JPanel via JList anzeigen Java Basics - Anfänger-Themen 8
K HashMap auf leere Key-Value-Paare prüfen Java Basics - Anfänger-Themen 14
F Hilfe bei der HashMap. Java Basics - Anfänger-Themen 3
F HashMap vs. TreeMap Java Basics - Anfänger-Themen 5
B HashMap Java Basics - Anfänger-Themen 9
C Collections String[] als value in HashMap Java Basics - Anfänger-Themen 6
V Hashmap Iterieren Java Basics - Anfänger-Themen 4
C Csv File in Hashmap ausgeben Java Basics - Anfänger-Themen 14
T HashMap<String,Object> Werte auslesen Java Basics - Anfänger-Themen 5
I HashMap sortieren Java Basics - Anfänger-Themen 10
I HashMap Java Basics - Anfänger-Themen 11
H Collections Brauche modifizierte HashMap Java Basics - Anfänger-Themen 6

Ähnliche Java Themen

Anzeige

Neue Themen


Oben