Moin,
einige Objekte (grob 10.000) sollen in einem Javaprogramm so gespeichert
werden (im RAM), dass schnell auf sie zugegriffen werden kann. Einfügen
muss nicht so schnell sein, traversieren/alle Objekte auslesen soll auch
möglich sein.
Jedes Objekt ist durch eine eindeutige Nummer identifizierbar, über die
das Objekt gefunden werden soll. Die Nummern sind nicht aufsteigend
sortiert, sondern über den Wertebereich (short oder int) etwa
gleichmäßig verteilt.
Mit welcher Standardjavastruktur macht man das am Besten?
Das Beste wäre wahrscheinlich eine Baumstruktur. Da gibt es in Java
TreeSet und TreeMap.
TreeMap hat eigentlich alles, allerdings müsste die Nummer zweimal
gespeichert und an zwei Stellen (im Objekt und in der Map) konsistent
gehalten werden.
TreeSet speichert nur einmal und man könnte CompareTo() mit der Nummer
implementieren. Allerdings gibt es keine get()-Funktion oder Ähnliches.
Das kann man mit ceiling() ziemlich einfach nachbauen, aber da das nicht
schon vorhanden ist, frage ich mich, ob es eine bessere Möglichkeit
gibt.
Was ist am Besten?
Dussel schrieb:> Jedes Objekt ist durch eine eindeutige Nummer identifizierbar, über die> das Objekt gefunden werden soll. Die Nummern sind nicht aufsteigend> sortiert, sondern über den Wertebereich (short oder int) etwa> gleichmäßig verteilt.>> Mit welcher Standardjavastruktur macht man das am Besten?> Das Beste wäre wahrscheinlich eine Baumstruktur.
Ja klar. Und zwar ein simpler Binärbaum (weil die Nummern in etwa
gleichverteilt sind, sonst wäre ein gewichteter Binärbaum das Mittel der
Wahl).
Carl D. schrieb:> "eindeutige Nummer" -> HashMap> unabhängig von der Sprache.
Nö, keinesfalls. Eine Hashmap enthält zwar einen Binärbaum (der die
sinnvollste Implentierung ist), aber eben auch den hier völlig nutzlosen
Overhead der Hashbildung.
Die "Nummern" sind doch nach Aussage des TO bereits näherungsweise
gleichverteilt, wozu soll denn dann noch der Hash gut sein? Dessen
einziger Sinn ist es, bei Daten die eben nicht bereits gleichverteilt
sind, das so hinzubiegen, dass sie es sind.
Und selbst, wenn die Daten nicht gleichverteilt wären, ist die Hashmap
zu hinterfragen. Ein gewichteter Binärbaum könnte die bessere Lösung
sein. Hängt von der Zahl der zu erwartenden Einfügungen im Vergleich zu
den Abfragungen ab. Und da gibt der TO an, dass das Einfügen nicht so
sehr schnell erfolgen muss. Das könnte darauf hinweisen, dass der
gewichtete Binärbaum hier der Hashtable vorzuziehen wäre.
Carl D. schrieb:> C nicht zu mögen macht nicht automatisch Experte für alles andere.> Das Internet hält Details zu Hashtabellen bereit.
Ich weiß, wie die Dinger funktionieren, das hättest du meinen
Anmerkungen entnehmen können.
Du aber scheinbar nicht. Einen sachlichen Einwand kann ich jedenfalls
nicht erkennen...
Carl D. schrieb:> "eindeutige Nummer" -> HashMap unabhängig von der Sprache.
HashMap hat auch zwei Templateparameter (oder wie man das in Java
nennt). Wo ist der Unterschied zur TreeMap?
In der Javareferenz steht "This implementation provides constant-time
performance for the basic operations (get and put), assuming the hash
function disperses the elements properly among the buckets."
Wie sieht das mit der Speichereffizienz aus? Wenn man Buckets für vier
Milliarden (32 Bit) mögliche Werte bereithält, gibt es RAM-Probleme. ;-)
c-hater schrieb:> Und zwar ein simpler Binärbaum (weil die Nummern in etwa> gleichverteilt sind, sonst wäre ein gewichteter Binärbaum> das Mittel der Wahl).
TreeSet ist wohl als Rot-Schwarz-Baum implementiert.
Mir geht es vor Allem darum, welche Javaimplementierung am Besten ist.
So ein binärer Suchbaum ist doch eine Standardanwendung, aber ich habe
bisher keinen mit get-Funktion gefunden. Das wundert mich.
c-hater schrieb:> Carl D. schrieb:>>> C nicht zu mögen macht nicht automatisch Experte für alles andere.>> Das Internet hält Details zu Hashtabellen bereit.>> Ich weiß, wie die Dinger funktionieren, das hättest du meinen> Anmerkungen entnehmen können.>> Du aber scheinbar nicht. Einen sachlichen Einwand kann ich jedenfalls> nicht erkennen...
Trotzdem erzählst du wie immer Scheiße. Jedes Objekt in Java hat eine
Methode hashCode(). Jetzt rate mal wozu die benutzt wird und wie man die
überschreibt wenn das Objekt selber schon einen guten Hash enthält.
Hannes J. schrieb:> Trotzdem erzählst du wie immer Scheiße.
Ah ja?
> Jedes Objekt in Java hat eine> Methode hashCode().
Das mag sein, weiß ich nicht. Nehmen wir mal an, es wäre tatsächlich so.
> Jetzt rate mal wozu die benutzt wird und wie man die> überschreibt wenn das Objekt selber schon einen guten Hash enthält.
Wenn das so ist, fällt zwar die aufwendige Hashbildung weg, es bleibt
aber immer noch eine unnötige Indirektion über die Tabelle der
virtuellen Funktionen als unnötiger Overhead über.
Was sagst du dazu?
c-hater schrieb:> Hannes J. schrieb:>>> Trotzdem erzählst du wie immer Scheiße.>> Ah ja?>>> Jedes Objekt in Java hat eine>> Methode hashCode().>> Das mag sein, weiß ich nicht. Nehmen wir mal an, es wäre tatsächlich so.
Also ahnungslos bei dem Thema.
>> Jetzt rate mal wozu die benutzt wird und wie man die>> überschreibt wenn das Objekt selber schon einen guten Hash enthält.>> Wenn das so ist, fällt zwar die aufwendige Hashbildung weg, es bleibt> aber immer noch eine unnötige Indirektion über die Tabelle der> virtuellen Funktionen als unnötiger Overhead über.>> Was sagst du dazu?
Es handelt sich um Java und nicht Assembler. Wenn man jetzt noch wüßte
wie so eine Methode in Java aufgerufen wird (bevor JIT aktiv wird), dann
wäre ein indirekter Call gar kein Problem.
Dussel schrieb:> Carl D. schrieb:>> "eindeutige Nummer" -> HashMap unabhängig von der Sprache.> HashMap hat auch zwei Templateparameter (oder wie man das in Java> nennt). Wo ist der Unterschied zur TreeMap?> In der Javareferenz steht "This implementation provides constant-time> performance for the basic operations (get and put), assuming the hash> function disperses the elements properly among the buckets."> Wie sieht das mit der Speichereffizienz aus? Wenn man Buckets für vier> Milliarden (32 Bit) mögliche Werte bereithält, gibt es RAM-Probleme. ;-)
.
> c-hater schrieb:>> Und zwar ein simpler Binärbaum (weil die Nummern in etwa>> gleichverteilt sind, sonst wäre ein gewichteter Binärbaum>> das Mittel der Wahl).> TreeSet ist wohl als Rot-Schwarz-Baum implementiert.>> Mir geht es vor Allem darum, welche Javaimplementierung am Besten ist.> So ein binärer Suchbaum ist doch eine Standardanwendung, aber ich habe> bisher keinen mit get-Funktion gefunden. Das wundert mich.
Nimm HashMap. Im Netz gibt es Performance-Untersuchungen, die für deinen
Fall mit 10k Einträgen ein get() mit 30ns messen. Das dürfte "schnell
auf sie zugegriffen werden kann die" sein. Und das Gejammer eines
speziellen bezieht sich auf das Einfügen, was ja "nicht so schnell sein
muß".
Carl D. schrieb:> Es handelt sich um Java und nicht Assembler.
Jetzt hast du verloren. Ich gebe zu bedenken, dass auch Java-Code
letztlich auf realen Maschinen laufen muß. Und es gibt absolut keine,
bei der eine Indirektion nicht zusätzlichen Rechenzeitaufwand
verursacht. Ein gewisser Nachteil ist also auf JEDEN Fall zu erwarten.
Der kann u.U. sogar ziemlich erheblich sein, denn bei großen Maschinen
hängt es auch stark von der Cachebelegung ab. Ein cache miss kann hier
richtig die Performance runter reißen.
c-hater schrieb:> Wenn das so ist, fällt zwar die aufwendige Hashbildung weg, es bleibt> aber immer noch eine unnötige Indirektion über die Tabelle der> virtuellen Funktionen als unnötiger Overhead über.
Na und? Ich bin zwar kein Java Versteher, aber das ist offensichtlich
eine Implementierung, die laut Dokumentation intern einen
Rot-Schwarz-Baum nutzt.
Wir sind und alle einig das ein Rot-Schwarz-Baum, die beste
Datenstruktur für die Anfrage des TO ist.
Von daher kann es sinnvoll sein, den von Dir behaupteten Overhead in
kauf zu nehmen und dafür vermutlich bestens getestete Klassen zu nutzen,
anstelle von unausgereiften eigenen Code.
Vielleicht ist auch der Compiler klug genug um die Indirektion zu
erkennen und weg zu optimieren. Ich würde es jedenfalls erst mal mit der
TreeMap versuchen, bevor ich eigene Datenstrukturen schreibe, vielleicht
ist sie ja für die Ansprüche des TO gut genug.
c-hater schrieb:> Carl D. schrieb:>>> Es handelt sich um Java und nicht Assembler.>> Jetzt hast du verloren. Ich gebe zu bedenken, dass auch Java-Code> letztlich auf realen Maschinen laufen muß. Und es gibt absolut keine,> bei der eine Indirektion nicht zusätzlichen Rechenzeitaufwand> verursacht. Ein gewisser Nachteil ist also auf JEDEN Fall zu erwarten.>> Der kann u.U. sogar ziemlich erheblich sein, denn bei großen Maschinen> hängt es auch stark von der Cachebelegung ab. Ein cache miss kann hier> richtig die Performance runter reißen.
Wenn man jetzt die vielen Puzzlesteine noch richtig zusammenlegen lernt,
dann kann man ein Gesamtbild erkennen. Vielleicht aber auch nur sehen.
imonbln schrieb:> Na und? Ich bin zwar kein Java Versteher
Ich auch nicht. Der Punkt ist, was eigentlich der Unterschied zwischen
den Implementierungen von Hashmap (darum drehte sich die Diskussion
zuletzt) und Treemap (das hast du eingebracht) ist...
Carl D. schrieb:> Wenn man jetzt die vielen Puzzlesteine noch richtig zusammenlegen lernt,> dann kann man ein Gesamtbild erkennen. Vielleicht aber auch nur sehen.
Und wieder nur schwammiges, nichtssagendes Gesülze. Keinerlei Fakten.
c-hater schrieb:> und wieder nur schwammiges, nichtssagendes Gesülze. Keinerlei Fakten.
Wo sind denn deine Messungen? Nur schwammiges, nichtssagendes Gesülze.
Keinerlei Fakten.
Jemand schrieb:> c-hater schrieb:>> und wieder nur schwammiges, nichtssagendes Gesülze. Keinerlei Fakten.>> Wo sind denn deine Messungen?
Ich habe nicht behauptet, irgendwelche Messungen zu haben. Ich habe ja
nichtmal das konkrete Problem, könnte also nichtmal dann, wenn ich
wollte, irgendwas messen.
Was ich aber habe, ist das allgemeine Wissen über Algorithmen und
Datenstrukturen. Und eine 25jahrige Praxis bei deren Optimierung in
unzähligen Anwendungen in ca. 10 Sprachen (Assemblerdialekte der Targets
nicht mitgerechnet).
Ja, Java war bisher nicht dabei. Aber ich gehe ganz stark davon aus,
dass auch Java den allgemeinen Gesetzen der Informatik folgt...
imonbln schrieb:> Wir sind und alle einig das ein Rot-Schwarz-Baum, die beste> Datenstruktur für die Anfrage des TO ist.
Nachdem ich nochmal über die Hashmap gelesen habe, bin ich am Überlegen.
c-hater schrieb:> Der Punkt ist, was eigentlich der Unterschied zwischen> den Implementierungen von Hashmap (darum drehte sich die Diskussion> zuletzt) und Treemap (das hast du eingebracht) ist...
Die TreeMap habe ich direkt am Anfang eingebracht.
Die TreeMap ist wohl ein normaler Baum, wahrscheinlich irgendwie
balanciert. Die HashMap ist wohl ein Array. Der Speicherplatz für ein
Objekt wird durch
Hash Modulo Arraylänge
gebildet. Wenn der Platz belegt ist, wird nach einem bestimmten
Verfahren nach einem freien Platz gesucht.
Die Laufzeit für Einfügen und Suchen ist wohl O(1) und damit schneller
als in einem Baum. Allerdings braucht sie mehr Speicher, als Elemente
gespeichert werden. Jetzt überlege ich, ob das nicht vielleicht doch
besser wäre.
c-hater schrieb:> Was ich aber habe, ist das allgemeine Wissen über Algorithmen und> Datenstrukturen.
Dafür gibt es hier aber ziemlich viel Gerede über irgendwelche angeblich
teuren Operationen, deren Verhalten allerdings maßgeblich von der
konkreten Implementation und der Optimierung abhängig ist.
In meinen ganz einfachen Tests in Rust ist die Cache-optimierte BTreeMap
bei 10 000 Elementen (zufällig Lookups) satt eine Größenordnung
langsamer als die FnvHashMap.
Ergo: Völlig wertloses Gelaber und Spekulation.
Jemand schrieb:> In meinen ganz einfachen Tests in Rust ist die Cache-optimierte BTreeMap> bei 10 000 Elementen (zufällig Lookups) satt eine Größenordnung> langsamer als die FnvHashMap.
Das hat bezüglich des konkreten Java-Problems ungefähr die Aussagekraft
einer Pisse-Spur im Schnee.
Das muss ich jetzt mal sagen, obwohl du eigentlich meine Meinung
bestätigst. Aber wir wollen ja über Fakten reden, nicht nur sinnlos
rumseiern wie dieser Carl D.
Es hängt einfach sehr stark von der konkreten Implementierung des
Java-Programms ab. Es ist nicht auszuschließen, dass der Nachteil der
Benutzung der Hashmap sich durch das Überschreiben des Hashgenerators
der Elemente wirklich auf eine unnötige Indirektion reduzieren läßt,
also letzlich nur der B-Tree der Hashmap vom Algorithmus überbleibt.
Dann wird der Performancenachteil meistens relativ gering bleiben,
jedenfalls deutlich kleiner als eine Größenordnung. Nur in ungünstigen
Konstellationen kann es halt mehr werden. Dann allerdings u.U. auch
deutlich mehr...
Und genau bei solchen Fällen komme dann ich in's Spiel und zeige:
Assembler und Kenntnisse der Zielhardware sind auch heute noch wichtig,
selbst wenn die ursprüngliche Quelle eine echte Hochsprache ist und
nicht nur dieses unsägliche C...
Und es ist mir jedes Mal ein echter Hochgenuss, das zu tun...
Fakt ist:
es gibt Datenstrukturen, die auf schnelles Finden optimiert sind. Da ist
Hash besser als Tree. O(1) < O(log(n)). Zumindest bei relevanten
Datenmengen. Und es hat nichts mit der Implemenrierungssprache zu tun.
Weiterer Fakt:
die Anforderung war, schnelles Finden, eventuell langsameres Einfügen
wird hingenommen. Wer darauf mit Optimierung am falschen Ende reagiert,
der hat die Anforderung nicht kapiert. Oder will einfach nur Stunk
machen. Inklusives oder vermutlich.
Carl D. schrieb:> Fakt ist:> es gibt Datenstrukturen, die auf schnelles Finden optimiert sind. Da ist> Hash besser als Tree. O(1) < O(log(n)).
Jetzt erkenne ich, was du eigentlich meinst. Eine primitive
Lookup-Tabelle.
Aber die macht Hashes echt endgültig überflüssig, wenn schon der
Werteraum der IDs selber klein genug ist. Was zum Teufel sollen dann die
Hashes noch?
Kannst du das erklären?
c-hater schrieb:> Aber die macht Hashes echt endgültig überflüssig, wenn schon der> Werteraum der IDs selber klein genug ist. Was zum Teufel sollen> dann die Hashes noch?
Der Werteraum ist ja nicht so klein. Der kann sehr groß sein. In meinem
Fall zum Beispiel bei einem Integer mehrere Milliarden. Die Tabelle muss
aber nur etwas größer sein, als es Einträge gibt. Dafür hat man im
Allgemeinen für Einfügen und Suchen eine Laufzeit von O(1).
Als Beispiel:
Acht Objekte mit den Nummern (Hashes) 9194291, 4313748, 1870147,
3584916, 2315091, 7138699, 6829790, 6606714 sollen gespeichert werden.
Dafür wählen wir eine Tabelle mit zehn Einträgen (25% freie Plätze). Um
den Speicherplatz für ein Objekt zu finden, wird einfach der Modulo mit
der Tabellenlänge gebildet. Wenn der Platz schon besetzt ist,
verschieben wir den Eintrag in die nächste freie Stelle
9194291 % 10 = 1
4313748 % 10 = 8
1870147 % 10 = 7
3584916 % 10 = 6
2315091 % 10 = 1, aber 1 ist schon besetzt, also kommt das auf Platz 2
7138699 % 10 = 9
6829790 % 10 = 0
6606714 % 10 = 4
Wenn man jetzt Objekt 4313748 finden will, bildet man den Modulo, also
4313748 % 10 = 8 und schon hat man die Speicherstelle in O(1) gefunden.
Wenn es eine Kollision gab, muss man noch weitere Stellen absuchen, aber
das unabhängig von der Gesamtzahl der Objekte.
Laufzeit für Suchen und Einfügen ist O(1), Speicherbedarf O(n).
Nur wenn die Tabelle zu voll wird, muss sie einmal mit mehr Zellen
komplett neu aufgebaut werden. Das müsste dann O(n) sein. Bei passend
gewähltem Anfangswert, passiert das aber nur sehr selten.
Anscheinend ist das für mich wirklich die beste Lösung.
Dussel schrieb:> Anscheinend ist das für mich wirklich die beste Lösung.
Nein nimm endlich HashMap wie schon am Anfang erwähnt. Sowas fummelt man
sich nicht selber zusammen, wenn es schon in der API drinn ist.
Das kannst du zum Spass nebenher mal machen aber das ist so trivial,
dass man sich das auch sparen kann wenn man das Prinzip verstanden hat.
Brühpolnische schrieb:> Sowas fummelt man sich nicht selber zusammen, wenn> es schon in der API drinn ist.
Das habe ich ja auch vor. Von den Datenstrukturen habe ich schon ein
bisschen Ahnung, aber ich weiß halt nicht, was wie in Java implementiert
ist. Deshalb die Frage.
Früher wollte ich immer alles selber machen, aber die Standardstrukturen
sind halt schneller zu benutzen und wahrscheinlich auch effizienter.
Dussel schrieb:> einige Objekte (grob 10.000)Dussel schrieb:> aber ich weiß halt nicht, was wie in Java implementiert> ist. Deshalb die Frage.
Was sind schon 10000 Objekte? Das ist nichts! Da lohnt es nicht,
überhaupt über die Implementierung eine Map in irgendeiner
Programmiersprache nachzudenken.
Überlege mal, wieviel Zeit Du schon zu dieser Frage hier verbraucht
hast. In dieser Zeit hättest Du ein HashMap einfach verwenden können und
Dich um die Geschäftslogik des Programms kümmern können.
Statt dessen wird hier eine rein theoretische Diskussion geführt, die in
der Praxis keine Rolle spielt. Das Zeitverhalten Deines Programms wird
vom Zugriffsmuster auf die Daten und dem CPU-Cache weit mehr beeinflusst
werden, als von der Wahl des Algorithmus.
Man wählt aus, ob Array, Liste, Map oder Set. Diese Auswahl ist in einer
Sekunde getroffen. Als Implementierung nimmt man den Standard der
gewählten Programmiersprache/Umgebung. Fertig.
Ist ein Programm wirklich zu lahm, wirf man den Profiler an und schaut,
wo es wirklich hackt. Alles andere ist Pfusch. Frühe Optimierung ist
absolutes Gift und vergeudete Mühe und Lebenszeit.
Dussel schrieb:> Wenn man jetzt Objekt 4313748 finden will, bildet man den Modulo, also> 4313748 % 10 = 8 und schon hat man die Speicherstelle in O(1) gefunden.> Wenn es eine Kollision gab, muss man noch weitere Stellen absuchen, aber> das unabhängig von der Gesamtzahl der Objekte.
So kann man sich wirklich strukturelle Scheiße schönrechnen...
Ich sage vorher, dass du bei signifkanter Anzahl von Einträgen weit weg
von log(1) für den Lookup landest...
Dazu braucht man kein Mathegenie sein (das bin ich nämlich definitiv
nicht). Aber soviel, wie nötig ist, um das zu erkennen, habe ich dann
doch locker drauf...
c-hater schrieb:> Ich sage vorher, dass du bei signifkanter Anzahl von Einträgen weit weg> von log(1) für den Lookup landest...
Definitiv. Da hast Du zu 100% recht. Denn log(1) = 0.
> Dazu braucht man kein Mathegenie sein (das bin ich nämlich definitiv> nicht).
Auch hier, uneingeschränkte Zustimmung von mir. Ein feiner Zug von Dir,
das hier schonungslos zuzugeben.
> Aber soviel, wie nötig ist, um das zu erkennen, habe ich dann> doch locker drauf...
Diese Offenheit, beneidenswert!
Zu meiner Schande muss ich gestehen, mit solch einer nackten Ehrlichkeit
hätte ich bei Dir nicht gerechnet.
Hut ab!
