Forum: PC-Programmierung Javastruktur um Objekte schnell zu finden


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Dussel (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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?

von Carl D. (jcw2)


Bewertung
2 lesenswert
nicht lesenswert
"eindeutige Nummer" -> HashMap
unabhängig von der Sprache.

von c-hater (Gast)


Bewertung
-2 lesenswert
nicht lesenswert
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).

von c-hater (Gast)


Bewertung
-3 lesenswert
nicht lesenswert
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.

von Carl D. (jcw2)


Bewertung
0 lesenswert
nicht lesenswert
C nicht zu mögen macht nicht automatisch Experte für alles andere.
Das Internet hält Details zu Hashtabellen bereit.

: Bearbeitet durch User
von c-hater (Gast)


Bewertung
-3 lesenswert
nicht lesenswert
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...

von Dussel (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Asdf (Gast)


Bewertung
-2 lesenswert
nicht lesenswert
Treemap ist das, was Du suchst

von Hannes J. (Firma: _⌨_) (pnuebergang)


Bewertung
2 lesenswert
nicht lesenswert
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.

von c-hater (Gast)


Bewertung
-2 lesenswert
nicht lesenswert
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?

von Carl D. (jcw2)


Bewertung
1 lesenswert
nicht lesenswert
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.

von Carl D. (jcw2)


Bewertung
1 lesenswert
nicht lesenswert
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ß".

von c-hater (Gast)


Bewertung
-3 lesenswert
nicht lesenswert
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.

von imonbln (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Carl D. (jcw2)


Bewertung
1 lesenswert
nicht lesenswert
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.

von c-hater (Gast)


Bewertung
-1 lesenswert
nicht lesenswert
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...

von c-hater (Gast)


Bewertung
-1 lesenswert
nicht lesenswert
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.

von Jemand (Gast)


Bewertung
2 lesenswert
nicht lesenswert
c-hater schrieb:
> und wieder nur schwammiges, nichtssagendes Gesülze. Keinerlei Fakten.

Wo sind denn deine Messungen? Nur schwammiges, nichtssagendes Gesülze. 
Keinerlei Fakten.

von c-hater (Gast)


Bewertung
-1 lesenswert
nicht lesenswert
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...

von Dussel (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Jemand (Gast)


Bewertung
2 lesenswert
nicht lesenswert
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.

von c-hater (Gast)


Bewertung
-3 lesenswert
nicht lesenswert
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...

von Carl D. (jcw2)


Bewertung
3 lesenswert
nicht lesenswert
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.

von c-hater (Gast)


Bewertung
-4 lesenswert
nicht lesenswert
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?

von Bastler (Gast)


Bewertung
4 lesenswert
nicht lesenswert
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:
    Map<Integer, IrgendeineKlasse> values
        = new HashMap<Integer, IrgendeineKlasse>();

geschrieben und sind fertig.

von Dussel (Gast)


Bewertung
2 lesenswert
nicht lesenswert
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.

von Brühpolnische (Gast)


Bewertung
2 lesenswert
nicht lesenswert
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.

von Dussel (Gast)


Bewertung
2 lesenswert
nicht lesenswert
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.

von Bastler (Gast)


Bewertung
4 lesenswert
nicht lesenswert
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.

von Dussel (Gast)


Bewertung
1 lesenswert
nicht lesenswert
Übrigens noch vielen Dank für die Antworten.

von c-hater (Gast)


Bewertung
-1 lesenswert
nicht lesenswert
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...

von Bastler (Gast)


Bewertung
2 lesenswert
nicht lesenswert
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!

von Dussel (Gast)


Bewertung
1 lesenswert
nicht lesenswert
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

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.