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

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

  • S

    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

    0
  • S

    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

    0

  • 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
    0
  • S

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

    0
  • S

    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

    0
  • 3

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

    0
  • S

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

    0

  • @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)

    0
  • S

    Danke!

    0
  • 3

    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.

    0
Anmelden zum Antworten