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

Log in to reply