Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 | Suche | FAQ

Hauptmenü
myCSharp.de
» Startseite
» Forum
» Suche
» Regeln
» Wie poste ich richtig?

Mitglieder
» Liste / Suche
» Wer ist online?

Ressourcen
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Microsoft Docs

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

Brauche Rat beim Durchsuchen von großen Binärdateien nach bestimmten Strings
Tanari
myCSharp.de - Member



Dabei seit:
Beiträge: 4

Themenstarter:

Brauche Rat beim Durchsuchen von großen Binärdateien nach bestimmten Strings

beantworten | zitieren | melden

Hallo Zusammen,

Würde gerne euren Rat hören zu folgender Sache:

Ich muss mehrere Pcap Dateien durchsuchen (Gesamtgröße geht in die Terrabyte) nach User-Agent Strings (z.B. "Mozilla/5.0 (Windows NT 6.1; WOW64; rv:7.0.1) Gecko/20100101 Firefox/7.0.1"). Diese Strings werden in den Dateien immer mit \r\n abgeschlossen. Ich möchte alle vorkommenden User-Agents sichern
, jedoch Duplikate verhindern.

Ich verfolge dabei den Ansatz die Pcap-Datei jeweils komplett einzulesen, in einer String-Variable zu speichern und anschliessend zu nach "\r\n" zu splitten.


// List for User Agents
        private List<String> userAgents = new List<String>();
...

string[] stringSeparators = new String[] { "\r\n" };
            string data;
            using (StreamReader sr = new StreamReader(dataFile))
                data = sr.ReadToEnd();
            dataStrings = data.Split(stringSeparators, StringSplitOptions.RemoveEmptyEntries);

            foreach (string s in dataStrings)
            {
                // found user-agent string?
                if (s.StartsWith("User-Agent:"))
                {
                    if (!userAgents.Contains(s.Substring(12)))
                        userAgents.Add(s.Substring(12));
                }

                if (GlobalVariables.StopThread)
                    return;
            }

Hier gibt es bestimmt einen eleganteren Ansatz.
Kann mir jemand einen nennen?
private Nachricht | Beiträge des Benutzers
Seikilos
myCSharp.de - Member



Dabei seit:
Beiträge: 759

beantworten | zitieren | melden

Funktioniert deine Lösung nicht, ist sie zu langsam?

Was ist Elegant? Schneller, speicher-effizienter?

Dein Frage ist zu unkonkret.

Mögliche Ansätze:
Du brauchst nicht die ganze Datei auf einmal einlesen sondern kannst es zeilenweise machen.

Desweiteren könntest du ein Dictionary<string,int> benutzen, dann müsstest du dich nicht über das contains kümmern und könntest z.B. zählen, wie oft der jeweilige User-Agent drin war
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Seikilos am .
Life is a short
private Nachricht | Beiträge des Benutzers
Tanari
myCSharp.de - Member



Dabei seit:
Beiträge: 4

Themenstarter:

beantworten | zitieren | melden

Hallo Seikilos,

vielen Dank für deine Antwort. Mir geht es darum die Schnelligkeit des Programmes zu erhöhen, es werden Datenmengen im Terrabytebereich verarbeitet.

Der Ansatz Dictionary<string,int> ist auf jeden Fall eine sehr gute Idee! Werde mich gleich mal an die Umsetzung wagen
Vielen Dank hierfür!
private Nachricht | Beiträge des Benutzers
Matthias Lauth
myCSharp.de - Member

Avatar #avatar-3344.gif


Dabei seit:
Beiträge: 50
Herkunft: DE

beantworten | zitieren | melden

Zum lesen: Ich würde es Zeilenweise machen, so hast Du z.B. die Möglichkeit eine Statusanzeige zu implementieren XX.XXX Zeilen Durchsucht oder sowas.

Zum suchen: Schreib die Methode lieber selbst. Boyer-Moore-Algorithmus dürfte passen. Hier ein Beispiel: Boyer-Moore DotNetPerls
Zitat von Tanari
Der Ansatz Dictionary<string,int> ist auf jeden Fall eine sehr gute Idee! Werde mich gleich mal an die Umsetzung wagen :)

Instinktiv würd ich das nicht on the fly machen sondern erstmal alle wegschreiben und nachher ein group by nachsetzen. Edit: Das ist blödsinn.
Dieser Beitrag wurde 4 mal editiert, zum letzten Mal von Matthias Lauth am .
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo Tanari,

bei Terrabytes würde File.ReadAllLines vermutlich genauso wie StreamReader.ReadToEnd den Hauptspeicher sprengen. Aber ich wüsste nicht, was gegen StreamReader.ReadLine spricht. Splitten muss und sollte man jedenfalls nicht.

Ich gehe davon aus, dass das Einlesen der Daten von der Platte der Flaschenhals ist. Daher stände der Programmieraufwand für Boyer-Moore wohl nicht im Verhältnis zum Nutzen.

List<String> userAgents solltest du allerdings besser durch HashSet<String> ersetzen. Und natürlich geht es damit genauso wie mit dem Dictionary<> gut "on the fly". Erstmal alles wegzuschreiben halte ich nicht nur für unnötig, sondern auch für unnötig aufwändig.

herbivore
private Nachricht | Beiträge des Benutzers
Seikilos
myCSharp.de - Member



Dabei seit:
Beiträge: 759

beantworten | zitieren | melden

Uuuh, HashSet, wo warst du mein Leben lang! :D

@Mathias Lauth: Was spricht gegen eine implizite Filterung von redundanten Einträgen durch Dictionary oder HashSet?

Ich stimme überein, dass man ein Problem nach dem anderen lösen sollte, aber hier fällt die Filterung ja quasi "kostenlos" nebenbei heraus.

Mich würde jedoch interessieren, wie sich Boyer-Moore zum StartsWith verhält
Life is a short
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo Seikilos,

StartsWith ist - gerade bei langen Strings - natürlich deutlich schneller als Boyer-Moore, weil StartWith nur am Anfang sucht. Aber wenn man Boyer-Moore verwenden würde, dann würde man gar nicht zeilenweise arbeiten, sondern könnte im Gesamt-String oder in größeren Blöcken davon möglicht schnell die Stellen finden, die mit User-Agent beginnen. Dabei arbeitet Boyer-Moore um so schneller, je länger der zu suchende String ist, weil dann gar nicht jedes Zeichen geprüft werden muss, sondern immer wieder Teile des zu durchsuchenden Strings übersprungen werden, weil klar ist, dass in diesem Teilen der gesuchte String nicht vorkommen kann. Genaueres in Boyer-Moore-Algorithmus.

herbivore
private Nachricht | Beiträge des Benutzers
Matthias Lauth
myCSharp.de - Member

Avatar #avatar-3344.gif


Dabei seit:
Beiträge: 50
Herkunft: DE

beantworten | zitieren | melden

Zitat von Seikilos
@Mathias Lauth: Was spricht gegen eine implizite Filterung von redundanten Einträgen durch Dictionary oder HashSet?

Offenbar nichts. Ich hatte vermutet (deswegen das Wort instinktiv), dass die ContainsKey Methode eine Laufzeit von mehr als O(1) hat, dass trifft aber nicht zu.
private Nachricht | Beiträge des Benutzers
Seikilos
myCSharp.de - Member



Dabei seit:
Beiträge: 759

beantworten | zitieren | melden

Wenn er jedoch wirklich große Mengen an Daten liest, müsste er nicht zeilenweise, sondern in Chunks die Daten lesen.

Wäre interessant, bei welcher Chunk Größe Boyer-Moore StartsWith überholen würde
Life is a short
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo Matthias Lauth,

beim HashSet muss man nicht mal Contains abfragen, sondern kann einfach ungeprüft Add verwenden. Ist der Eintrag schon vorhanden, wird er - automatisch - nicht neu hinzugefügt. Auch Add hat O(1).


Hallo Seikilos,

wie schon gesagt, wird der Flaschenhals das Einlesen sein. Spätestens wenn man das Durchsuchen auf einem Multicore-System in einen anderen Thread packt als das Einlesen, wird es von der Gesamtlaufzeit keinen Unterschied machen, ob man den String linear durchsucht oder mit Boyer-Moore. Selbst wenn man Einlesen und Durchsuchen in einem einzigen Thread durchführt, werden die Laufzeitunterschiede vermutlich minimal sein. Oder mit anderen Worten: "premature optimization is the root of all evil".

herbivore
private Nachricht | Beiträge des Benutzers
Tanari
myCSharp.de - Member



Dabei seit:
Beiträge: 4

Themenstarter:

beantworten | zitieren | melden

Hallo Zusammen!

viele Dank für die rege Teilnahme! Ich habe jetzt alle List<String> auf HashSet<String> umgestellt und mal die Performance verglichen.

für die Verarbeitung von 52 Pcap-Dateien (insg. 2 GB) benötigt das Programm (inkl. parsen der User-Agents) auf einem i5 Prozessor mit 8GB Ram ziemlich genau 2 Minuten. Durch die Nutzung von HashSet<String> habe ich wie es scheint insg. ca 5 Sekunden gewonnen.

Wie setze ich es jetzt aber um das ich zu dem jeweiligen User-Agent String auch eine Anzahl speichere? Kann mir da jemand weiterhelfen?
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo Tanari,

das wurde doch schon beantwortet: Mit einem Dictionary<String, int>.

Wir sollten aufpassen, dass der Thread nicht vollends nach [Hinweis] Wie poste ich richtig? Punkt 1.1.1 abgleitet.

herbivore
private Nachricht | Beiträge des Benutzers
Tanari
myCSharp.de - Member



Dabei seit:
Beiträge: 4

Themenstarter:

beantworten | zitieren | melden

Hallo herbivore,

sorry für meine Unkenntnis, aber kann ich Dictonary mit HashSet anstatt String kombinieren?

Danke!
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Tanari am .
private Nachricht | Beiträge des Benutzers
Seikilos
myCSharp.de - Member



Dabei seit:
Beiträge: 759

beantworten | zitieren | melden

Dictionary ist eine Art HashSet, bei dem zu jedem Hash Key ein Value zugewiesen wird.
Du brauchst also nur Dictionary<string, int>

Konkrete Antwort auf die Frage: Ja, da es generisch ist, kannst du auch Dictionary<HashSet<string>, int> schreiben, macht aber keinen Sinn.
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von Seikilos am .
Life is a short
private Nachricht | Beiträge des Benutzers
ujr
myCSharp.de - Experte



Dabei seit:
Beiträge: 1770

beantworten | zitieren | melden

Zitat von Tanari
Durch die Nutzung von HashSet<String> habe ich wie es scheint insg. ca 5 Sekunden gewonnen.

Da das Lesen von der Platte der Flaschenhals sein sollte, ist es sinnvoll, anstatt StreamReader einen BufferedReader (edit: heißt korrekt BufferedStream) oder einen FileStream mit Puffer zu verwenden.

Was Dictionary/HashSet angeht - schau einfach mal in die Doku!
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von ujr am .
private Nachricht | Beiträge des Benutzers

Moderationshinweis von herbivore (09.03.2012 - 10:32:29):

Nun ist es - trotz meiner Warnung - leider (und wie ich finde vollkommen unnötigerweise) doch passiert. Die letzte Nachfrage hättest du dir und uns wirklich sparen können und müssen. Bitte beachte in Zukunft [Hinweis] Wie poste ich richtig? Punkt 1.1.1 und 1.1. Ich finde es besonders ärgerlich, wenn der Bogen nach schon ausführlich erfolgter und zielführender Hilfe und trotz entsprechender Warnung am Ende doch so überspannt wird. Dabei hätte es vermutlich schon gereicht, sich mehr als <6 Minuten nachdenken zu gönnen. In der Zeit kannst es gar nicht vernünftig selbst versucht haben. Bitte etwas mehr Eigeninitiative.