Binäre (Hex) Suche

[jfheins]

Binäre Suche kannste knicken wenn deine Daten nicht sortiert sind.

Bleiben noch Suchalgorithmen wie z.B. http://de.wikipedia.org/wiki/Boyer-Moore-Algorithmus
Falls du keine fertige Implementierung findest, musst du ihn wohl selbst implementieren.

Ach ja, und natürlich eine anständige Puffergröße verwenden. 4kB Mindestens.

[Furtbichler]

Boyer moore bietet sich hier an: Hier mal eine Delphi-Implementierung

http://www.delphigeist.com/2010/04/b...lphi-2010.html

Wie lang ist denn die zu suchende Bytefolge?

[p80286]

Such mal hier nach Boyer Moore, da gab es for ein paar Jahren eine Diskussion über die effizentest weiterentwicklung.

Gruß
K-H

[Furtbichler]

Welcher Algorithmus (BM, BM-Horspool, KMP, Quicksearch) der beste ist, kann pauschal nicht beantwortet werden, sondern ist vielmehr abhängig von der Alphabetgröße (hier: 256 Zeichen) und vor allen Dingen von der Länge des zu suchenden Teilstückes.

BM und Derivate spielt seine Stärken bei langen Substrings und großen Alphabeten aus.

[Alter Mann]

Wie immer,

schnell und zuverlässig.

Doch leider nicht so das Richtige.
Die JsTextSearch.pas von Jens ist eine Implementierung von Boyer Moore, habe
sie an Byte angepasst, läuft auch, aber kommt unter Umständen in einen Loop und es dauert.
Mit Strings ist sie Super schnell(512MB in 3sec.).
Werde mal die Fragen aufteilen, vielleicht findet sich ja die Lösung auf eine andere Art.

Danke an Alle und ein schönes Wochenende.

[Aphton]

Ich habe die BM-Suche implementiert und bei dieser Datei (genauer hier, vorgestellt von SemperVideo) eine Suche gestartet.
Weiters habe ich das ganze per FileMapping gelöst - damit das System per Paging & Optimierungen (und was halt sonst noch so dazu gehört) da mitmischen kann.

Die Datei ist 15.696.118.781 bytes groß (14.6 GB).
Ich habe nach den letzten 7 Stellen gesucht. Das ganze hat im Schnitt um die 169 Sekunden gedauert. Dh 14.6 GB in 169 Sekunden (169136 ms) mit 7 Zeichen durchsucht.

Das wären dann 92801761 Bytes/Sek.

Im Vergleich zu deinen 512mb in 1.13 sec:
Ich habe mir 20 Bytes genau bei 512 rausgesucht und danach suchen lassen (gleiche Situation/Verhältnisse).
Die Suche hat im Schnitt 900 ms gedauert.

Falls Interesse besteht, kann ich die kleine Demo ja hochladen!

[Furtbichler]

Vorsicht, werden hier vielleicht Äpfel mit Birnen verglichen? Also vielmehr: IO vs. Cache?

Bei Dateien dieser Größe kommt es imho in erster Linie auf die Art des Einlesens an. Hier hat Sebastian Jänicke eine Textreader-Klasse mit Memory mapped files implementiert, die nach seinen Aussagen das schnellste ist, was es diesbezüglich gibt.

Ich kann mir vorstellen, das man seine Klasse auf Bytestreams anpassen kann.

Zitat von Alter Mann:

...habe sie an Byte angepasst, läuft auch, aber kommt unter Umständen in einen Loop und es dauert.
Mit Strings ist sie Super schnell(512MB in 3sec.).

Zeig mal den Code, denn ein String ist ja nichts anderes als ein Bytestream (wenn man unicode mal außen vor lässt).

[lbccaleb]

Zitat von Aphton:

... Falls Interesse besteht, kann ich die kleine Demo ja hochladen!

Also ich würd mal Intresse anmelden