mikrocontroller.net

Forum: PC-Programmierung Schnellster Such Algorithmus für File in C#


Autor: Marc (Gast)
Datum:

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

Autor: guru (Gast)
Datum:

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

Autor: bluppdidupp (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nimm den StreamReader

Autor: Simon K. (simon) Benutzerseite
Datum:

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

Autor: Sven P. (haku) Benutzerseite
Datum:

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

Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert

Autor: yalu (Gast)
Datum:

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

Autor: Hans (Gast)
Datum:

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

Autor: Sven P. (haku) Benutzerseite
Datum:

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

Autor: Anton Messerer (amr2100)
Datum:

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

Autor: Hans (Gast)
Datum:

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

Autor: Arc Net (arc)
Datum:

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

Autor: Andreas Schwarz (andreas) (Admin) Benutzerseite Flattr this
Datum:

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

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.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

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