Lisp（またはAutoLisp）を使用すると、連想リストのパフォーマンスはどの程度向上しますか？

Question

長い連想構造を使用して重い幾何学的処理を行うAutoLispプロジェクトを行っています。そのため、連想リストの激しい使用タイミングの結果に興味があります。 実装はどの程度単純/複雑ですか？データ構造または点線ペアの通常のリストを使用しますか？ Bツリーなどの拡張機能はありますか？

Answer 1

Common LispとEmacs Lispの関連リストはリンクリストであるため、検索時間が線形になります。 AutoLispが同じであると仮定すると（そして、そうでない場合は、「連想リスト」という用語の使用は誤解を招く）、すべての操作がリストの長さで線形になると仮定できます。たとえば、100個の要素を持つalistは、平均で50回アクセスして必要なものを見つける必要があります。

Answer 2

アクセスの均等な分散を想定した、リストとIDベースのハッシュテーブル間の最近のx86ハードウェア上のSBCLのターニングポイントは、約30〜40要素です。

Answer 3

もちろん、ほとんどのScheme実装（または仕様にあるのでしょうか？）には、ほとんど同じAPIを使用するハッシュテーブルがあります。しかし、それは透過的ではありません。リストを要求すると、ペアのリストが取得されます。ハッシュテーブルが必要な場合は、要求してください。

とはいえ、線形アルゴリズムは遅くないことを覚えておくことが重要です。それらは「スケーラブルではありません」。少数の要素については、より複雑な「賢い」アルゴリズムよりも優れています。 「n」の大きさはアルゴリズムに大きく依存します。また、キャッシュは大きいがRAMが遅い高速プロセッサは、それを押し続けます。また、重い最適化コンパイラ（一部のLispで利用可能なものなど）は、非常にタイトな線形コードを生成します。

Answer 4

約10年間AutoLispを使用したことはありませんが、アソシエーションリストの操作で実際のパフォーマンスの問題を発見したことはありません。そして、かなりの量の関連リスト操作を行うコードを書きました。

VBAまたはObjectARXで作業するとパフォーマンスが向上する場合がありますが、比較テストを実行して本当に優れているかどうかを確認する必要があります。

Answer 5

私が知っているBツリーの拡張機能はありませんが、Visual LISPを使用している場合は、ActiveXオブジェクトを使用できるため、ほとんどの種類のデータベースにアクセスできます。