Wie iteriert man am besten über einen vector

FragaK schrieb:

...

Mit den Iteratoren kann man wenig verkehrt machen, nach den Optimierungen wird da nur ein roher Zeiger dereferenziert und inkrementiert. Seit auto aus C++0x ist die Deklaration auch nicht mehr so häßlich und zusätzlich kann man den darunterliegenden Container leichter austauschen.

SideWinder

Skym0sh0 schrieb:

Michael E. schrieb:

Das hat doch nichts mit Qualität zu tun

Die Komplexitäten sind korrekt, aber sie sagen nur etwas über das asymptotische Verhalten bei sehr vielen Zugriffen aus. Konstanten werden dabei vernachlässigt.

das ist ja auch der grund warum mergesort(O(n*log n)) in der praxis langsamer ist als quicksort(O(n*log n) bzw O(n²), die zusätzlichen konstanten machens in dem fall langsamer

Dann musst du aber auch dazusagen, dass dies speziell für Speichermedien gilt die konstante Random-Access-Zugriffszeiten bieten. Rein serielle Speichermedien arbeiten viel lieber mit Mergesort.

MfG SideWinder

BOOST_FOREACH( Foo foo, myVec )
{
}

314159265358979

SideWinder schrieb:

Skym0sh0 schrieb:

Michael E. schrieb:

Das hat doch nichts mit Qualität zu tun

Die Komplexitäten sind korrekt, aber sie sagen nur etwas über das asymptotische Verhalten bei sehr vielen Zugriffen aus. Konstanten werden dabei vernachlässigt.

das ist ja auch der grund warum mergesort(O(n*log n)) in der praxis langsamer ist als quicksort(O(n*log n) bzw O(n²), die zusätzlichen konstanten machens in dem fall langsamer

Dann musst du aber auch dazusagen, dass dies speziell für Speichermedien gilt die konstante Random-Access-Zugriffszeiten bieten. Rein serielle Speichermedien arbeiten viel lieber mit Mergesort.

MfG SideWinder

Ich habe mal versucht, jedes Element in einer std::list einen Zeiger zu holen und in einen vector zu werfen, und dann mit nem indirect_iterator und std::sort zu sortieren. War schneller als Mergesort.

Michael E.

314159265358979 schrieb:

SideWinder schrieb:

Dann musst du aber auch dazusagen, dass dies speziell für Speichermedien gilt die konstante Random-Access-Zugriffszeiten bieten. Rein serielle Speichermedien arbeiten viel lieber mit Mergesort.

MfG SideWinder

Ich habe mal versucht, jedes Element in einer std::list einen Zeiger zu holen und in einen vector zu werfen, und dann mit nem indirect_iterator und std::sort zu sortieren. War schneller als Mergesort.

Und? Das bestätigt SideWinder doch.

muffmolch

@boostyouup
wenn dann:

BOOST_FOREACH( Foo & f, fooVec ) ...
//bzw.
BOOST_FOREACH( const  & f, fooVec ) ...

@Performenztests:
Derartige sind mit äußerster Vorsicht zu genießen, da sie sehr von den durchgeführten Compileroptimierungen abhängen. Generell ist das Verwenden von Iteratoren zu bevorzugen. Wobei ich bei vectoren aus alter Gewohnheit meist den Indexoperator verwende...

DocShoe

FragaK schrieb:

Hi,

sagen wir ich habe einen vector<Foo> und will über alle Elemente iterieren. Wie mach ich das am effiziensten?

// A) Mit Iteratoren
vector<Foo>::iterator it = myVec.begin();
vector<Foo>::iterator itEnd = myVec.end();
for(; it != itEnd; ++it) {
    int val = it->member;
    int val2 = it->member2;
    ...
}

// B) Mit operator[]
for(int i; i < myVec.size(); i++) {
    int val  = myVec[i].member;
    int val2 = myVec[i].member2;
    ...
}

// C) Einmal const Referenz holen, damit man nur einmal operator[] aufruft:
for(int i; i < myVec.size(); i++) {
    const Foo& foo = myVec[i];
    int val  = foo.member;
    int val2 = foo.member2;
    ...
}

Ist eine der Varianten am besten/effizientesten?

Ist das Absicht, dass du in Variante und C) die Laufvariable i nicht initialisierst?

Skym0sh0

das gesamte thema hatten wir aber schon ein paar mal

im prinzip kannst du sagen per index und per iterator ist gleich schnell. das würde ich schon premature optimizing nennen wenn du da was dran drehen willst.

mach dir lieber sorgen um die richtigen performancefresser (wie z.b. schlechte algorithmen, oder container falsch eingesetzt)

muffmolch

FragaK schrieb:

Hi,
sagen wir ich habe einen vector<Foo> und will über alle Elemente iterieren. Wie mach ich das am effiziensten?
[/cpp]
Ist eine der Varianten am besten/effizientesten?

Ich persönlich bevorzuge die letzte Variante, wobei ich (wenn ich schon auf Laufzeit achte), val und val2 ausserhalb des for-scopes deklariere.

Ein guter Compiler sollte sowas aber von sich aus optimieren. Bei komplexen Datenstrukturen sieht das idR schon anders aus!

Nexus

muffmolch schrieb:

@boostyouup
wenn dann:

BOOST_FOREACH( Foo & f, fooVec ) ...
//bzw.
BOOST_FOREACH( const  & f, fooVec ) ...

Oder mit C++0x, sobald es die Compiler unterstützen:

for (Foo& f : fooVec)

Und vorher kann man sich ein foreach -Makro mit auto basteln.

muffmolch schrieb:

Ich persönlich bevorzuge die letzte Variante, wobei ich (wenn ich schon auf Laufzeit achte), val und val2 ausserhalb des for-scopes deklariere.

Wenn du schon auf die Laufzeit achtest, kannst du es gleich richtig machen. Die Annahme, nicht-lokale Definitionen seien schneller, stimmt so verallgemeinert nicht. Siehe hier.

muffmolch

Nexus schrieb:

Wenn du schon auf die Laufzeit achtest, kannst du es gleich richtig machen. Die Annahme, nicht-lokale Definitionen seien schneller, stimmt so verallgemeinert nicht. Siehe hier.

Da gebe ich dir recht, aber bei unserem Strömungssimulator hat es nunmal in Summe ~10% Leistung ausgemacht. Dabei handelte es sich größtenteils um double-Werte, die in vectoren gespeichert wurden. Sowas ist natürlich stark compilerabhängig (was ich auch erwähnte). Beim gcc 4.3 brachte es eben knapp 10%, beim icc 10.x hingegen war der Leistungsunterschied vernachlässigbar. Bei der Optimierung war kein Unterschied zwischen O2 und O3 messbar. Daher gilt für mich immer: laufzeitkritische Abschnitte immer manuell optimieren. Zudem hängt es auch stark davon ab, welcher Code letztlich im Scope ausgeführt wird. Meistens sollte man sich mehr Gedanken um diesen Code machen als um die Art der Vectoriteration, die meist nicht von Belang ist.

Speicherzugriffsmuster sind da wichtiger als "wie iteriere ich über einen vector"-Fragen.

hustbaer

Nexus schrieb:

muffmolch schrieb:
@boostyouup
wenn dann:
BOOST_FOREACH( Foo & f, fooVec ) ...
//bzw.
BOOST_FOREACH( const  & f, fooVec ) ...
Oder mit C++0x, sobald es die Compiler unterstützen:
for (Foo& f : fooVec)
Und vorher kann man sich ein foreach -Makro mit auto basteln.

Ein foreach-Makro wie BOOST_FOREACH.
Wozu sollte man sich sowas selbst basteln?

Nexus

hustbaer schrieb:

Ein foreach-Makro wie BOOST_FOREACH.
Wozu sollte man sich sowas selbst basteln?

Z.B. weil man Boost nicht benutzen kann. Oder weil einem "the performance of BOOST_FOREACH is usually within a few percent of the equivalent hand-coded loop" nicht passt. Oder weil man die Compiletime-Dependencies von <boost/foreach.hpp> (unter Anderem Range, TypeTraits, MPL) unverhältnismässig findet.