Mit Lisp (oder AutoLisp) wie gut ist die assoziativen Listen Leistung?
https://stackoverflow.com/questions/262628
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich bin ein AutoLisp Projekt zu tun, die lange assoziativen Strukturen verwendet schwere geometrische Verarbeitung zu tun - so bin ich neugierig auf die assoziative Liste intensive Nutzung Ergebnisse Timing. Wie einfach / komplex ist die Umsetzung? Es verwendet eine Datenstruktur oder eine normale Liste der punktierten Paare? Das ist jede Erweiterung für b-Baum oder etwas?
Lösung
In Common Lisp und Emacs Lisp Assoziationslisten Listen verbunden sind, so dass sie linear Suchzeit. Unter der Annahme, dass AutoLisp das gleiche ist (und wenn es nicht ist, dann ist ihre Verwendung des Begriffs „Assoziative List“ ist irreführend), können Sie davon ausgehen, dass alle Operationen linear in der Länge der Liste sein. Zum Beispiel kann ein alist mit 100 Elementen werden im Durchschnitt 50 müssen greift auf die Sache zu finden, die Sie nach.
Andere Tipps
der Wendepunkt für SBCL auf den letzten x86-Hardware zwischen Alists und identitätsbasierten Hash-Tabellen, unter der Annahme, eine gleichmäßige Verteilung des Zugangs, ist etwa 30 bis 40 Elemente.
Natürlich, die meisten Scheme-Implementierungen (? Oder vielleicht ist es in den Spezifikationen) haben Hashtables, die meist die gleiche API verwenden; aber es ist nicht transparent, wenn Sie für einen alist fragen Sie eine Liste von Paaren bekommen, wenn Sie eine Hash-Tabelle wollen, um sie bitten.
Das heißt, es ist wichtig, sich daran zu erinnern, dass lineare Algorithmen sind nicht verlangsamen; sie sind ‚unbezwingbar‘. für eine kleine Anzahl von Elementen, werden sie eine komplexere ‚klug‘ Algorithmus entwickeln. wie groß ‚n‘ sein, hängt viel von dem Algorithmus und schnelle Prozessoren mit großen Caches, aber langsam RAM, halten Sie es gedrückt wird. Auch schwere optimierende Compiler (wie die auf einige Lisp der) erzeugen sehr fest linearer Code.
Ich habe nicht mit AutoLisp in etwa 10 Jahren gearbeitet, aber ich fand nie ein wirklichen Performance-Probleme mit Assoziationsliste Manipulation. Und ich schrieb Code, der einen fairen Betrag von Assoziationsliste Manipulation tun würde.
Arbeiten in VBA oder ObjectARX könnten einige Leistungsvorteile haben, aber Sie müssten wahrscheinlich einige Vergleichstests laufen, um zu sehen, ob es wirklich besser ist.
Es gibt keine Erweiterung für b-Baum, die ich kenne, aber wenn Sie Visual LISP verwenden Sie ActiveX-Objekte verwenden können und damit Zugriff auf die meisten Arten von Datenbanken.
