Moin,
seit es in AutoIt nun offiziell den Map-Datentyp gibt dachte ich mir: Warum keine UDF für doubly linked lists basteln?
Idee dahinter: Es gibt keinen nativen List-Datentyp, und (mangels Pointer und dynamischer Allokation) auch keine Möglichkeit selbst eine Liste aufzubauen (ja, es geht mit Structs die man vor dem automatischen Löschen schützt, aber die können keine "AutoIt-Variablen" speichern). Daher: Nutze eine Map als "dynamischen Speicher" und packe die [value, previousPointer, nextPointer] tripel einfach in eine Map.
Geschwindigkeitstests habe ich nur bei relevanten Funktionen gemacht:
Datengröße: 0 - 1000
- List schneller (ca. 2x - 10x) _ArrayAdd vs _ListPushBack, _ArrayPop vs _ListPopBack, (und ähnliche Funktionen) (Iteratorversion)
- List schneller (ca. 1x - 100x) _ArrayDelete vs _ListRemove, _ArrayInsert vs _ListInsert (Iteratorversion)
- Array schneller (100x+) Direktzugriff vs _ListRead & _ListWrite (Indexversion)
- Array schneller (ca. 2x) Direktzugriff vs (inlined) _ListRead & _ListWrite (Iteratorversion)
Von vielen List-Funktionen gibt es eine Indexversion und eine Iteratorversion. Die Indexversion hat immer Komplexität O(n/2). Die Iteratorversion ist (näherungsweise) O(1) und damit meistens halbwegs flott. Das allerschlimmste was man tun kann ist der Direktzugriff via Index (das ist 100x+ langsamer). Insgesamt kam das heraus was wir alle vorher schon wussten: Das was Lists in O(1) und Arrays in O(n) machen ist ab einer Größe von ca. 5 Elementen schon schneller, alles andere ist langsamer.
Manche List-typische Funktionalität fehlt leider:
- Es gibt keine Mergefunktion (hier würden Listen auch extrem gut abschneiden, da man nur ein paar Pointer ändert und nichts kopiert)
- Es gibt keine Splitfunktion (s.o.)
Grund dafür ist: Es ist (zumindest mit dem jetzigen Aufbau der UDF) nicht möglich von einer Liste auf eine andere zu verlinken. Ein "ListPool" der komplett innerhalb einer Map liegt könnte das Problem lösen, würde aber auch einiges an Overhead mitbringen.
- Insgesamt ist der Umfang/Errorhandling/etc. nicht mit Array.au3 vergleichbar, sondern nur ein sehr kleines Subset was mit der Zeit vielleicht noch etwas wächst
Wie immer gilt: Viel Spaß mit der UDF und meldet Fehler/Wünsche. Falls ich Zeit und Lust habe kümmere ich mich darum.
lg
Mars