Was ist schneller im Zugriff?

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