Wie vergleicht man 2 sehr große Liste (>1.000.000 Einträge)



  • Hallo,
    ich will mit einem Programme eine Library ansteuern um Dateien in eine ZIP-Datei zu schreiben.

    Nun drüfeen aber aus Zeitgründen nur geänderte Dateien kopiert werden.
    Also ein incrementelles Backup.

    Dazu lesen ich aus der Ursprungsdatei alle Einträge aus.
    Eine Callback Routine wird für jede Datei aufgerufen. Ich vergleiche die Daten mit der Datei auf der Festplatte und speicher sie aktuell in eine CStringList.

    Beim starten der normalen Sicherung wird jede zu sichernde Datei vorher per Callbackup nachgefragt. Ich vergleiche sie mit der Liste. Sobald der Eintrag dort vorhanden ist, überspring ich die Datei und lösche den Eintrag in der Liste um die Größe zu reduzieren.

    Das ganze funktioniert prima mit 10tausenden Dateien. Bei 1.000.000 dauert der Abgleich aber mehr als 12 Stunden (Xeon Quad).

    Am einfachsten wäre es ja zwei Liste zu haben, diese zu sortieren und dann abzugleichen. Geht aber wegen dem Callback beim Backup nicht.

    Ich versuche Heute Abend mal eine Liste mit 128Bit MD5 zu verwenden (__int128?).

    Hat da sonst noch Jemand eine zündende Idee?

    Danke

    Stefan



  • Du könntest zumindest die Liste sortieren und dann im Callback eine binäre Suche machen. Das bringt schonmal O(log n) statt O(n). Oder machst du das schon?



  • Geht eine Überprüfung der Timestamp der Datei?



  • Darüber hinaus muss das Löschen in der Liste gar nicht so viel bringen. Das kostet nämlich auch O(n), es sei denn du nutzt den Swap-Trick, dabei geht aber die Sortierung verloren. Da musst du einfach ausprobieren, was dir am Ende mehr bringt.



  • ipsec schrieb:

    Darüber hinaus muss das Löschen in der Liste gar nicht so viel bringen. Das kostet nämlich auch O(n)

    CStringList ist eine double linked list. Hat also O(1) löschen.

    @StefanKittel: Ich würde mit einem Profile drüber fahren und schauen wo genau die Zeit verschwendet wird. uU ist das suchen der Datei in der Liste zu langwierig? uU reicht es nach timestamps der letzten Änderung der Datei zu gehen? uU ist die Reihenfolge in der die Dateien abgeklappert werden schlecht (zu hohe seek time der Platte)?

    Sobald du das weisst, kannst du viel einfacher ansetzen wo das Problem liegt.



  • @Shade: Habe den Rest des Threads nicht verfolgt, aber double-linked != löschen in O(1), um etwas zu löschen musst du dich nämlich vorher erst einmal bis zum Element hingehangelt haben.

    MfG SideWinder



  • vielleich für anregung bei rsync reinspicken?

    http://samba.anu.edu.au/rsync/download.html
    http://www.itefix.no/i2/node/10650

    oder einfach das benutzen?



  • SideWinder schrieb:

    @Shade: Habe den Rest des Threads nicht verfolgt, aber double-linked != löschen in O(1), um etwas zu löschen musst du dich nämlich vorher erst einmal bis zum Element hingehangelt haben.

    Ich wuerde das als suchen bezeichnen 😉

    Das entfernen des elements ist O(1) es zu finden kann O(N) sein, muss aber nicht. Je nachdem wie man hier vorgeht. Deshalb hab ich ja auch geschrieben dass man das finden des Elements messen soll ob uU hier das bottleneck ist.



  • Ich verstehe ehrlich gesagt nicht ganz was du jetzt für Listen hast, und was für Daten in diesen gespeichert werden?
    Nur Pfade, oder der gesamte Dateiinhalt oder ...?

    Was das Nachschlagen in einer Datenstruktur angeht: wie wär's mit einer Hash-Map?
    Das Rauslöschen kannst du dir IMO auch sparen, das sollte dann keinen grossen Unterschied mehr machen.



  • Vielen Dank für die Infos.

    Für jede Datei habe ich einen String des vollständigen Dateinamens.
    z.B.
    d:\daten\kfz\text1.doc
    d:\daten\buchhaltung\text2.doc
    d:\daten\buchhaltung\text3.doc

    Im 1. Schritt erhalte ich durch eine CallBackupRoutine jede Datei einzelnd.
    Ich prüfe diese dann auf Änderungen gegenüber dem Original auf der Festplatte. Wenn es keine Änderungen gibt füge ich den Namen der Liste hinzu.

    Im 2. Schritt werden ich vor jeder zu sichernden Datei gefragt ob ich diese Auslassen möchte. Wenn es einen Eintrag in der Liste gibt antworte ich mich ja.

    Ich habe schon versucht statt dem ganzen Namen eine MD5 Prüfsumme zu verwenden, da diese kürzer ist. Dadurch dauert das sortieren beim hinzufügen aber viel länger.

    Allein das hinzufügen im 1. Schritt dauert ca. 90 Minunten!
    Dabei sinkt die Geschwindigkeit kontinuierlich. Am Anfang ca. 10.000 Einträge so Sekunden runter auf 500 pro Sekunde.

    Gibt es sonst die Möglichkeit ein Array in dieser Größe zu nutzen?
    1.000.000 Einträge * 255 Chars = ca. 300MB. Dort kann ich einfach mal 10.000 Einträge weiterspringen.

    CSortStringList ist von CStringList abgeleitet.

    void CSortStringList::AddStringSorted(CString _AddString)
    {
    	POSITION		pos;
    	CString			currentString;
    
    	//walk the list
    	pos = GetTailPosition();
    	if (pos != NULL)
    	{
    		currentString = GetAt( pos );
    
    		//if string to add is "larger" than the last one add after
    		if (_AddString > currentString)
    		{
    			AddTail(_AddString);
    			return;
    		}
    	}
    
    	//walk the list
    	for( pos = GetHeadPosition(); pos != NULL; )
    	{
    		//get string
    		currentString = GetAt( pos );
    
    		//if string to add is "smaller" than the current insert before
    		if (_AddString < currentString)
    		{
    			InsertBefore(pos, _AddString);
    			return;
    		}
    
    		GetNext(pos);
    	}
    
    	//add string to the tail
    	AddTail(_AddString);
    }
    
    POSITION CSortStringList::FindStringSorted(CString _FindString)
    {
    	POSITION		pos;
    	CString			currentString;
    	int				compareResult;
    
    	//walk the list
    	for( pos = GetHeadPosition(); pos != NULL; )
    	{
    		//get string
    		currentString = GetAt( pos );
    
    		compareResult = currentString.CompareNoCase(_FindString);
    
    		//found?
    		if (compareResult == 0)
    			return pos;
    
    		//if string to add is "smaller" than the current abort
    		if (compareResult > 0)
    			return NULL;
    
    		GetNext(pos);
    	}
    
    	return NULL;
    }
    

    Danke für Eure Zeit

    Stefan



  • Folgende Idee: Ich erstelle pro Verzeichniss eine Liste der Dateien in diesem Verzeichniss.
    Dadurch kann ich sehr gezielt die richtigen Einträge finden.

    Aber mein Compiler mag mich nicht.
    error C2248: "CObject::CObject": Kein Zugriff auf private Member, dessen Deklaration in der CObject-Klasse erfolgte.

    Soweit ich gefunden habe gibts dafür keine Abhilfe außer CArray zu verwenden was ich mir nun anschaue.

    Oder gibts da einen Trick?

    typedef struct DirListItemTag
    {
    	CString				DirName;
    	CStringList	fileList;
    } DirListItem;
    typedef CList <DirListItem, DirListItem>	DirList;
    
    class CSortFilenameList : public CSortStringList
    {
    public:
    	DirList		m_DirList;
    
    	void AddFileNameWithDir(CString _FileNameWithDir);
    	void AddFileNameWithDir(CString _FileName, CString _DirName);
    
    	BOOL FindFileNameWithDir(CString _FileNameWithDir, BOOL _RemoveItem = FALSE);
    	BOOL FindFileNameWithDir(CString _FileName, CString _DirName, BOOL _RemoveItem = FALSE);
    
    	void Test(void);
    };
    

    Danke

    Stefan



  • Du machst dir das aber ordentlich schwer. Unnötig schwer.

    std::set sollte alles sein was du brauchst.
    Theoretisch könntest du auch CMap/CMapStringToPtr verwenden, bloss bei denen musst du die Hashtable-Grösse vorab angeben (kann nachträglich nicht mehr geändert werden!), und wenn die zu klein ist (Default = 17!) dann werden sie langsam! Bäh!
    (ja, einself, ich weiss, ich schäme mich eh schon)

    Alternativ könntest du std::unordered_set verwenden, wenn du mit VC10 arbeitest (oder auch boost::unordered_set oder die Non-Standard Set Klassen von VC7+).

    Mal ein kleiner Test mit std::set:

    #include "stdafx.h"
    
    #include <afx.h>
    #include <afxwin.h>
    #include <set>
    
    CWinApp theApp;
    
    CString NormalizePath(CString const& path)
    {
    	// TODO: absoluten Pfad aus "path" machen
    	CString result = path;
    	result.MakeLower();
    	return result;
    }
    
    class MyList
    {
    public:
    	MyList::MyList()
    		: m_counter(0)
    	{
    	}
    
    	void AddDirectory(CString const& path)
    	{
    		CStringArray subdirs;
    
    		CFileFind ff;
    		BOOL run = ff.FindFile(path + _T("\\*.*"));
    		while (run)
    		{
    			run = ff.FindNextFile();
    
    			if (ff.IsDots())
    				continue;
    			else if (ff.IsDirectory())
     				subdirs.Add(ff.GetFilePath());
    			else
    				AddFile(ff.GetFilePath());
    		}
    
    		ff.Close();
    
     		for (INT_PTR i = 0; i < subdirs.GetSize(); i++)
     			AddDirectory(subdirs.GetAt(i));
    	}
    
    	void AddFile(CString const& path)
    	{
    		CString normPath = NormalizePath(path);
    
    		ASSERT(m_set.find(normPath) == m_set.end());
    		m_set.insert(normPath);
    
    		m_counter++;
    
    		size_t const count = m_set.size();
    		ASSERT(count == m_counter);
    
    		if ((m_counter % 1000) == 1)
    		{
    			_tprintf(_T("count = %d K\n"), static_cast<int>(m_counter / 1000));
    		}
    	}
    
    	INT_PTR GetCount() const
    	{
    		return m_set.size();
    	}
    
    	int m_counter;
    	std::set<CString> m_set;
    };
    
    int main()
    {
    	MyList l;
    
    	DWORD t0 = ::GetTickCount();
    
    	l.AddDirectory(_T("C:"));
    
    	DWORD t1 = ::GetTickCount();
    
    	_tprintf(_T("file count = %d\n"), static_cast<int>(l.GetCount()));
    	_tprintf(_T("time = %d sec\n"), (t1 - t0) / 1000);
    	_tprintf(_T("bye\n"));
    	return 0;
    }
    

    Ich hab' grad keine Platte mit 1 Mio. Files drauf, aber ich hab's mal testweise gegen meine C Platte laufen lassen (Release build mit VC 2008):

    count = 0 K
    ...
    count = 253 K
    file count = 253554
    time = 6 sec
    


  • Moin,
    vielen Dank!
    Ich schaue mal wie es sich mit Live-Daten verhält.
    Stefan



  • Hallo,

    prima. Ist schon sehr viel schneller geworden.
    Allerdings ist der Speicherverbrauch sehr hoch.
    Beim Suchen sind es teilweise mehr als 2GB was zum Absturz führt.

    Ich habe es nun durch MD5 Stirngs ersetzt und nun sind es max 1.8GB.

    Kann man die Sets auch mit 128Bit DWORDs füttern?

    Danke

    Stefan



  • Es gibt keine 128Bit DOWRDs, was du meinst ist ein QWORD 🤡



  • Dann ein QWord oder DDWord?
    Irgendwas wo ich eine 128Bit MD5 speichern und vergleichen kann ohne den Umweg über einen String zu gehen.
    Stefan



  • @314159265358979:
    Ein QWORD unter Windows hat 64 Bit (keine Überraschung, da ein DWORD ja 32 hat). Was er meint würde dann wohl OWORD heissen. Gibt's aber nicht.

    @StefanKittel:
    Du kannst std::set mit allem füttern, so lange es Value-Semantik hat bzw. anders gesagt: die Bedingungen erfüllt.

    z.B. sowas:

    struct Thing
    {
        DWORD parts[4];
    };
    
    // operator < definieren damit std::set (std::less) funktioniert
    bool operator < (Thing const& lhs, Thing const& rhs)
    {
        for (int i = 3; i >= 0; i--) // EDIT: hier stand > 0 was natürlich Blödsinn ist. Rückwärts zählende Schleifen sind einfach wider die Natur :^)
            if (lhs.parts[i] < rhs.parts[i]) //EDIT: muaha, nochmehr Unfug korrigiert
                return true;
            else if (lhs.parts[i] > rhs.parts[i])
                return false;
    
        return false;
    }
    

    BTW: 64 Bit und viel Speicher hilft auch gut 😉

    EDIT: @StefanKittel: ich hoffe die offensichtlichen Fehler in meinem Code waren nicht zu verwirrend. Was gemeint war war aber hoffentlich klar 🙂 (Ich weiss auch nicht ob jetzt alles passt, hab's nicht ausprobiert, hihi)



  • Danke!



  • hustbaer schrieb:

    @314159265358979:
    Ein QWORD unter Windows hat 64 Bit (keine Überraschung, da ein DWORD ja 32 hat). Was er meint würde dann wohl OWORD heissen. Gibt's aber nicht.

    Natürlich, richtig, mein Fehler.


Anmelden zum Antworten