Schnellster Such Algorithmus für File in C#

[Marc (Gast)]

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

[guru (Gast)]

Dann würde ich das nicht in C machen. Es gibt Hardwarebefehle für die 
80x86 cpu die das sehr schnell erledigen.

[bluppdidupp (Gast)]

Nimm den StreamReader

[Simon K. (simon)]

guru wrote:
> Dann würde ich das nicht in C machen. Es gibt Hardwarebefehle für die
> 80x86 cpu die das sehr schnell erledigen.

Also Assembler? ;)

[Sven P. (Gast)]

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

[Simon K. (simon)]

Wo ist das Problem ein bisschen zu googlen?
http://www.google.de/search?q=c%23+search+replace
http://www.google.de/search?q=c%23+file+search

[yalu (Gast)]

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.

[Hans (Gast)]

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.)

[Sven P. (Gast)]

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.

[Anton M. (amr2100)]

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

[Hans (Gast)]

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.

[Arc N. (arc)]

Hier gibt's ein schönes Paper zu verschiedenen Suchalgorithmen
http://macedonia.uom.gr/~panosm/pdfs/jpaper001.pdf
(ab Seite 7 werden die Vor- und Nachteile der einzelnen Algorithmen 
aufgeführt).

Neben den genannten Optimierungen des Algorithmus, kann man das ganze 
auch sehr schön Parallelisieren...

[Andreas S. (andreas) (Admin)]

Einfach blockweise laden und mit Standard-Funktionen zu suchen wird 
reichen um die Festplatte voll auszulasten. Den Suchalgorithmus zu 
optimieren dürfte nicht viel bringen.