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,3

    lade 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 lesen

    beide methoden sind sehr langsam
    bei der 2. wird logischerweise mehr speicher benutzt

    die 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 gesammelt

    Das 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 werden

    noch 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 voll

    gibt 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" probieren

    thx



  • 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 sparen

    hier mal mein code
    bin nicht sicher ob ich cmap richtig anwende

    CMapStringToString 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();
    

Anmelden zum Antworten