grosse Datenmengen - wie in der App halten?

[Smitty]

Moinsn,

wie würdet ihr grössere Datenmengen in einer App im Speicher halten?
Daten pro Eintrag: long, long, int, CString, CString

Momentan habe ich dafür ein struct, das in einen std::vector kommt. Die Anzahl der Einträge kann - und wird hin und wieder auch - grösser 200.000 sein.
Angezeigt weden die Daten( müssen nicht alle sein! ) in einem virtuellen CListCtrl. Bis hierher funktioniert alles bestens.
Aber wenn die Daten dann mal sortiert werden müssen bricht die blanke Panik aus. Bei ca 102.000 Einträgen dauert das sortieren schon mal mehr als 70 Minuten

habe testweise mal die Daten( hier CString ) in einen eigenen std::vector<CString> gewuchtet, den dann mit seiner eigenen sort sortiert. Bis hierher ohne spürbare Zeitverluste. Dann müssen die Daten aber wieder 'zusammengeführt' werden, sprich in aktueller Reihenfolge zurück in vector. Das bedeutet Kaffeepause. Aber nicht nur trinken, sonder auch noch Zeit Kaffee anzubauen und zu ernten

Also: Gibt es eine performantere Lösung? Antwort: Ja. Frage: welche?

Ne Loide, mir fällt nix mehr ein. Was ich brauche, ist eine

Ich bin schon gross, ich bewältige auch viele Antworten

thx & grüssle

[CStoll]

Das zeitaufwendigste am Sortieren dürfte wohl das ständige Umkopieren der Daten sein (speziell der CString's), eventuell könntest du das eliminieren, indem du zwei Container verwendest - in einem vector<data> liegen die Einträge ungeordnet, in einem vector<int> stehen Indizes auf den ersten vector<> (passend sortiert). Oder du packst die Daten gleich in eine (multi)set<>.

[Martin Richter]

Wie sortierst Du denn?

[Smitty]

Offensichtlich nicht schnell genug

Hole eben den entsprechenden Eintrag( ListCtrl hat 3 Spalten ) aus dem struct und vergleiche. Den Algo hab ich von hier: http://www.codeguru.com/cpp/controls/listview/sorting/article.php/c975/ angepasst an meine vector/struct Bedürfnisse. Was ausserdem noch ewig dauert ist eben das Problem, die ganze struct mitzuziehen, also bei PosWechsel im vector.

Oder gibt es eine direkte Sort Möglichkeit im Virtual CListCtrl? Da hier aber immer nur die 'sichtbaren' Einträge in der Liste stehen ???

grüssle

Edit: Schei** Komma am Linkende

[Martin Richter]

1. Warum verwendest Du kein virtuelles ClistCtrl und hältst die Daten selber vor.
2. Wenn das CListCtrl die Daten sortieren soll, ist jedesmal eine Nachricht fällig um zwei Items zu vergleichen, das ist natürlich extrem. Fang den Sortierbefehl ab (den Column-Klick) sortiere Deine interne Liste neu und wenn Du eine virtuelles List Ctrl verwendest war es das schon...

[Smitty]

aber isch abe doch ein virtuelles CListCtrl, Signore

nö, die doppelte datenhaltung muss sein, weil ich, wie weiter oben geschrieben, evtl. nur einen Teil der Daten im listCtrl anzeigen muss. Die Daten können dann geändert werden( Edits unter ListCtrl, die im listCtrl ausgewählten Texte werden in den Edits angezeigt ) und die geschriebene Datei mit Änderungen soll vom Aufbau aussehen wie die Originaldatei. Bsp. Datei kann XML sein, angezeigt werden aber nur die Texte.

Schief geht beim sortieren der hier:

void CFileReaderView::OnColumnclickList1(NMHDR* pNMHDR, LRESULT* pResult) 
{
	DWORD dwStart = GetTickCount();
	DWORD dwEnde;
	DWORD dwDauer;

	NM_LISTVIEW* pNMListView = (NM_LISTVIEW*)pNMHDR;

	if (pNMListView->iSubItem == m_SortInfo.nColumnNo)
		m_SortInfo.nAscendingSortOrder = !m_SortInfo.nAscendingSortOrder;
	else
		m_SortInfo.nAscendingSortOrder = TRUE;

	m_SortInfo.nColumnNo = pNMListView->iSubItem;
	m_SortInfo.pListControl = &m_listCtrl;

	m_listCtrl.SortItems( SortList,(DWORD)&m_SortInfo );  // hier steigt er aus ...

	dwEnde = GetTickCount();
	dwDauer = dwEnde - dwStart;
	*pResult = 0;
}

... und dann kommt das:

_AFXCMN_INLINE BOOL CListCtrl::SortItems(PFNLVCOMPARE pfnCompare, DWORD dwData)
	{ ASSERT(::IsWindow(m_hWnd)); ASSERT((GetStyle() & LVS_OWNERDATA)==0); return (BOOL) ::SendMessage(m_hWnd, LVM_SORTITEMS, dwData, (LPARAM)pfnCompare); }

Mit einer normalen CListCtrl hab ich dieses Problem nicht.

grüssle

Edit: Die Datenhaltung hat nix mit dem ListCtrl zu tun. Es würde also reichen, das ListCtrl zu sortieren. Der Rest ist dann eine Kleinigkeit.

[sri]

SortItems wird von einem virtuellen CListCtrl nicht unterstützt.

[Martin Richter]

Wenn es eine virtuelle Liste ist, dan kannst Du doch Deinen Container einfach sortieren und ein Invalidate machen. That's all.

[Smitty]

sri schrieb:

SortItems wird von einem virtuellen CListCtrl nicht unterstützt.

soweit bin ich mittlerweile auch. Ist zwar schnell, aber nicht grade üppig mit Funktionen ausgestattet

Martin Richter schrieb:

Wenn es eine virtuelle Liste ist, dan kannst Du doch Deinen Container einfach sortieren und ein Invalidate machen. That's all.

Und genau hier liegt mein Problem: Den Contaimer sortieren. Dauert eben ziemlich lange, durch den vector zu gehen, one by one, den benötigten Wert aus der jeweiligen struct zu holen, zu vergleichen, die struct neu im vector zu positionieren, ...
Deswegen auch die Frage nach einer performanteren Datenhaltung. Mal sehen, ob sich beim sortieren zeitmässig noch was rausholen lässt

jedenfalls erstmal ein :xmas1: Danke an alle

grüssle

[CStoll]

Hast du ein Kriterium, nach dem du sortieren willst, oder mehrere, zwischen denen du (auf Knopfdruck) wechseln kannst? Im ersten Fall könntest du ein set<> verwenden (hält die Elemente permanent sortiert), im letzten Fall eine list<> (deren eingebaute sort()-Methode kommt ohne Kopieren aus).

Btw, und im Zweifelsfall sind die Sortier-Algorithmen der STL (std::sort(), std::stable_sort() etc) häufig noch schneller als eine handgeschriebene Variante.

[Martin Richter]

@smitty: Wie sortierst Du denn bitte? BubbleSort. Direktes Einfügen?
Zeigt mal bitte Code.

Warum verwendest Du nicht vector::sort?

[Smitty]

Moin ihr Frühaufsteher

Ja ne, is klar

@CStoll:

Sortieren nach: 3 Spalten, 1 x long, 2 x CString, auf / absteigend, je nach vorheriger Sortierung.

@Martin:

Das Problem ist wie schon gesagt das mitziehen der structs im vectot.
std::sort( bzw. vector::sort ) hatte ich schon.

habe testweise mal die Daten( hier CString ) in einen eigenen std::vector<CString> gewuchtet, den dann mit seiner eigenen sort sortiert. Bis hierher ohne spürbare Zeitverluste. Dann müssen die Daten aber wieder 'zusammengeführt' werden, sprich in aktueller Reihenfolge zurück in vector. Das bedeutet Kaffeepause. Aber nicht nur trinken, sonder auch noch Zeit Kaffee anzubauen und zu ernten

ausserdem habe ich keine Lösung bei std::sort für die Behandlung von Umlauten gefunden. Schnell ist der schon.

Code Marsch!

int iChk1, iChk2;

	int wg = lstVect.size();

	std::vector<LCSTRUCT>::iterator tmxIter;
	std::vector<LCSTRUCT>::iterator tmpIter;

	for( tmxIter = lstVect.begin(); tmxIter != lstVect.end(); tmxIter++ )
	{
		lstStruct = *tmxIter;
		tmpIter = tmxIter;
		tmpIter++;
		if( col == 0 )
		{
			iChk1 = lstStruct.vNmbr;
			if( tmpIter != lstVect.end() )
			{
				srtStruct = *tmpIter;
				iChk2 = srtStruct.vNmbr;
			}
			else
				continue;
			if( up )
			{
				while( iChk1 > iChk2 )
				{
					if( tmpIter != lstVect.end() )
						std::iter_swap( tmpIter, tmxIter );

					tmpIter++;
					if( tmpIter != lstVect.end() )
					{
						srtStruct = *tmpIter;
						iChk2 = srtStruct.vNmbr;
					}
					else
						break;
				}
			}
			else
			{
				while( iChk1 < iChk2 )
				{
					if( tmpIter != lstVect.end() )
						std::iter_swap( tmxIter, tmpIter );

					tmpIter++;
					if( tmpIter != lstVect.end() )
					{
						srtStruct = *tmpIter;
						iChk2 = srtStruct.vNmbr;
					}
					else
						break;
				}
			}

		}
	}

Das ist Spalte 1( Zahl ). Nur mal zu Bsp.

grüssle

[CStoll]

Smitty schrieb:

Das Problem ist wie schon gesagt das mitziehen der structs im vectot.
std::sort( bzw. vector::sort ) hatte ich schon.

Ich wußte gar nicht, daß vector<> eine sort-Methode mitliefert

ausserdem habe ich keine Lösung bei std::sort für die Behandlung von Umlauten gefunden. Schnell ist der schon.

Du mußt dir für jede deiner Sortierfolgen eine eine eigene Vergleichsfunktion schreiben, die auf die jeweiligen Eigenheiten eingeht - der normale String-Vergleich arbeitet mit den ASCII-Werten, dadurch landen Umlaute üblicherweise am Ende der Liste.

(wenn du die Umlaute im Alphabet einschieben willst, mußt du eine eigene Vergleichsfunktion schreiben - oder ein deutsches Locale zum Vergleichen verwenden)

PS: Wo hast du denn diesen Sortieralgorithmus her?

[Smitty]

CStoll schrieb:

Smitty schrieb:

Das Problem ist wie schon gesagt das mitziehen der structs im vectot.
std::sort( bzw. vector::sort ) hatte ich schon.

Ich wußte gar nicht, daß vector<> eine sort-Methode mitliefert

Der vector::sort ist nicht von mir. Guckst du weiter oben ( war wohl std::sort gemeint )

CStoll schrieb:

Du mußt dir für jede deiner Sortierfolgen eine eine eigene Vergleichsfunktion schreiben, die auf die jeweiligen Eigenheiten eingeht - der normale String-Vergleich arbeitet mit den ASCII-Werten, dadurch landen Umlaute üblicherweise am Ende der Liste.

(wenn du die Umlaute im Alphabet einschieben willst, mußt du eine eigene Vergleichsfunktion schreiben - oder ein deutsches Locale zum Vergleichen verwenden)

Auch klar. habe ich auch gemacht. Funzt auch. Nur nicht mit dem:

std::sort( hVect.begin(), hVect.end(), std::greater<CString>() );

CStoll schrieb:

PS: Wo hast du denn diesen Sortieralgorithmus her?

Sag ich nicht :p
Ne, hab ich mir mal quick&dirty so zusammengekloppt. Tut seinen Dienst, ist aber wohl nicht der weisheit letzter Schluss

grüssle

[EXDW]

mach doch ne eigene sortier funktion:

// struktur definieren und vector fuellen, das hast du ja schon
struct DATA
{
    CString strA;
    CString strB;
    int i = 0;
};

vector<DATA> bla;
/* - fill - */

// merkt sich wie rum du sortieren moechtest
bool bDirectionA = false;

// sortiere nach strA
bool SortByA(const DATA &l, const DATA &r)
{
    if(bDirectionA) return l.strA < r.strA;
    else return l.strA > r.strA;
}

// richtung umkehrem und sortieren
bDirectionA = (bDirectionA) ? false : true;
std::sort(bla.begin(), bla.end(), SortByA);

[CStoll]

Smitty schrieb:

CStoll schrieb:

Du mußt dir für jede deiner Sortierfolgen eine eine eigene Vergleichsfunktion schreiben, die auf die jeweiligen Eigenheiten eingeht - der normale String-Vergleich arbeitet mit den ASCII-Werten, dadurch landen Umlaute üblicherweise am Ende der Liste.

(wenn du die Umlaute im Alphabet einschieben willst, mußt du eine eigene Vergleichsfunktion schreiben - oder ein deutsches Locale zum Vergleichen verwenden)

Auch klar. habe ich auch gemacht. Funzt auch. Nur nicht mit dem:

std::sort( hVect.begin(), hVect.end(), std::greater<CString>() );

Ja, eine struct als CString zu vergleichen macht sich nicht so gut - da mußt du dir eine eigene Funktion schreiben, die das gewünschte Element herausnimmt und vergleicht:

bool compare_string1(const data& l,const data& r)
{
  return l.s1<r.s1;
}
//analog compare_string2() und compare_int()

//Und als besonderes Schmankerl für die umgekehrte Sortierung:
struct inverse : public binary_function<bool,data,data>
{
  typedef bool (*comp_fn)(const data&,const data&);
  inverse(comp_fn func) : m_func(func) {}
  bool operator()(const data& l,const data& r)
  {
    return m_func(r,l);
  }
private:
  comp_fn m_func;
};

// Verwendung:
...
sort(hVect.begin(),hVect.end(),compare_string1);//aufsteigend nach erstem String
sort(hVect.begin(),hVect.end(),inverse(compare_int));//absteigend nach Zahl

CStoll schrieb:

PS: Wo hast du denn diesen Sortieralgorithmus her?

Sag ich nicht :p
Ne, hab ich mir mal quick&dirty so zusammengekloppt. Tut seinen Dienst, ist aber wohl nicht der weisheit letzter Schluss

bestimmt nicht - und statt etwas eigenes zu programmieren nach dem Motto "tut seinen Dienst", solltest du lieber auf die Arbeit von Experten vertrauen - da gibt es genug Verfahren, die meilenweit besser sein dürften^* (such mal nach "QuickSort", "MergeSort" oder "HeapSort").

^* nein, ich hab' dein Verfahren jetzt nicht im Detail analysiert

[Cpp_Junky]

Mach dir doch ne kleine Datenbank bevor du dir über den ganzen Kram den Kopf zerbrichst. Access über DAO, ist schnell implementiert und die haben den ganzen Sortier-Kram schon erforscht An sonsten würde ich einen Algorithmus vorschlagen, der die Elemente schon beim Einfügen vorsortiert (Heap-Sort? )

[CStoll]

Cpp_Junky schrieb:

An sonsten würde ich einen Algorithmus vorschlagen, der die Elemente schon beim Einfügen vorsortiert (Heap-Sort? )

Ja, das hätte ich auch vorgeschlagen (allerdings eher mit einem vorsortierten Container - set<>). Das Problem dabei ist aber, daß der OP das Sortierkriterium zwischendurch ändern will - und eine nach Vornamen sortierte Liste bringt keine Vorteile, wenn du die Daten nach Alter auflisten willst.

[Martin Richter]

CStoll schrieb:

Ich wußte gar nicht, daß vector<> eine sort-Methode mitliefert

Sorry. Meinte natürlich std::sort, habe es in der Eile mit list<>::sort

[Smitty]

CStoll schrieb:

Ja, eine struct als CString zu vergleichen macht sich nicht so gut - da mußt du dir eine eigene Funktion schreiben, die das gewünschte Element herausnimmt und vergleicht:

bool compare_string1(const data& l,const data& r)
{
  return l.s1<r.s1;
}
//analog compare_string2() und compare_int()

//Und als besonderes Schmankerl für die umgekehrte Sortierung:
struct inverse : public binary_function<bool,data,data>
{
  typedef bool (*comp_fn)(const data&,const data&);
  inverse(comp_fn func) : m_func(func) {}
  bool operator()(const data& l,const data& r)
  {
    return m_func(r,l);
  }
private:
  comp_fn m_func;
};

// Verwendung:
...
sort(hVect.begin(),hVect.end(),compare_string1);//aufsteigend nach erstem String
sort(hVect.begin(),hVect.end(),inverse(compare_int));//absteigend nach Zahl

[/quote]
Sieht gut aus, nur gibt der mir eine Fehlermeldung beim kompilieren:

E:\MLS\FileReader\FileReader\FileReaderView.cpp(672) : error C2664: 'void __cdecl std::sort(struct CFileReaderView::LCSTRUCT *,struct CFileReaderView::LCSTRUCT *,bool (__thiscall *)(const struct CFileReaderView::LCSTRUCT &,const struct CFileReaderVi
ew::LCSTRUCT &))' : Konvertierung des Parameters 3 von 'bool (const struct CFileReaderView::LCSTRUCT &,const struct CFileReaderView::LCSTRUCT &)' in 'bool (__thiscall *)(const struct CFileReaderView::LCSTRUCT &,const struct CFileReaderView::LCSTRUCT
 &)' nicht moeglich
        Keine Funktion mit diesem Namen im Gueltigkeitsbereich stimmt mit dem Zieltyp ueberein

Alles ausser 'Verwendung' ist doch in der .h, oder seh ich das falsch?

grüssle