interne Funktionsweise eines Arrays

[himitsu]

Die Größe des Arrays ist vollkommen egal, da der Zugriff über einen Index (Offset) immer gleich schnell ist.
SpeicherAdresse = Array-Pointer + Index * SizeOf(...)
Aus diesem Grund besteht ein Array auch immer nur aus einem zusammenhängendem Block, welcher die Maximalgröße bestimmt, da sie durch den größten freien Speicherblock bestimmt wird, welcher verwendet werden kann -> Speicherfragmentierung.

Was langsamer wird, je größer das Array (und auch eine TList<>, welche intern ebenfalls ein Array nutzt) wird, die Änderung der Größe.
Wenn der Speicher nicht inplace verändert werden kann (was der FastMM beherscht), weil z.B. dahinter kein freier Platz mehr ist, dann muß der Speicher umkopiert werden, was natürlich bei mehr Daten etwas länger dauert.


Bei einer verketteten Liste wäre zwar die Größe durch den gesamten belegbaren Speicher wesentlich unbegenzter und die Größenänderung (Speicherreservierung/-freigabe) hängt nicht von der Größe der Liste ab, aber dafür ist der Zugriff langsamer, außer man baut parallel einen Index auf.

[Gargamel]

@Aphton (und natürlich alle anderen auch)

Zitat:

Du kannst ja mal erläutern, um was für Daten es sich handelt und in welcher Relation diese zueinander stehen.

Es geht darum, daß eine KI innerhalb einer DLL ausgeführt/berechnet werden soll. Die Host-Anwendung ist Unity3D. Die Programmierung innerhalb dieser 3D-Engine erfolgt mit C# und damit managed Code. Das Thema 'Ausführungsgeschwindigkeit managed Code vs. nativer Code' liefert im Internet gerne mal widersprüchliche Aussagen. Aber lassen wir das mal aussen vor.
Jetzt ist es so, daß ein reger Datenaustausch zwischen der Engine und der KI-DLL stattfindet. Mein Gedanke war der, daß jedes Objekt innerhalb der Engine, welches durch KI gesteuert werden soll, ein Schwester-Objekt innerhalb der DLL besitzt und diesem immer seine aktuellsten Werte übermittelt. Also Position, Rotation, Sichtbarkeiten (Portale), Kollision mit Objekt XY usw. ...
Das Schwester-Objekt rechnet irgendwelche Dinge auf Basis von State-Machines, Pathfinding, Fuzzy-Logic, Schwarmverhalten, etc. aus und liefert dem zugehörigen Objekt in der 3D-Engine alle nötigen Informationen, was es denn nun tun soll (drehe Dich in diese Richtung, schieße da hin, spiele Animation XY mit, usw. ...).

Jedes Objekt in der Engine, was durch die KI gesteuert wird, erhält von der DLL eine eindeutige ID-Nummer (und damit den Index eines Arrays), um mit seinem Schwester-Objekt kommunizieren zu können. Und genau an dieser Stelle war ich mir unschlüssig, ob der ständige Zugriff über ein Array-Index u.U. zu langsam ist. Wobei 'langsam' natürlich relativ ist.

Zudem kommt noch, daß es je nach Spiel bzw. Gameplay vorkommen kann, daß KI-Objekte in einem kurzen Turnus erstellt und wieder gelöscht werden. Und das bedeutet, daß es recht schnell Lücken innerhalb des Arrays geben kann, die man sich irgendwie merken muß, um diese mit später erzeugten KI-Objekten wieder befüllen zu können.

Um das zu umgehen, fielen mir einfach verkettete Listen ein, da man schnell Elemente entfernen und hinzufügen kann.
Gestern testete ich die Möglichkeit, mir von diversen Variablen in der DLL die Speicheradressen liefern zu lassen. Auf diese Weise konnte ich aus der 3D-Engine heraus den Speicherinhalt der DLL-Variablen direkt manipulieren (was dem Aktualisieren der Schwester-Objekte für Positon. Rotation, ... entsprechen würde).

[Namenloser]

Die Lösung für dein Problem ist eine Hashmap (aka. Hashtable). C# wird vermutlich auch schon eine fertige Implementierung davon mitbringen.

[Blup]

Zitat von Gargamel:

Jedes Objekt in der Engine, was durch die KI gesteuert wird, erhält von der DLL eine eindeutige ID-Nummer (und damit den Index eines Arrays), um mit seinem Schwester-Objekt kommunizieren zu können. Und genau an dieser Stelle war ich mir unschlüssig, ob der ständige Zugriff über ein Array-Index u.U. zu langsam ist. Wobei 'langsam' natürlich relativ ist.

Zudem kommt noch, daß es je nach Spiel bzw. Gameplay vorkommen kann, daß KI-Objekte in einem kurzen Turnus erstellt und wieder gelöscht werden. Und das bedeutet, daß es recht schnell Lücken innerhalb des Arrays geben kann, die man sich irgendwie merken muß, um diese mit später erzeugten KI-Objekten wieder befüllen zu können.

Den Index in einer Liste als ID zu verwenden ist eine schlechte Idee. Eine ID sollte wirklich nur einmal eindeutig vergeben und nicht wiederverwendet werden.
Damit man das Objekt mit wenigen Zugriffen auf die Liste findet, kann man diese nach ID sortieren.

Zitat von Gargamel:

Um das zu umgehen, fielen mir einfach verkettete Listen ein, da man schnell Elemente entfernen und hinzufügen kann.

Von verketteten Listen besser die Finger lassen. Die Vorteile von TList/TObjectList (gekapseltes Array) überwiegen in der Regel.
Z.B. passt das Array der Elemente häufig in den Cache der CPU. Das Verschieben von Elementen innerhalb des Arrays beim Löschen einzelner Elemente spielt so für die Geschwindigkeit nur eine untergeordnete Rolle.
Bei verketteten Listen liegen die Elemente im Speicher verstreut, es müssen eventuell mehrere Speicherbänke in den Cache geladen werden (der hat aber nur eine begrenzte Kapazität). Da kann es auch viel eher zu Kollisionen kommen, wenn mehrere CPUs auf die selbe Speicherbank zugreifen.
Als Folge dann Wartezeiten bis sich die Cache der CPUs synchronisiert haben.

Zitat von Gargamel:

Gestern testete ich die Möglichkeit, mir von diversen Variablen in der DLL die Speicheradressen liefern zu lassen. Auf diese Weise konnte ich aus der 3D-Engine heraus den Speicherinhalt der DLL-Variablen direkt manipulieren (was dem Aktualisieren der Schwester-Objekte für Positon. Rotation, ... entsprechen würde).

Hier bietet es sich an den Objekten außerhalb der KI ein Interface zu verpassen.
Dieses kann dem KI-Objekt beim Erzeugen mitgegeben werden.
Das KI-Objekt hat so immer Zugriff auf die aktuellen Objektwerte.