使用 Lisp（或 AutoLisp）关联列表的性能有多好？
我正在做一个 AutoLisp 项目，它使用长关联结构来进行繁重的几何处理 - 所以我对关联列表密集使用计时结果感到好奇。 实施的简单/复杂程度如何？ 它使用某种数据结构或普通的点对列表？ 有b树之类的扩展吗？
I'm doing an AutoLisp project which uses long associative structures to do heavy geometrical processing - so I'm curious about the associative list intense use timing results.
How simple/complex is the implementation? It uses some data structure or a normal list of dotted pairs?
The are any extension for b-tree or something?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
假设访问均匀分布，最近 x86 硬件上的 SBCL 在 alist 和基于身份的哈希表之间的转折点约为 30-40 个元素。
the turning point for SBCL on recent x86 hardware between alists and identity based hashtables, assuming even distribution of access, is around 30-40 elements.
在 Common Lisp 和 Emacs Lisp 中，关联列表是链表，因此它们具有线性搜索时间。 假设 AutoLisp 是相同的（如果不是，那么他们使用术语“关联列表”会产生误导），您可以假设所有操作在列表的长度上都是线性的。 例如，一个包含 100 个元素的列表平均需要 50 次访问才能找到您要查找的内容。
In Common Lisp and Emacs Lisp association lists are linked lists, so they have linear search time. Assuming that AutoLisp is the same (and if it isn't, then their use of the term "Associative List" is misleading), you can assume that all operations will be linear in the length of the list. For example, an alist with 100 elements will, on average, need 50 accesses to find the thing that you are after.
当然，大多数Scheme 实现（或者可能是在规范中？）都有哈希表，它们大多使用相同的API； 但它不是透明的，当你请求一个列表时，你会得到一个对的列表，如果你想要一个哈希表，就请求它。
也就是说，重要的是要记住线性算法并不慢； 它们是“不可扩展的”。 对于少量元素，它们将胜过更复杂的“聪明”算法。 “n”必须有多大，很大程度上取决于算法，以及具有大缓存但 RAM 较慢的快速处理器，请继续推动它。 此外，重度优化编译器（如某些 Lisp 上可用的编译器）会生成非常的线性代码。
Of course, most Scheme implementations (or maybe it's in the specs?) have hashtables, which use mostly the same API; but it's not transparent, when you ask for an alist, you get a list of pairs, if you want a hashtable, ask for it.
that said, it's important to remember that linear algorithms aren't slow; they're 'unscalable'. for a small number of elements, they'll outperform a more complex 'clever' algorithm. just how large 'n' has to be, depends a lot on the algorithm, and fast processors with big caches but slow RAM, keep pushing it. Also, heavy optimising compilers (like those available on some Lisp's) generate very tight linear code.
我大约有 10 年没有使用 AutoLisp，但我从未发现关联列表操作有任何真正的性能问题。 我编写了可以进行大量关联列表操作的代码。
使用 VBA 或 ObjectARX 可能会带来一些性能优势，但您可能需要运行一些比较测试来查看它是否真的更好。
I have not worked with AutoLisp in about 10 years, but I never found any real performance issues with association list manipulation. And I wrote code that would do a fair amount of association list manipulation.
Working in VBA or ObjectARX might have some performance benefits, but you would probably need to run some comparison testing to see if it is really better.
据我所知，b 树没有扩展，但如果您使用 Visual LISP，则可以使用 ActiveX 对象，从而访问大多数类型的数据库。
There is no extension for b-tree that I know of but if you use Visual LISP you can use ActiveX objects and thus access most types of databases.