Schnellster Such Algorithmus für File in C#

Marc Gast #891149
Lesenswert?
• ▲
▼ 
Hallo Leute

ich bin auf der Suche nach einem Schnelleren(schnellsten) 
Suchalgorithmus der ein File nach einem String durchsucht als :

String name="hallo";

string[] fileInhalt = File.ReadAllLines(text.txt);

foreach (string str in fileInhalt)
{

    if(str.Contains(hallo)){
                            //tue irgendwas
                            }
}

in C#! Kann man das noch schneller hinkriegen?oder ist das schon das 
Maximum?
Es geht um performance da mein Programm nicht nur eine Datei durchsucht 
sonder einige GigaByte!

Grüße
Hilbert
Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Beitrag melden
Sven P. Gast #891193
Lesenswert?
• ▲
▼ 
Inline-Assembler^^ Wenns im Speicher liegt, dann gibts in der Tat 
ASM-Instruktionen, die einen Speicherblock zumindest nach einem Zeichen 
durchsuchen.
Solls hardcore auf der Festplatte sein, dann würd ich das vermutlich in 
C schreiben, ist dann irgendwo immer noch die schnellste Variante, zumal 
bei echtem C kein Zwischenkompiler drinnesteckt, der alles und jeden 
erstmal überprüft g
Antwort Zitieren Bearbeiten Löschen Beitrag melden
yalu Gast #891210
Lesenswert?
• ▲
▼ 
Man kann für die Suche auch einen endlichen Automaten einsetzen.

Dieser hat den Vorteil, dass die benötigte Zeit unabhängig von der
Länge des zu suchenden Worts ist. Ist das Wort fest vorgegeben, kann
auch der Automat fest codiert werden. Sonst muss die Zustandsüber-
gangstabelle dynamisch generiert werden. Das kostet zwar etwas Zeit,
fällt aber in deinem Fall kaum ins Gewicht, da du ja anschließend
viele GBytes durch den einmal generierten Automaten jagst.

Ohne Zeitnachteil kann man mit endlichen Automaten auch nach regulären
Ausdrücken (also bspw. [a-z][0-9]*) suchen.

Der endliche Automat verarbeitet die Eingabe Zeichen für Zeichen. Du
benötigst also keinen Zeilenpuffer o.ä., dessen richtige
Dimensionierung oft ein Problem darstellt.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Hans Gast #891216
Lesenswert?
• ▲
▼ 
Es gibt verschiedene Algorithmen. Eine Übersicht findest Du hier:

http://de.wikipedia.org/wiki/String-Matching-Algorithmus

Der hier scheint mir ganz brauchbar:

http://de.wikipedia.org/wiki/Knuth-Morris-Pratt-Algorithmus

Man muss die gesamte Datei genau einmal einlesen (aber nur teilweise im 
Speicher behalten). Den Abschnitt der Datei, den man gerade betrachtet 
muss man nicht unbedingt naiv mit dem Suchbegriff vergleichen, sondern 
kann dies geschickter tun, um damit Zeit zu sparen.

Wenn M die Länge des Suchbegriffs ist, und N die Länge des zu 
durchsuchenden Textes, dann gibt es einen Algorithmus, der die Laufzeit 
M+N besitzt (S. A. Cook, 1970).

Ausführlich erklärt ist das z.B. im Standardwerk Algorithmen von Robert 
Sedgewick, ab S. 325. (Sollte in fast jeder größeren Bibliothek 
vorhanden sein.)
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Sven P. Gast #891217
Lesenswert?
• ▲
▼ 
Es gab doch da mal so eine Optimierung für die Sucherei, bei der man den 
Text rückwärts durchsucht hat, oder meine ich das nur?! Stand mein ich 
in "The Practice of Programming" (Pike/Richard) oder so drinne.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Anton M. #891237
Lesenswert?
• ▲
▼ 
Direkt im Speicher zu suchen ist sicherlich die schnellste Möglichkeit. 
Strings in C# sind langsam (besser StringBuilder). Eine Datei wie im 
Beispiel angegeben zu laden ist bei bei wenigen Dateien und kleinen 
Dateigrößen durchaus machbar.

Wenn viele Dateien durchsucht werden sollen könnte das Mapping von 
Dateien in den Adressraum des Prozesses helfen -> CreateFileMapping / 
MapViewOfFile (suche bei pinvoke.net danach). Das sind Funktionen der 
Win32 Programmier API. Dann kann direkt ein Bereich des Hauptspeichers 
durchsucht werden
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Hans Gast #891254
Lesenswert?
• ▲
▼ 
Evtl. kann man den Datenbestand auch Indexieren. Sucht man z.B. in 
WinAMP nach einem Lied, wird nicht die gesamte Sammlung durchsucht, 
sondern nur der Index. Den einmaligen Aufwand, einen Index zu erstellen, 
hat man trotzdem. Aber die Suche geht schneller.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Thread beobachten

Antwort schreiben

Bitte melde dich an, um einen Beitrag zu schreiben.

Bestehender Account

oder

Mit Google-Account einloggen

Noch kein Account?

Die Registrierung ist kostenlos und dauert nur eine Minute.

Jetzt registrieren