PureBoard

Hey Leute,

ich suche nach einer Möglichkeit ein Verfahren zum Durchsuchen größerer Listen (~60/70) Einträge mithilfe verschiedener Suchkriterien zu zu optimieren. Es geht hier vor allem um echtzeittaugliche Verfahren (Suchzeit < 10ms o.Ä.), bei denen so wenig Vergleiche von Einträgen mit den Suchkriterien gemacht werden müssen wie nur möglich. Die Situation ist wie folgt:

Gegeben ist ein eindimensionales Feld, deren Einträge drei Attribute enthalten (die als Suchattribute verwendet werden können). Zusätzlich befindet sich ein 4. Attribut, welches von dem Alghorythmus zurückgegeben wird, wenn die Suchkriterien mit den 3 vorherigen des Eintrages übereinstimmen. Da diese Attribute die wildesten Werte haben könnnen, sieht mein pseudo-code für den aktuellen Alghorythmus so aus:
Wie man sieht, wird die gesamte Liste durchgegangen. Ziemlich datensparend, aber sehr langsam. Der Fokus der Suche liegt auf darauf, dass erst die Attribute ihrer Reihenfolge nach geprüft werden, was keine größere Bewandnis hat. Ich könnte mir jetzt ein recht kompliziertes System ausdenken, mit welchem so einiges an Verknüpfungstabellen erstellt werden müsste, aber vielleicht ist das garnicht nötig.

Hat irgendwer ne Idee von euch, wie man das am effektivsten zu lösen ist? Die Attribute sind alle Long-Werte.

Naja, wenn deine Liste ein Array wäre, könntest du mit einer binären Suche
ran. Dazu müsstest du das Array z.B. nach Attribut1 sortieren, das erste, das
du suchst, finden und dann die restlichen Attribute vergleichen. Das sollte bei
einer Liste mit 65536 Einträgen nach 16 + x vergleichen zum Ergebnis
führen, wobei x die Anzahl der doppelten Vorkommen des Attributs 1 ist.

Ah, du meinst also bitweise vergleichen? Hm... könnte es etwas beschleunigen. Sagen wir, ich will zudem die Redundanz der Attribute (und damit die Anzahl der Vergleiche) möglichst gering halten, im Notfall auch mit LinkedLists/Verknüpfungstabellen. Fällt dir dazu spontan auch was sein? (ergo möglichst wenig Doppelungen im Arbeitsspeicher vorkommen lassen -> die Tabellendaten liegen als Textdatei vor, dort herrscht die Redunz zur Übersicht immer noch.

Bitweises Vergleichen ist das nicht. Das ist eine Abwandlung des
Quicksort-Algorithmus zum schnellen Finden eines Eintrags in einem
vorsortierten Array.

Du könntest auch eine Struktur erstellen, die Attribut 1 auf Attribut 2 und
Attribut 2 auf Attribut 3 verlinkt. Außerdem verlinkst du Attribut 3 auf Attribut 4.

Aber ich weiß nicht, ob das wirklich was bringen wird. Wieviele Einträge sind
denn maximal in der Tabelle?

Ich nehme nicht an, dass die Einträge über 100 Stück gehen werden. Das mit dem Verlinken habe ich auch schon in Erwägung gezogen, aber im Endeffekt scheitert es daran, dass keines der Attribute bevorzugt wird (daher die Verlinkung nicht sehr viel bringt), was es unmöglich macht aus den daraus entstehenden Verlinkungen das passende Resultat ohne Überprüfen aller Eigenschaften herauszufinden.

Im Moment ist die Geschwindigkeit noch recht gut, da die Abfrage nicht sehr angewandt werden. Aber ich mache mir halt doch Sorgen, da es teil einer auf Tabellen basierender KI in einem Spiel ist und die Nutzung dieser Tabellen bei vielen Objekten bis ins Exessive ausgereizt werden könnte.

Es werden nicht mehr als 100 Einträge in der Tabelle?

Na dann brauchst du dir doch keine Sorgen zu machen. Das dauert doch keine 10 ms, höchstens 2 ms oder so um den Dreh 'rum.
Wie oft wird die Routine denn pro Runde bzw. Frame aufgerufen?

Oh, ich denke das wird schon ne ordentliche Menge werden. Je nach der Action auf dem Bildschirm könnten das schonmal 70 Abfragen pro Frame werden. Ich bezweifle zwar, dass ich jemals so viel Leistung damit verbrate, aber man muss schließlich auch anderes mit einbeziehen: Audiostreaming, Lichtberechnungen, Sound-Emissionen, etc... Insgesamt müsste das alles flüssig bei 70 Frames o.ä. laufen, da die Engine ein paar mehr Updates braucht.

Also maximal: 70 * 2 = 140 ms
Wo wir schon be dem Salat währen, dass schon ein 60Hz-Update max. 16ms fürs richtige Timing braucht.

HAst du das schon erledigt?
Ich vermute besser als oben geht es nicht.

Aber was da helfen kann, wenn man genauer wüßte um was für Daten es geht. Wie viele Einträge gibt es nun, Datensätze also die pro Durchlauf überpüft werden müssen. Sind die Einträge statisch oder ändern sie sich? Wie oft ändern sie sich. Wovon hängt die Änderung ab, welcher Typ Daten steht in den Feldern drinn?

Hast du mit deinen Daten und deinem Beispiel schon mal zum Test was ausgeführt und die Zeit gemessen?

Kekskiller hat geschrieben:Also maximal: 70 * 2 = 140 ms
Wo wir schon be dem Salat währen, dass schon ein 60Hz-Update max. 16ms fürs richtige Timing braucht.

da hast du dich verrechnet... das sind 140ms pro sekunde, also für alle 70 frames.

..und an dieser stelle sag ich nochmal, dass ich ein anständiges timing auf 30 oder 60 Fps
für besser halte als Frames schinden und sich in den Po kneifen.

...RiseOfNations läuft auf 30, Black&White läuft auf 30, also warum eigentlich nicht...?