使用Lisp（或AutoLisp）關聯列表性能有多好？

我正在做一個AutoLisp項目，它使用長關聯結構來進行重型幾何處理 - 所以我很好奇關聯列表激烈使用時間結果。實施過程簡單/複雜嗎？它使用一些數據結構或一個普通的虛線對列表？是什麼擴展爲B樹或什麼的？使用Lisp（或AutoLisp）關聯列表性能有多好？

2008-11-04 user13383

在通用Lisp和Emacs Lisp關聯列表中是鏈表，因此它們具有線性搜索時間。假設AutoLisp是相同的（如果不是，那麼他們對術語「關聯列表」的使用是誤導性的），則可以假定所有操作在列表長度上都是線性的。例如，一個有100個元素的alist平均需要50次訪問才能找到你以後的東西。

2008-11-04 17:48:05 Glomek

請在下面查看我對crashmstr答案的評論。 – user13383 2008-11-04 19:37:07

當然，大多數Scheme實現（或者它在規範中？）都有散列表，它們大多使用相同的API;但它不透明，當你要求一個alist的時候，你會得到一個成對的列表，如果你想要一個hashtable，請求它。

表示，重要的是要記住線性算法並不慢;他們是'不可擴充的'。對於少數元素，它們將超越更復雜的「聰明」算法。只有'n'有多大，取決於算法，快速處理器和大緩存但是RAM速度很慢，不斷推動它。此外，重優化編譯器（如某些Lisp的可用編譯器）會生成非常嚴密的線性代碼。

2008-11-04 17:50:44 Javier

我在10年左右沒有使用過AutoLisp，但我從來沒有發現任何關聯列表操作的真正性能問題。而且我編寫了可以執行大量關聯列表操作的代碼。

使用VBA或ObjectARX可能會有一些性能優勢，但您可能需要運行一些比較測試以確定它是否真的更好。

2008-11-04 17:54:42 crashmstr

我做了一個快速測試，在10k元素關聯列表中進行三次搜索：從0到100的50k個隨機元素;然後從9900到10000;然後從0到10000（所有範圍）。結果是：0.2173秒，22.0785秒和11.1284秒。所以，我認爲它是線性的。 – user13383 2008-11-04 19:35:06

在Alist和基於身份的散列表之間的近期x86硬件上，SBCL的轉折點，假設訪問的均勻分佈，大約有30-40個元素。

2008-11-05 10:39:24

我知道B樹沒有擴展名，但如果使用Visual LISP，則可以使用ActiveX對象，從而訪問大多數類型的數據庫。

2008-12-28 15:27:35

回答