Usando Lisp (o AutoLisp), ¿qué tan bueno es el rendimiento de las listas asociativas?
https://stackoverflow.com/questions/262628
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Estoy haciendo un proyecto AutoLisp que utiliza estructuras asociativas largas para realizar un procesamiento geométrico pesado, por lo que tengo curiosidad acerca de los resultados de temporización de uso intensivo de la lista asociativa. ¿Qué tan simple / compleja es la implementación? ¿Utiliza alguna estructura de datos o una lista normal de pares de puntos? ¿Hay alguna extensión para b-tree o algo así?
Solución
En Common Lisp y Emacs Lisp, las listas de asociación son listas enlazadas, por lo que tienen un tiempo de búsqueda lineal. Suponiendo que AutoLisp es el mismo (y si no lo es, entonces su uso del término "Lista asociativa" es engañoso), puede suponer que todas las operaciones serán lineales en la longitud de la lista. Por ejemplo, una lista con 100 elementos necesitará, en promedio, 50 accesos para encontrar lo que busca.
Otros consejos
el punto de inflexión para SBCL en hardware x86 reciente entre listas y hashtables basados ??en identidad, suponiendo una distribución uniforme del acceso, es de alrededor de 30-40 elementos.
Por supuesto, la mayoría de las implementaciones de Scheme (¿o tal vez está en las especificaciones?) tienen tablas hash, que utilizan principalmente la misma API; pero no es transparente, cuando solicita una lista, obtiene una lista de pares, si desea una tabla hash, solicítela.
Dicho esto, es importante recordar que los algoritmos lineales no son lentos; son 'no escalables'. para una pequeña cantidad de elementos, superarán a un algoritmo 'inteligente' más complejo. cuán grande debe ser 'n', depende mucho del algoritmo, y los procesadores rápidos con grandes cachés pero RAM lenta, continúen presionando. Además, los compiladores de optimización pesados ??(como los disponibles en algunos Lisp) generan muy código lineal ajustado.
No he trabajado con AutoLisp en aproximadamente 10 años, pero nunca encontré ningún problema de rendimiento real con la manipulación de la lista de asociación. Y escribí un código que haría una buena cantidad de manipulación de la lista de asociación.
Trabajar en VBA u ObjectARX puede tener algunos beneficios de rendimiento, pero probablemente deba ejecutar algunas pruebas de comparación para ver si es realmente mejor.
No conozco ninguna extensión para b-tree, pero si usa Visual LISP puede usar objetos ActiveX y acceder a la mayoría de los tipos de bases de datos.
