qlisten

[RHBaum]

Ich kenn deinen Algo ned, von daher weiss ich ned was du wirklich brauchst ^^

Also gehts nur an nem "beispiel"

Du musst "irgendwie" eine Liste mit Namen speichern(im Speicher)

Dein Ansatz waer also:

Code: Alles auswählen

std::vector<std::string> myAdressList;
// ... irgendwann irgendwas einfuegen 
myAdressList.push_back("Horst Berger");
// .... 
/// ... durchlaufen wuerdest du Dann so: 
/// 
for(init i = 0; i < myAdressList.size(); ++i)
{
    std::cout << myAdressList[i] << std::endl;
}

Das funktioniert sicher auch redlich ....
Aber jetzt stell dir mal vor, du musst 100000 elemente da reinpumpen ...
was passiert ?

1. std::string iss ne speicherklasse, das heisst die haelt nur verwaltungsinfos + nen zeiger auf weiteren speicher, wo die eigentlichen daten stehen
2. std::string benutzt keine impliziete optimierung, ein kopieren eines strings ist also immer eine tiefe kopie, oder deine STL Impl haelt sich ned an den standard.
3. dein vector hat ne (vorhalte)basisgroesse von einigen T (typ was im vector steht), wenn der volllaeuft, muss der vector expandieren.
4. expandieren implementieren die meisten STL_Impls in dem sie Speicher doppelter groesse anfordern, das zeug rueberkopieren, den alten bereich loeschen (daten muessen ja immer hintereinander liegen)
5. also schatzen wir mal beim 10. 20. 40. 80. 160. ... Einfuegen, bricht die performance des einfuegens ein. Am anfang nur ganz wenig, aber um so mehr elemente drinne sind, um so seltener, aber um so drastischer wird der Einbruch.

Dabei iss das ganze komplett unnoetig. warum ?
ausser in der schleife verwendest du den indexoperator nicht ...
wenn du die schnelligkeit des indexoperators, und die notwqendigkeit der bLockweissen anordnung der Daten (c-kompatiblitaet) eliminieren kannst, iss ein vector total unnötig.

das schnellste einfügen der daten bietet dir die liste.
weiterhin garantiert dir die liste schnellstmöglich einen komplettdurchlauf durch alle elemente (komplette iteration).
index zugriff kann man nachprogrammieren, der iss aber dann nicht wirklich effizient, sollte man daher auch nicht.
Und die daten liegen nicht en block vor (verkettete liste halt).

Code: Alles auswählen

std::list<std::string> myAdressList;
// ... irgendwann irgendwas einfuegen 
myAdressList.push_back("Horst Berger");
// .... 
/// ... durchlaufen wuerdest du Dann so: 
/// 
for(std::list<std::string>::const_iterator it = myAdressList.begin(); it != myAdressList.end(); ++it)
{
    std::cout << (*it) << std::endl;
}

schon beim normalen einfuegen waer das ding (geringfügig)schneller. Aber auch jedes weitere anfügen waer genausoschnell !
Das staendige kopieren der kompletten string (holder + daten) wuerde entfallen.

Das ganze iss nun eben sehr theorethisch.

nen praktisches beispiel:

ich krieg hier staendig messdaten, bestehend aus nen zeitstempel (int64) und nen messwert(8 Byte datenblock), so ca. 8000 - 60000 pro sekunde in echtzeit.
DIe muss ich kurz bearbeiten und dann wegdumpen.
das wegdumpen iss ne FileIO operation, die kann also boese verzoegern.
die hardware hat nur nen puffer von paar 100Byte, die kann grad mal ne zehtelsekunde zwischenpuffern.
ich muss also selber puffern ... was werd ich wohl als puffer nehmen ?
vector ginge, wenn ich den gross genug vordimensionier (ne art ringpuffer).
Aber wehe ich verschaetze mich mal und er iss kleiner als benoetigt -> expandieren -> resize -> kann paar zehntel sek dauern -> datenverlust !
entweder verschlampe ich speicher wie doof, oder ich nehm was anderes. ne queue (also liste) bietet sich da formlich an !

Ciao ...

[franzf]

2. std::string benutzt keine impliziete optimierung, ein kopieren eines strings ist also immer eine tiefe kopie, oder deine STL Impl haelt sich ned an den standard.

Der C++-Standard schreibt gar nicht vor wie etwas implementiert sein soll. Er gibt nur ein Interface an, und bei manchen Sachen, welche Laufzeit die Operation haben darf.
Denn sollte obiges gelten, wäre die Implementierung von std::string im GCC nicht standardkonform - dort wird aktuell COW (copy on write) eingesetzt. Der selbe Mechanismus, der u.A. auch QString (-Kopien) schnell macht.

[kater]

Alles klar.Ich verstehe. In deinem Beispiel ist eine Liste schon besser. Ich wusste nicht, dass man Listen nur mit Iteratoren durchlaufen kann.
Also: Wenn nicht weiss, wieviel Daten so kommen und es sehr viele werden, eben mehr, als der Vector per default lang ist, dann sehe ich die Vorteile.

Habe gerade etwas überlegt... das ist noch nie vorgekommen
Ich kenne eigentlich immer die Anzahl der Daten. Teilweise sind es Bilder, da kennt man die Größe, und die leben nicht in einem std Container.

In meinem Projekt überschreibe ich mit 600000 Elemente zwar bestimmt die default Größe des std::vector, aber da da ich nur einmal den Vektor beim einlesen mit Daten füttere ist mir das egal.

Aber ich sehe was du meinst und habe es im Hinterkopf.

Danke für die Erklärung

[RHBaum]

Der C++-Standard schreibt gar nicht vor wie etwas implementiert sein soll. Er gibt nur ein Interface an, und bei manchen Sachen, welche Laufzeit die Operation haben darf.

Jein,
Die Schnittstelle ist die eine Sache.
Die STL macht aber auch Zusicherungen des Laufzeitverhaltens, welches eigentlich gewisse "Techniken und Optimierungen" ausschliesst.

Glaub das populaerste Beispiel war die von M$ modifizierte STL Impl von Dinkumware in frühen Versionen von VC6, was für arge Probleme gesorgt hat.

wäre die Implementierung von std::string im GCC nicht standardkonform - dort wird aktuell COW (copy on write) eingesetzt.

Entspricht überhaupt nicht meinem Kenntnissstand. Hab aber auch lange nix mehr mit dem gcc gemacht. Dacht immer der GCC nimmt ne STL impl direkt von SGI oder nahe vom SGI Standard ? Da dürfte sowas definitiv nicht vorkommen.

Auf welche Doku verweisen die denn in Sachen STL ? Was machen die da fuer Aussagen in bezug auf gueltigkeit des pointers von std::string::c_str() const und des Laufzeitverhaltens dieser Funktion ?

Schalten die bei singlethread und multithread die STL impls um(wie damals M$, wo es immer ne singlethread und ne multithreaded standard lib gab ? )

Ciao ...

[kater]

Noch so eine kleine Anmerkung zu Vector vs. Liste, Iteratoren und Initialsize.
Der gcc Compilert Version 4.5 kann da was lustiges

#

An experimental profile mode has been added. This is an implementation of many C++ standard library constructs with an additional analysis layer that gives performance improvement advice based on recognition of suboptimal usage patterns. For example,

#include <vector>
int main()
{
std::vector<int> v;
for (int k = 0; k < 1024; ++k)
v.insert(v.begin(), k);
}

When instrumented via the profile mode, can return suggestions about the initial size and choice of the container used as follows:

vector-to-list: improvement = 5: call stack = 0x804842c ...
: advice = change std::vector to std::list
vector-size: improvement = 3: call stack = 0x804842c ...
: advice = change initial container size from 0 to 1024

These constructs can be substituted for the normal libstdc++ constructs on a piecemeal basis, or all existing components can be transformed via the -D_GLIBCXX_PROFILE macro.

Werd ich wohl aus ausprobieren müssen

[odenter]

- ein kleiner Benchmark ergab mir mal, dass die QList-Indexe mindestens gleich schnell sind wie Iteratoren.

Vermutlich fällt der Unterschied gar nicht mehr auf, weil die Rechner heute so fix sind. Es gibt nichts schnelleres als den Zugriff per Index, da hier einfach ein Offset auf die Startadresse addiert wird und Du sofort am Ziel bist.

Der Iterator wird grundsätzlich das gleiche machen, nur eben nochmal extra gekapselt.

Bin nicht so der Assembler Crack, aber interessant wären in dem Zusammenhang mal zwei Beispiele Durchlauf per Index vs. Interator und dann ein Vergleich des erzeugten Maschinencodes.
Denn bei den Iteratoren haste möglicherweise, je nach Optimierung des Compilers, noch zusätzliche Methoden aufrufe die Overhead sind. Abhängig von dem Einsatzzweck kann das schon wichtig werden.

[franzf]

Der Iterator wird grundsätzlich das gleiche machen, nur eben nochmal extra gekapselt.

Bei QList ist das sicher eine eigene Klasse. QVector::iterator ist ein ordinärer typedef auf TypeT* (würde mir arg wundern, wenn QVector das anders lösen würde, bin aber jetzt zu faul nachzuschauen ). Also nur ein Pointer in das intern verwaltete Array. Dadurch ist iterieren über einen Vector genauso schnell wie Indexzugriff. Aber auch bei QList::iterator wird ein operator++ lediglich einen Zeiger versetzen.

[franzf]

QVector::iterator ist ein ordinärer typedef auf TypeT* (würde mir arg wundern, wenn QVector das anders lösen würde, bin aber jetzt zu faul nachzuschauen ).

Da muss ich mich korrigieren. Hab nachgeschaut und QVector::iterator ist eine eigene Klasse! Wobei alle Methoden inline sind, und am Ende (fast) nur das im Code steht, was mit dem typedef auch dastehen würde. Sollte also nicht an der Performance nagen