Oha. Ich und BigO

Xion hat folgendes geschrieben :

Martok hat folgendes geschrieben : binäre Suche auf sortierter Liste Das fasziniert mich. Kannst du mal kurz skizzieren, wie das geht? Typischerweise kann man bei Listen nicht in O(1) auf ein bestimmtes (das mittlere) Objekt zugreifen.

Nicht in verketteten Liste, klar. Da ists O(n/2), klar (falls man die Anzahl separat mitzählt). Aber wer will auch verketten, wenn man nicht muss Auf Arrays ist jeder Zugriff O(1)...
Damit wird die gesamte Suche:

Xion hat folgendes geschrieben :

Komplexität O(logn)

Aber wenn man unbedingt was verkettetes braucht, gibt's immer noch SkipListen. Wenn man die passend verdrahtet, könnte das auch gehen. Da würde man dann die Skips als so eine Art BTree setzen. Glaube ich

Xion hat folgendes geschrieben :

also deutlich schlechter als O(1) für die Hashtable.

Da hast du aber nur 1/3 berechnet:
Hash berechnen: O(stringlänge)
Bucket finden: O(1) falls das ein Array ist, bei größerem Keyspace wirds wohl eine Sparselist, die ist langsamer
Eintrag in Bucket suchen: O(m) oder O(logm), je nachdem was da drunter hängt...

Martok hat folgendes geschrieben :

Aber wenn man unbedingt was verkettetes braucht, gibt's immer noch SkipListen. Wenn man die passend verdrahtet, könnte das auch gehen. Da würde man dann die Skips als so eine Art BTree setzen. Glaube ich

Du hattest was von InsertionSort und binärer Suche erzählt. Für InsertionSort in O(1) ("sofort") braucht man ja verkettete Listen. Und das dann mit binärer Suche...
Ok, SkipListen kannte ich noch nicht, aber das Vorgehen ist logisch. Vielleicht würde das tatsächlich gehen, aber man müsste diese "Skips" immer wieder reparieren...weil wenn man einen Eintrag löscht oder einfügt, dann ist die Mitte ja nicht mehr die Mitte Einfügen wäre wohl dann O(logn)

Martok hat folgendes geschrieben :

Da hast du aber nur 1/3 berechnet: Hash berechnen: O(stringlänge)

Das stimmt.

Martok hat folgendes geschrieben :

Eintrag in Bucket suchen: O(m) oder O(logm), je nachdem was da drunter hängt...

Eigentlich sollte die Hashtable so groß sein, dass es keine Kollisionen gibt. Bei Mathematiker waren es ja nur 5 Elemente, bei denen eine Kollision vorkam. Das m wäre also etwa 5/16000 (im Durchschnitt)

Also wenn man grob genug ist, kommt für die Hashtable schon O(1) hin Wir haben aber auch Algorithmen gehabt, bei denen man sagt, der braucht O(2^100+logn) = O(logn) Die Notation ist nicht immer ganz praxisnah

Xion hat folgendes geschrieben :

Du hattest was von InsertionSort und binärer Suche erzählt.

Da hatte ich mich wohl irgendwo selbst überholt

Xion hat folgendes geschrieben :

Martok hat folgendes geschrieben : Eintrag in Bucket suchen: O(m) oder O(logm), je nachdem was da drunter hängt... Eigentlich sollte die Hashtable so groß sein, dass es keine Kollisionen gibt. Bei Mathematiker waren es ja nur 5 Elemente, bei denen eine Kollision vorkam. Das m wäre also etwa 5/16000 (im Durchschnitt)

Um den Preis von hohem Speicherverbrauch. 16bit Keyspace mit je 4byte Daten sind 256kByte, das geht ja noch. Bei 32bit sind das dann schon 16GByte...

Wobei das dann auch wieder ein anderes Verfahren ist. WP sagt, das was du meinst heißt dann "dynamic perfect hashing". Ich kenn keinen, der das freiwillig für General-Purpose Klassen nimmt Das was ich meine ist eine "array hash table". Kann man natürlich auch gern mit einer TList bauen, ist meistens einfacher.

Ging es in diesem Thread eigentlich um die effizienteste Speziallösung für das konkrete Problem oder was Allgemeines? Kann nämlich durchaus sein, dass ich hier Zeug meine, was gar keinen interessiert

OT: MurmurHash wär auch noch was, falls die KeyStrings viel länger werden (und so viele, dass man nicht einfach auf 1-2 Bytes runter-XORen kann, sondern die perfekte Verteilung im Keyspace braucht). Implementation in Delphi existiert, aber ohne Testvector etwas schwierig. Muss bei Gelegenheit mal die Testsuite portieren.

[quote="Martok"(673345)]

Xion hat folgendes geschrieben :

Wobei das dann auch wieder ein anderes Verfahren ist. WP sagt, das was du meinst heißt dann "dynamic perfect hashing". Ich kenn keinen, der das freiwillig für General-Purpose Klassen nimmt Das was ich meine ist eine "array hash table". Kann man natürlich auch gern mit einer TList bauen, ist meistens einfacher.

Ich meine das dort erwähnte Open addressing. Statt Buckets mit Listen suche ich mir einfach deterministisch ein neues freies Slot. Das ist auch nicht schneller als mit Buckets, aber wie auch dort erwähnt, sollten pro Bucket sowieso nur max. 3 Elemente drin sein. Fällt also aus der O-Notation raus

Martok hat folgendes geschrieben :

Ging es in diesem Thread eigentlich um die effizienteste Speziallösung für das konkrete Problem oder was Allgemeines?

Ich denke es ging um eine Speziallösung. Das Thema ist aber eigentlich schon gelöst, und ich werde mich jetzt auch zurückhalten. Versprochen

Hallo,

Martok hat folgendes geschrieben :

Ging es in diesem Thread eigentlich um die effizienteste Speziallösung für das konkrete Problem oder was Allgemeines? Kann nämlich durchaus sein, dass ich hier Zeug meine, was gar keinen interessiert

Auch wenn ich nichts alles verstehe, ist es meiner Meinung nach hochinteressant. Und Lernen kann man bei Euren Beiträgen eine Menge.

Xion hat folgendes geschrieben :

Ich denke es ging um eine Speziallösung. Das Thema ist aber eigentlich schon gelöst, und ich werde mich jetzt auch zurückhalten. Versprochen

Warum? Wie gesagt, mich interessiert dies sehr und ich denke auch andere.
Allein schon die Vielzahl der Möglichkeiten, so ein Suchproblem effektiv umzusetzen, ist faszinierend.

Beste Grüße
Mathematiker