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?
"eindeutige Nummer" -> HashMap unabhängig von der Sprache.
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.
C nicht zu mögen macht nicht automatisch Experte für alles andere. Das Internet hält Details zu Hashtabellen bereit.
:
Bearbeitet durch User
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: > Und genau bei solchen Fällen komme dann ich in's Spiel und zeige: Während Du hier noch spielst, haben andere schon längst:
1 | Map<Integer, IrgendeineKlasse> values |
2 | = new HashMap<Integer, IrgendeineKlasse>(); |
geschrieben und sind fertig.
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!
c-hater schrieb: > 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... Bei deinen ersten Beiträgen habe ich wirklich gedacht, du würdest fundiert antworten. Falls du doch daran interessiert bist, dich weiterzubilden: http://www.informatik.tu-freiberg.de/lehre/pflicht/EinInf/ws07/Informatik12.pdf (Seite 12) http://ais.informatik.uni-freiburg.de/teaching/ss08/info_MST/material/mst_14_hashing.pdf (Seite 12.24, Alpha ist der Füllfaktor, der auf maximal etwa 0,8 gesetzt wird) Oder in kurz: https://martin-thoma.com/ubersicht-uber-datenstrukturen/#hashtabelle
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.