lisp - 使用 Lisp（或 AutoLisp）的关联列表性能有多好？

Question

我正在做一个 AutoLisp 项目，它使用长关联结构来进行繁重的几何处理——所以我对关联列表的密集使用时间结果很好奇。实现有多简单/复杂？它使用一些数据结构还是普通的点对列表？b-tree 有什么扩展名吗？

Answer 1

在最近的 x86 硬件上，SBCL 在 alist 和基于身份的哈希表之间的转折点，假设访问分布均匀，大约是 30-40 个元素。

Answer 2

在 Common Lisp 和 Emacs Lisp 中，关联列表是链表，因此它们具有线性搜索时间。假设 AutoLisp 是相同的（如果不是，那么他们对术语“关联列表”的使用具有误导性），您可以假设所有操作在列表长度上都是线性的。例如，具有 100 个元素的 alist 平均需要 50 次访问才能找到您想要的东西。

Answer 3

当然，大多数 Scheme 实现（或者可能在规范中？）都有哈希表，它们使用的 API 大多相同。但这不是透明的，当你要求一个列表时，你会得到一个配对列表，如果你想要一个哈希表，就要求它。

也就是说，重要的是要记住线性算法并不慢；它们是“不可扩展的”。对于少数元素，它们将胜过更复杂的“聪明”算法。'n' 必须有多大，很大程度上取决于算法，以及具有大缓存但 RAM 慢的快速处理器，继续推动它。此外，重度优化编译器（如某些 Lisp 上可用的编译器）会生成非常紧凑的线性代码。

Answer 4

我已经有大约 10 年没有使用过 AutoLisp 了，但我从未发现任何与关联列表操作有关的真正性能问题。而且我编写了可以进行大量关联列表操作的代码。

在 VBA 或 ObjectARX 中工作可能会带来一些性能优势，但您可能需要运行一些比较测试以查看它是否真的更好。

Answer 5

据我所知，b-tree 没有扩展，但如果您使用 Visual LISP，您可以使用 ActiveX 对象，从而访问大多数类型的数据库。