fragen zu geschwindigkeit (algorithmen)
-
hallo
also ich habe folgendes problem.
ich habe 2 textdateien.
jede hat ein wort pro zeile.ich muss jede zeile von der ersten datei mit jeder zeile der zweiten vergleichen
und dann soll jede zeile der ersten datei (welche nicht in der zweiten enthalten ist) in eine dritte datei geschrieben werden.habe 2 unterschiedliche methoden probiert.
das problem ist jedoch ,dass beide dateien 50 mb gross sind .öffne datei 1
öffne datei 2
for (i=0;i<zeilenanzahl datei 1;++i)
{
for (n=0;n<zeilenanzahl datei 2;++n)
{falls datei 1[i]!=2[n] schreibe 1[i] in 3}}
schliesse datei 1,2,3lade datei 1 in cstringarray
schliesse datei 1
lade datei 2 in cstringarray
schliesse datei 2
danach wie bei der 1. methode
vergleiche nur die arrays anstatt in den dateien zu lesenbeide methoden sind sehr langsam
bei der 2. wird logischerweise mehr speicher benutztdie methode mit dem array müsste wohl deutlich schneller sein
weiss jemand ob es noch andere möglichkeiten gibt ?
vielleicht einen sortieralgorithmus?und bringt es mehr speed wenn ich z.b. warte bis ich 1000 strings zusammen
habe um in datei3 zu schreiben
oder sollte ich jeden einzelnen string sofort in datei3 schreiben?danke für die hilfe
-
(1) Du hast ja keine echten algorithmischen Unterschiede (und ich denk was besseres ist auch nicht möglich), nur der Ablauf ändert sich. Für optimierungen muß mal also die "algoruthmische Abstraktion" hinter sich lassen, und sich die "Ausführende Maschine" (hardware+OS) ansehen. Da gibt es immer noch eine menge generische optimierungen.
(2) Profiler! Immer erst messen, dann optimieren.
Ist allerdings bei solchen Operationen schwer, da die Zeiten eines Einzelschritts stark variieren.Naheliegend sind:
- größere Blöcke lesen (nicht zeilenweise, Zeilenenden selbst parsen)
- größere Blöcke schreiben (bringt OS-abhängig nicht ganz so viel)
- möglichst wenig Allokationen+Kopie beim parsen/vergleichen(3) Die "schnellste" Methode, die mir so einfällt ist plattformspezifisch und sieht in etwas so aus:
(a) Erzeuge File Mapping auf File 1 und 2, FILE_FLAG_SEQUENTIAL beim öffnen
(b) Verwende einen inplace-parser
(c) sammle die Daten für File 3 im Speicher (grow by power of two) und schreibe gesammeltDas ist aber schrecklich unportabel und aufwendig. Vermeidet Allokationen und Kopien, hauptsächlich, um das Working Set runterzutrimmen. Speicherzugriffe sind auf heutigen Platformen *der* Flaschenhals.
-
wäre es vieleicht ratsamer
alle doppelten einträge in ein cstringarray zu schreiben und diese dann
aus der ersten datei zu löschen ?
oder bringt die verwendung eines vektors anstatt cstringarrays vielleicht geschwindigkeitsvorteile?
-
(1) in einer Textdatei zu löschen ist nicht ganz einfach, und kaum schneller als die Datei neu aufzubauen (höchstens bei kleinen Dateien, wo sich's eh nicht lohnt)
Ist natürlich eine frage der äußeren Anforderungen - darfst du eine neue Datei schreiben? Ist der Plattenplatz knapp?
(2) vector oder CStringArray sollten sich hier nicht viel nehmen.
Mein Gefühl: Die meiste Zeit wird eh für Dateizugriffe draufgehen, dann . Allokationen und Vergleiche.
-
@peterchen
plattenplatz ist kein problem
und neue dateien dürfen auch erstellt werdennoch eine sache ist mir aufgefallen
im moment habe ich den arbeitsthread so programmiert,
dass er jeden eintrag sofort speichert (ins file) falls die zeile nicht doppelt ist
jedoch speichert er sogut wie gar nichts während der arbeitsthread arbeitet
und der speicher läuft vollgibt es eine methode das speichern zu erzwingen?
oder sollte dies ein anderer thread ausführen ,da der arbeitsthread die cpunutzung auf 100% schraubt?
-
Was nimmst du für den Dateizugriff? CFile?
Womit splittest Du in einzelne Zeilen?
Am besten du postest mal etwas Pseudocode (inkl. der Klassen/API's die du verwendest)Der zweite Thread lohnt sich normalerweise nicht, das System kümmert sich selbst drum (schreiben in Datei-Cache, und ein Systemthread schreibt lazy auf die Platte)
Das kann man natürlich umgehen (CFile::Flush() / FlushFileBuffers(HANDLE), oder CreatFile: FILE_FLAG_WRITE_THROUGH) macht das ganze aber eher langsamer.
-
Wenn die Einträge in den Dateien eindeutig sind, kannst du ein Map verwenden. (Edit - Geht auch, wenn sie nicht eindeutig sind, aber dann bekommst du jeden nicht vorhandenen Eintrag auch nur einmal in die Datei3. Aber ich schätze, das ist auch was du willst)
Das ist ziemlich schnell. Die Einträge aus Datei2 prüfst du dann "on-the-fly" ab ohne in ein Array zwischenzuspeichern. Immer wenn der Eintrag nicht im Map der Datei1 vorhanden ist, schreibst du die Zeile in Datei3.
Ach ja, und probier mal die Klasse CStdioFile aus, die ist einfacher zu handhaben und möglicherweise auch schneller.Pseudocode:
Datei1.Open() while (!Datei1.EOF()) { Map.SetAt(Datei1.ReadString()); } Datei1.Close(); Datei3.Open(); Datei2.Open(); while (!Datei2.EOF()) { CString Zeile = Datei2.ReadString(); if (!Map.LookUp(Zeile)) Datei3.WriteString(Zeile); } Datei2.Close(); Datei3.Close();
-
*ups* die doppelschleife im ersten Post hab ich übersehen
-
danke !
sieht gut aus
werde das mal aus probieren
habe schon cstdiofile benutzt
aber habe mir gedacht wenn ich die daten im array habe
lassen sie sich schneller prüfen
werd es nochmal "onthefly" probierenthx
-
Interessant wäre vielleicht wenn du mal jede Methode die du bisher ausprobiert hast mit einem Timer misst und uns hier das Ergebnis zeigst, so kann man vielleicht was draus schliessen.
-
hab es einmal mit map probiert
aber war das erste mal das ich map benutzt habe
es dauert recht lange die maptabelle zu erstellen
was aber daran liegen könnte ,dass ich vom file 2 nur den werte
nach einen "." filtere und in file 1 dann nur die werte vor dem "."aber wenn sie erst einmal erstellt ist
läuft es superschnell (kein vergleich zu den 2 for-schleifen)
und mässige speichernutzung thx!!gibt es eine möglichkeit nicht nur exakte werte
sondern auch teilwerte zu finden ?
(z.B in map asd.123 und ich suche nach 123 )
dann könnte ich mir das filtern sparenhier mal mein code
bin nicht sicher ob ich cmap richtig anwendeCMapStringToString myMap; CString null="NULL"; CString content; while( Datei1.ReadString(Zeile1) || (! Zeile1.IsEmpty())) { stelle1=Zeile1.Find('.'); myMap.SetAt(Zeile1.Left(stelle1), (null)); } Datei1.Close(); while( Datei2.ReadString(Zeile2) || (! Zeile2.IsEmpty())) { stelle2=Zeile2.Find('.'); content=sZeile2.Mid(stelle2+1); if (!myMap.Lookup(content,null)) {Datei3.WriteString(Zeile2+"\r\n");} } Datei2.Close(); Datei3.Close();