Utilisation de Lisp (ou AutoLisp) Quelle est la qualité des performances des listes associatives?
https://stackoverflow.com/questions/262628
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je fais un projet AutoLisp qui utilise de longues structures associatives pour effectuer un traitement géométrique complexe. Je suis donc curieux de connaître les résultats de chronométrage d'utilisation intensive de la liste associative. Dans quelle mesure la mise en œuvre est-elle simple / complexe? Il utilise une structure de données ou une liste normale de paires en pointillés? Existe-t-il une extension pour b-tree ou quelque chose comme ça?
La solution
Dans Common Lisp et Emacs, les listes d’associations Lisp sont des listes chaînées, elles ont donc une durée de recherche linéaire. En supposant qu'AutoLisp soit identique (et si ce n'est pas le cas, leur utilisation du terme "liste associative" est trompeuse), vous pouvez supposer que toutes les opérations seront linéaires dans la longueur de la liste. Par exemple, une liste de 100 éléments nécessitera en moyenne 50 accès pour trouver le but recherché.
Autres conseils
le point tournant pour SBCL sur le matériel x86 récent entre les listes d'identification et les tables de hachage basées sur l'identité, en supposant une distribution uniforme de l'accès, est d'environ 30 à 40 éléments.
Bien sûr, la plupart des implémentations de Scheme (ou peut-être est-ce dans les spécifications?) ont des hashtables, qui utilisent principalement la même API; mais ce n'est pas transparent, lorsque vous demandez une liste, vous obtenez une liste de paires, si vous voulez une table de hachage, demandez-la.
Cela dit, il est important de se rappeler que les algorithmes linéaires ne sont pas lents; ils sont "indestructibles". pour un petit nombre d'éléments, ils surperforment un algorithme plus «intelligent» plus complexe. La taille de ce "n" dépend en grande partie de l'algorithme, et des processeurs rapides avec de gros caches, mais une RAM lente, continuent de le pousser. De plus, les compilateurs d'optimisation lourds (comme ceux disponibles sur certains Lisp) génèrent un code très très serré.
Je n'ai pas travaillé avec AutoLisp depuis environ 10 ans, mais je n’ai jamais rencontré de problème de performances réel avec la manipulation de la liste d’association. Et j’ai écrit un code qui ferait pas mal de manipulations de listes d’associations.
L'utilisation de VBA ou d'ObjectARX peut présenter des avantages en termes de performances, mais vous devrez probablement effectuer des tests de comparaison pour voir si c'est vraiment mieux.
À ma connaissance, il n'y a pas d'extension pour b-tree, mais si vous utilisez Visual LISP, vous pouvez utiliser des objets ActiveX et accéder ainsi à la plupart des types de bases de données.
