Was ist schneller im Zugriff?

Hi,

also ich habe einen scenemanager bei dem ich alle sichtbaren objekte mit einer add-funktion hinzufüge in eine std::list oder std::vector (darum gehts ja was schneller ist), die dort nach texturen sortiere und dann runterrendere.

Dabei ist mir die zugriffsgeschwindigkeit auf die daten sowie das hinzufügen sehr wichtig.

Ponto

Ich geh mal von folgendem aus:

- Du willst Daten nur ans Ende des Containers anfügen.
- Deine Objekte lassen sich schnell kopieren, oder du kennst die Anzahl im voraus.

Dann würde ich std::vector nehmen, ansonsten std::list.

wo ist eigentlich der unterschied zwischen den beiden? Vor/Nachteile?

otze

list hat konstante einfügezeit am anfang und am ende(oder war am ende auch linear?), in der mitte linear.
leseoperationen sind auch nur in linearer laufzeit möglich.

beim vector ist das einfügen am ende konstant,sonst linear.
leseoperationen sind konstant.

d.h.?

Ja, was heißt wohl konstant und linier, wenn es um die Zeit geht?

Wenns darum geht, den Kram zu sortieren, wär im Zweifel std::set ne sinnvolle Idee.

So eine Tabelle wäre nützlich wie in manchen Büchern, wo die Eigenschaften von den Containern drin stehen.

volkard

Strogij schrieb:

So eine Tabelle wäre nützlich wie in manchen Büchern, wo die Eigenschaften von den Containern drin stehen.

kaum. es gibt so viele konfigurationen, was man haben mag, daß die nicht alle sinnvoll auflistbar sind.

was echt hilft, ist die datenstrukturen erst einmal (ganz laienhaft und nicht perfekt aber im prinzip ok) zu bauen. dann erst std::kram benutzen.

also ich habe einen scenemanager bei dem ich alle sichtbaren objekte mit einer add-funktion hinzufüge in eine std::list oder std::vector (darum gehts ja was schneller ist), die dort nach texturen sortiere und dann runterrendere.
Dabei ist mir die zugriffsgeschwindigkeit auf die daten sowie das hinzufügen sehr wichtig.

vergleichen wir mal push_back().

speicher:
bei der liste wird immer ein knoten neu angelegt. mit new. kostet 32 bytes speicher minstetens (bei msvc6) und wohl mindestens 4 bytes internen overhead.
bei vector ist kein overhead.

laufzeit:
bei liste immer ein aufruf von op new und der kostet locker 100 zyklen (bei msvc6 mehr). bei vecto5 bauchts eher 10, außer wenn gewachsen werden muss. dann ein komplettes kopieren aller bisherigen elemente. for 1000000 elemente muss man 1000000 elems einfügen und 500000 und 250000 und 125000 und ... kopieren. in summe auch nur 1000000. also pro einfogung auch eine kopierung und ld(1000000) mal op new. das ist bei eher kleinen objekten *deutlich* schneller als ein op new pro objekt.

sequenzieller zugriff:
bei vector ist es schlicht eine zeiger-dereferenzierung, das kann der prozessor saugut. weiterschaltung ist ein ++ und das kann er extrem saugut.
bei liste ist der zugriff auch eine zeigerdereferenzierung und die weiterschaltung auch eine. also leicht lahmer.

sortieren:
hier gewinnt klar vector, weil introsort (im kern quicksort) auf arrays einfach zur zeit der geilste sortieralgo ist. list kackt da um größenordnungen ab. in der tat isses oft besser, eine list erst komplett in einen vector zu kopieren, doer zu sortieren und zurückzukoperen statt direkt auf der loist zu sortieren.

also ganz allgemein ist bei deinen anforderungen vector erheblich besser.

map wie hier vorgeshlagen ist ein witz.

dann kommen wir dazu, daß, wenn genauere angaben zur datenverteilung bekannt sind, es evtl möglich ist, nochmal faktor 10 oder 100 rauszukolen. kenne deine daten nicht. gibt es am ende 1000000 flächen, die zu rendern sind aber nur 100 surfaces? dann doch bitte 100 getrennte vectors bauen. dann mpssen die vielen vectors mit durchschnittlich 10000 flächen gar nicht sortiert werden und die 100 vectors sind schon geeignet, die nacheinander an die graka zu werfen.

Jetzt weiß ich wieso man dich "Den Paten" nennt. Man bist du gut! Vielen Dank!

otze

hier gewinnt klar vector, weil introsort (im kern quicksort) auf arrays einfach zur zeit der geilste sortieralgo ist. list kackt da um größenordnungen ab.

wurde list aber nicht dafür designt, _der_ sortiercontainer zu sein? die elemente in der list werden ja beim sort nicht kopiert(hoffentlich). Ist introsort wirklich so extrem viel schneller, dass man das zt langsame kopieren von elementen ausser acht lassen kann?

Shade Of Mine

otze schrieb:

wurde list aber nicht dafür designt, _der_ sortiercontainer zu sein?

Ohne random access? da kann man nicht so gut sortieren, egal welche tricks man anwendet. mit random access geht sortieren um längen besser.

Ponto

Wenn das Kopieren eines Elementes sehr langsam ist, dann verliert wieder vector gegenüber der list. In diesem Fall speichert man aber von vornerein nur Zeiger auf die Elemente im vector, so dass dieser wieder gewinnt.

otze

Shade Of Mine schrieb:

otze schrieb:

wurde list aber nicht dafür designt, _der_ sortiercontainer zu sein?

Ohne random access? da kann man nicht so gut sortieren, egal welche tricks man anwendet. mit random access geht sortieren um längen besser.

wieso besitzt list dann eine sort methode? irgendwie muss sie ja schon dafür designt worden sein, dass es ohne random access schwer ist, ist mir auch klar, oder ist das ganze einfach nur ein designfehler?

phlox81

Irgendwo hab ich mal vor kurzen gelesen, das
man statt vector deque nehmen soll, weil deque
z.b. nicht unbedingt einen zusammenhängenden Speicherblock
braucht.

Ist da was dran ?

Devil

volkard

otze schrieb:

wieso besitzt list dann eine sort methode? irgendwie muss sie ja schon dafür designt worden sein, dass es ohne random access schwer ist, ist mir auch klar, oder ist das ganze einfach nur ein designfehler?

weil list::sort am besten ganz anders implementiert wird. sind die daten recht zufällig, dann ein quicksort. anderenfalls ein mergesort würde ich sagen. beide brauchen nur zugriff auf's erste element einer liste.
pseudocode für quicksort (man erkenne, daß sich quicksort auf listen wirklich wohl fühlt. die lehrbücher, die quicksort auf listenb zwingen und dazu array-quicksort mit random-access-iterator benutzen oder so nen mist machen, einfach ignorieren):

void list::sort(){
   if(empty) return;
   list links,rechts;
   T pivot=front();
   pop();
   while(!empty()){
      if(front()<pivot)
         kleijner.pushback(front())
      else
         groesser.pushback(front())
      pop();
   }
   swap(*this,links);
   push_back(pivot);
   hänge rechzts an *this an.
}

volkard

devil81 schrieb:

Irgendwo hab ich mal vor kurzen gelesen, das
man statt vector deque nehmen soll, weil deque
z.b. nicht unbedingt einen zusammenhängenden Speicherblock
braucht.
Ist da was dran ?
Devil

ja.

schauen wir nochmal vector uns list an.

vector "ruckelt". beim wachsen ist immer ein kleines päuschen. naja, eins, das bei jedem wachsen doppelt so groß wird (aber auch immer seltener, im durchschnitt ist das päuschen pro einfügung extrem kleine). wenn man dann langsam bei 200000000 elementen ist, die man eingefügt hat, wird das päuschen auch mal ein sekündchen dauern. das kannste mitten im game nicht gebrauchen. also nimmste vector nicht. lieber die list, die imme bei jedem einfügen ein päuschen nimmt. am enbde ist dein game zwar um faktor 10 lahmer, aber es ruckelt nicht, sondern schneckt gleichmäßig. das ist marktfähig.

queue macht einen kompromiss. es legt (sagen wir mal ne speicherseite hat 4k und man tut nur ints rein) immer einen block von 1000 elementen an. macht die voll. und dann wieder 1000. macht minimale speicherverschwendung (einmal steiuerinfos pro 1000 elemete). ist sauschnell (viel schneller als list). und ist oft eine gute alternative.

verglichen mit vector würde ich sagen, daß der op[] lahmer sein muss. immerhin muß er erst schauen, welche speicherseite es ist und dann in der speicherseite das element holen. dürfte halb so schnell wie vei vector sein. iteratorweiterschaltung dürfte erheblich langsamer sein, immerhin ist da ein if drin, wenn die aktuelle seite zu ende ist. mit tricks und glück nur ein &, dann mags halb so schnell wie beim vector sein. op* auf den iterator genausoschnell. und sortieren...

und sortieren halb so schnell bei kleinen elementen spürbar langsamer, aber nicht halb so langsam, wenn introsort genommen wird. vielleicht sollte man hier mergesort nehmen, weil die speicherseiten so lecker vorbereitet sind. klingt verlockend. macht auch wohl weniger vergleiche. aber es muß öfters geschrieben werden, dann bestraft einen das lahme ram.

otze

volkard schrieb:

void list::sort(){
   if(empty) return;
   list links,rechts;
   T pivot=front();
   pop();
   while(!empty()){
      if(front()<pivot)
         kleijner.pushback(front())
      else
         groesser.pushback(front())
      pop();
   }
   swap(*this,links);
   push_back(pivot);
   hänge rechzts an *this an.
}

hmm, bin ich jetzt dumm, oder befinden sich nach einer benutzung dieses sorts alle werte <pivot unsortiert am anfang und alle werte >pivot unsortiert am ende?(müsste danach nicht vielleicht noch ein anderer sort algo kommen, bzw dieser hier rekursiv für links/rechts aufgerufen werden?)

volkard

otze schrieb:

volkard schrieb:
void list::sort(){
   if(empty) return;
   list links,rechts;
   T pivot=front();
   pop();
   while(!empty()){
      if(front()<pivot)
         kleijner.pushback(front())
      else
         groesser.pushback(front())
      pop();
   }
   swap(*this,links);
   push_back(pivot);
   hänge rechzts an *this an.
}
hmm, bin ich jetzt dumm, oder befinden sich nach einer benutzung dieses sorts alle werte <pivot unsortiert am anfang und alle werte >pivot unsortiert am ende?

ups, hab zwei zeilen vergessen.

void list::sort(){
   if(empty) return;
   list links,rechts;
   T pivot=front();
   pop();
   while(!empty()){
      if(front()<pivot)
         kleijner.pushback(front())
      else
         groesser.pushback(front())
      pop();
   }
   links.sort();//<--- hier neu, kauf mich!
   rechts.sort();<--- hier neu, kauf mich!
   swap(*this,links);
   push_back(pivot);
   hänge rechzts an *this an.
}

otze

dacht ich mir schon :), nun ist klar