• 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

  • Hi Mars ,

    vielen Dank für die UDF bzw. deine Implementierung 👍 .
    Ich bin zwar gerade noch dabei mich mal durchzuforsten, doch bereits durch __ListExample() sehe ich den von dir beschriebenen Mehrwert 😀 .
    Danke, kann sehr nützlich sein.


    Viele Grüße
    Sven

  • Moin Mars,

    sorry - bis zu Deinem Beitrag wußte ich nichteinmal, dass es einen Map Datentyp gibt geschweige denn was das ist. in Map Datentyp ist. Ist das sotwas wie hier erklärt?

    Map-Datentyp

    Wenn ja - wo ist der Vorteil gegnüber einem Komma getrennten Datensatz oder eben einem Array. Für das Beispiel aus dem Link:

    2022334;Daniel Düsentrieb

    2345678; Donald Duck


    Danke für die Nachhilfe

    Peter

    Hinweise auf Suchmaschinen finde ich überflüssig - wer fragt hat es nicht gefunden oder nicht verstanden. Die Antwort gibt sich oftmals schneller als der Hinweis auf Dr. Goggle & Co.

    Ab 19-10-22 ergänzt um:

    Die Welt wird nicht bedroht von den Menschen, die böse sind, sondern von denen, die das Böse zulassen. (Albert Einstein)

    Einmal editiert, zuletzt von Peter S. Taler (17. Dezember 2022 um 11:19)

  • Ist das sotwas wie hier erklärt?

    Map stellt tatsächlich - wie in deinem Link beschrieben - eine Liste von Schlüssel-Wert-Paaren dar.

    In AutoIt wurde hierfür bisher das externe Scripting.Dictionary-Objekt verwendet.

    Nun gibt es mit den Maps eine native AutoIt-Struktur hierfür.

    Wenn ja - wo ist der Vorteil gegnüber einem Komma getrennten Datensatz oder eben einem Array.

    Eine Kommagetrennter Datenssatz ist im Grunde etwas ganz anderes.
    Eine Map oder ein Array, eine List usw. sind programmiertechnische Datenstrukturen mit denen in einem Programm direkt gearbeitet werden kann.

    Eine csv hingegen ist eine Festlegung wie man Daten speichert oder austauscht.
    Um sie in einem Programm weiterzuverarbeiten muss man sie erst in eine programmiertechnische Datenstruktur konvertieren - z.B. ein Array oder eben auch eine Map (wenn es denn 2 Spalten hat).

    Der Vorteil gegenüber Arrays ist, dass der Index eben ein ganz anderer ist.
    Ein Array ist durchnummeriert. Um auf ein Element zuzugreifen, dessen Position man nicht kennt muss man das ganze Array durchgehen.

    Die AutoIt-Map hingegen ist als Hash-Tabelle implementiert.
    Dort wird die Position des Elementes anhand des Schlüssels berechnet.
    Hat man z.B. eine Map mit Postleitzahlen als Key und den Ort als Wert dann bekommt man ratz fatz den Ort zu irgendeiner Postleitzahl ohne die ganze Struktur erst durchgehen zu müssen.

    Zwar kann man auch in Arrays deutlich schneller suchen wenn man diese vorher sortiert - aber bei einer Map braucht man das nicht.

    Ein weiterer Vorteil ist, dass ein Hinzufügen und Entfernen von Elementen in Maps deutlich fixer vonstatten geht.

    Ein Array hingegen ist schneller und speicher-sparsamer wenn man alle Elemente durchiterieren muss oder direkt auf Elemente zugreift deren Index bekannt ist.

    Außerdem müssen halt auch die Daten zur Struktur passen.
    Wenn es keine sinnvolle Schlüssel-Wert-Beziehung in den Daten gibt die man dann tatsächlich auch programmiertechnisch ausnutzen kann, dann wäre eine Map nicht die richtige Wahl.

  • AspirinJunkie

    Danke für die Erklärung

    LG

    Peter

    Hinweise auf Suchmaschinen finde ich überflüssig - wer fragt hat es nicht gefunden oder nicht verstanden. Die Antwort gibt sich oftmals schneller als der Hinweis auf Dr. Goggle & Co.

    Ab 19-10-22 ergänzt um:

    Die Welt wird nicht bedroht von den Menschen, die böse sind, sondern von denen, die das Böse zulassen. (Albert Einstein)

  • Hi AspirinJunkie ,

    ja wirklich gut erklärt. Warst schneller als ich, ich wollte auch was dazu schreiben, doch dies muss ich nun nicht mehr 😅 , Danke.

    Viele Grüße
    Sven

  • Die List.au3 ist eigentlich eher ausversehen entstanden (habe ich für ein anderes Projekt gebraucht und erschreckt festgestellt, dass es in AutoIt immernoch keine (native) LinkedList Implementierung gibt). Ich glaube in 95% der Fälle ist ein einfaches Array, oder eine Map ohne den List-Wrapper die bessere Wahl, aber für die wenigen Fälle wo das nicht so ist gibt es jetzt diese UDF mit der man eine DoublyLinkedList mit Iterator verwenden kann.

    lg

    M