Die Komplexität von Schema Vektoren

Question

Der 6.3.6 Vectors Abschnitt in den Schema R5RS Standard besagt folgendes über Vektoren:

Vektoren sind heterogene Strukturen, deren Elemente durch ganze Zahlen indiziert. Ein Vektor belegt typischerweise weniger Platz als eine Liste gleicher Länge, und die durchschnittliche Zeit, die für den Zugriff auf ein zufällig ausgewähltes Element benötigt wird, ist typischerweise für den Vektor geringer als für die Liste.

Diese Beschreibung der Vektoren ist ein bisschen diffus.

würde ich gerne wissen, was das eigentlich bedeutet in Bezug auf die vector-ref und list-ref Operationen und deren Komplexität. Beide Prozeduren geben das k-te Element eines Vektors und eine Liste zurück. Ist die Vektoroperation O (1) und ist die Listenoperation O (n)? Wie unterscheiden sich Vektoren von Listen? Wo finde ich weitere Informationen?

Im Moment verwende ich Assoziationslisten als Datenstruktur zum Speichern von Schlüssel/Wert-Paaren für die einfache Suche. Wenn die Schlüssel ganze Zahlen sind, wäre es vielleicht besser, Vektoren zum Speichern der Werte zu verwenden.

Answer 1

Die sehr spezifischen Details vector-ref und list-ref sind implementierungsabhängig, das heißt: jede Scheme-Interpreter die Spezifikation implementieren kann, wie es für richtig hält, so eine Antwort auf Ihre Frage an alle Dolmetscher kann es nicht zu R5RS, in Übereinstimmung verallgemeinert werden hängt auf dem tatsächlichen Interpreter, den Sie verwenden.

Aber ja, in jeder anständigen Implementierung ist eine sichere Wette anzunehmen, dass die vector-ref Operation ist O (1), und dass die list-ref Operation wahrscheinlich ist O (n). Warum? weil ein Vektor unter der Haube unter Verwendung einer Datenstruktur implementiert werden sollte, die für die Implementierungssprache nativ ist, die O (1) Zugriff auf ein Element mit seinem Index (z. B. ein primitives Array) erlaubt - daher die Implementierung von vector-ref einfach. Während Listen in Lisp durch Verknüpfen von cons Zellen erstellt werden, und das Auffinden eines Elements in einem beliebigen gegebenen Index bedeutet, dass alle Elemente davor in der Liste durchlaufen werden müssen - daher O (n) -Komplexität. Als Randnotiz - ja, die Verwendung von Vektoren wäre eine schnellere Alternative als die Verwendung von Assoziationslisten von Schlüssel/Wert-Paaren, solange die Schlüssel Integer sind und die Anzahl der zu indizierenden Elemente vorher bekannt ist (ein Scheme-Vektor) kann seine Größe nach der Erstellung nicht vergrößern). Für den allgemeinen Fall (andere Schlüssel als ganze Zahlen, variable Größe) überprüfen Sie, ob Ihr Interpreter Hash-Tabellen unterstützt, oder verwenden Sie eine externe Bibliothek, die diese zur Verfügung stellt (z. B. SRFI 69).

Answer 2

Eine Liste besteht aus cons Zellen. Von der R⁵RS list section:

Die Objekte in den Auto-Feldern der aufeinander folgenden Paare einer Liste sind die Elemente der Liste. Zum Beispiel ist eine Liste mit zwei Elementen ein Paar, dessen Auto das erste Element ist und dessen cdr ein Paar ist, dessen Auto das zweite Element ist und dessen cdr die leere Liste ist. Die Länge einer Liste ist die Anzahl der Elemente, die der Anzahl der Paare entspricht.

Zum Beispiel kann die Liste (a b c) entspricht die folgende Reihe von Paaren: (a . (b . (c .())))

und konnte durch den folgenden „Knoten“ im Speicher dargestellt werden: []

[p] --> [p] --> [p] --> null 
|  |  | 
|==> a |==> b |==> c 

jeden Knoten enthält einen Zeiger auf den Wert (es ist car), und einen weiteren Zeiger auf das nächste Element (es ist cdr).

Dadurch kann die Liste auf eine unbegrenzte Länge anwachsen, aber eine ref Operation muss am Anfang der Liste beginnen und k Elemente durchlaufen, um die gewünschte zu finden. Wie Sie gesagt haben, ist dies O (n).

---

dagegen ein Vektor ist im Grunde eine Anordnung von Werten, die intern als ein Array von Zeigern dargestellt werden könnten.

[p p p] 
| | | 
| | |==> c 
| | 
| |==> b 
| 
|==> a 

Wo das Array [] eine Reihe von drei Zeigern enthält, und jeder Zeiger auf einen Wert in dem Vektor zugeordnet ist: Zum Beispiel könnte der Vektor #(a b c) dargestellt werden. So könnten Sie intern das dritte Element des Vektors v mit der Notation v[3] referenzieren. Da Sie die vorherigen Elemente nicht durchlaufen müssen, ist vector-ref eine O (1) -Operation.

Der Hauptnachteil ist, dass Vektoren eine feste Größe haben. Wenn Sie also mehr Elemente hinzufügen müssen, als der Vektor halten kann, müssen Sie einen neuen Vektor zuweisen und die alten Elemente in diesen neuen Vektor kopieren. Dies kann möglicherweise eine teure Operation sein, wenn Ihre Anwendung dies regelmäßig tut.

---

Es gibt viele Online-Ressourcen - dieser Artikel auf Scheme Data Structures geht mehr ins Detail und liefert einige Beispiele, obwohl es viel mehr auf Listen ist.

---

Alles, was gesagt, wenn Ihre Schlüssel sind (oder werden kann) ganze Zahlen sind und Sie entweder eine feste Anzahl von Elementen haben oder können mit einer angemessenen Menge von Vektor-Umschichtungen verwalten - zum Beispiel, laden Sie den Vektor beim Start und dann meist Lesevorgänge ausführen - ein Vektor kann eine attraktive Alternative zu einer Assoziationsliste sein.