brauche Indexsuche-algorithmus

bIce

Hi!!!

brauche wieder Hilfe, kann jemand diese Funktion optimieren (ausführungszeit)

Es muss hier ein Objekt (TSItem*) mit dem Index index zurückgegeben werden. Ich bin mit meinem Wissen schon am Ende , aber die Funktion ist immer noch zu langsam.

FList ist vom Typ TItems, TItems ist list<TSItem*>

TSettings::TSItem* TSettings::Get(UINT index)
{
   // Aufwärts oder Abwärts. Wenn index in der unteren hälfte dann aufwärts (1)
   // mit aufwärts initialiesieren
   int step = 1;
   TItems::iterator iter = FList.begin();
   UINT pos = 0;

   // Und hier für Abwärts
   if ( FList.size() / 2 < index ){
       step = -1;
       iter = FList.end();
       iter--; // weil .end() *über* dem letzten element liegt
       pos = FList.size() - 1;
   }

   // position suchen
   while (index != pos){
      if (step > 0) iter ++;
      else          iter --;

      pos +=step;
   }
   // ergebnis zurückgeben
   return *iter;
}

PeterTheMaster

wuerdest du mal abstrakt formulieren, was du willst, dann laesst sich besser ueberlegen, wie das wohl am optimalsten geht.
wenn du ein objekt nach einem bestimmten kriterium finden willst macht es meist, den container nach diesm kriterium zu sortieren, dann kannst du es in
O(logN) finden.
willst du die ordnung im container nicht aendern (oder wenn nach mehreren kriterien gesucht werden koennen soll), koenntest du statt dessen einen ensprechend sortieren container mit pointern oder indices in den ersten container vorhalten.

PeterTheMaster

geht es hier um die get(index) methode einer liste? dann vielleicht ein zusaetzliches array mit pointern auf die elemente. dann geht es in konstanter zeit.
speziell in deiner funktion kannst du auf jeden fall das if aus dem while rausnehmen und dann 2 whiles haben. beim optimieren ist es haeufig sinnvoll, in der innersten schleife zu beginnen, da der code dort am haeufigsten ausgefuehrt wird.

bIce

Die Reihenfolge sollte nicht geändert werden. Es soll nur ein Zeiger zurückgegeben werden.

ich beschreibe hier mal das Problem mehr oder weniger ausführlich:
---------------------------------------
ich habe eine Liste,
in dieser sind Zeiger auf Objekte gespeichert:

zum Beispiel so:
erstes Element (mit index = 0) ist ein Zeiger auf das Objekt a
zweites Element (mit index = 1) ist ein Zeiger auf das Objekt b
usw.

meine funktion Get(index) soll den Zeiger eines Objekts mit einem bestimten index zurückgeben.

bIce

PeterTheMaster schrieb:

geht es hier um die get(index) methode einer liste? dann vielleicht ein zusaetzliches array mit pointern auf die elemente. dann geht es in konstanter zeit.
speziell in deiner funktion kannst du auf jeden fall das if aus dem while rausnehmen und dann 2 whiles haben. beim optimieren ist es haeufig sinnvoll, in der innersten schleife zu beginnen, da der code dort am haeufigsten ausgefuehrt wird.

Danke erstmal für die Tipps, werde morgen ausprobieren.