#1 09.01.2006 12:51:36

Neo
Member
Ort: Erfurt/Thüringen
Registriert: 31.01.2005
Beiträge: 78
Web-Seite

Performantes dynamisches Array ähnlich TList

Heute möchte auch ich einmal wieder mehr für die Community beitragen als nur mit ein paar Antworten.

In fast allen größeren Projekten und besonders auch in 3D Engines existieren oft dynamische Arrays zur Verwaltung von Objekten, sei es z.B. ein Scenegraph oder eine Renderqueue.

Ich habe mir dafür eine eine kleine, aber feine Klasse geschrieben die ähnlich wie TList arbeitet. Die Klasse verwaltet beliebige Typen durch Pointer (oder somit auch jeden 32 Bit Datentyp direkt) und bietet eine optimiertere Sortierroutine an. Ich verwende dabei den Quicksort Algorithmus, der ab einer kleinen Menge allerdings zum Einfügesort wechselt. Dadurch erreiche ich auf meiner CPU einen Geschwindigkeitsvorteil gegenüber TList von ungefähr 15%.

Ihr könnt die Klasse für jeden Zweck frei verwenden, sei es nur aus Neugierde oder vielleicht sogar aus praktischem Interesse.
Ich verwende dieses Array für meinen Szenengraphen, meine ResourceManager und meine Renderschleife und habe daher auf eine schlanke, aber flinke Klasse viel wert gelegt (was ich eigentlich grundsätzlich tue).

Viel Spaß damit, würde mich über Kommentare und Verbesserungswünsche freuen.

Neo


Attachments:
Attachment Icon NBArray.pas, Größe: 6,213 bytes, Downloads: 932

Offline

 

#2 09.01.2006 15:02:09

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Performantes dynamisches Array ähnlich TList

Ist des nu ein Array oder eine Liste? Also Randomaccess oder nicht?


My software never has bugs. It just develops random features.

Offline

 

#3 09.01.2006 15:18:45

Neo
Member
Ort: Erfurt/Thüringen
Registriert: 31.01.2005
Beiträge: 78
Web-Seite

Re: Performantes dynamisches Array ähnlich TList

Das ist ein dynamisches Array, also "array of Pointer", keine verknüpfte Liste.

Neo

Offline

 

#4 09.01.2006 16:19:54

MexDelphi
ProMember
Ort: Göppingen
Registriert: 24.01.2005
Beiträge: 235
Web-Seite

Re: Performantes dynamisches Array ähnlich TList

klein ... fein ... fix  :mrgreen: gefällt mir  :thx2:


goto: http://mexdelphi.cybton.com

Offline

 

#5 09.01.2006 18:36:43

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Performantes dynamisches Array ähnlich TList

Also ich hab mir das gerade mal angeschaut, scheint ganz praktisch zu sein, sofern man nicht löschen will.
Du verschiebst beim löschen alle Nachfolgenden Elemente, oder?
Sofern man kein sortiertes Array benötigt, kann man Elemente viel schneller (mit konstantem Aufwand) löschen, indem man einfach das letzte Element des Arrays an die Stelle kopiert und dann ein pop_back() macht.

Coolcat


My software never has bugs. It just develops random features.

Offline

 

#6 09.01.2006 18:53:05

Neo
Member
Ort: Erfurt/Thüringen
Registriert: 31.01.2005
Beiträge: 78
Web-Seite

Re: Performantes dynamisches Array ähnlich TList

Danke für den Tipp Coolcat, das ist durchaus eine bessere Möglichkeit wenn die Reihenfolge zu keinem Zeitpunkt eine Rolle spielt, in einem Szenengraph ist dies ja z.B. der Fall, dort spielt es keine Rolle an welcher Position ein Element im Array steht.

Ich werde das mal mit einbinden.

Neo

Offline

 

Brett Fußzeile

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson