3

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

4

5 に答える 5

4

最近の x86 ハードウェアでの SBCL のアリストと ID ベースのハッシュテーブルの間の転換点は、アクセスが均等に分散されていると仮定すると、約 30 ～ 40 要素です。

于 2008-11-05T10:39:24.253 に答える
2

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

于 2008-11-04T17:48:05.607 に答える
2

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

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

于 2008-11-04T17:50:44.180 に答える
1

私は約 10 年間 AutoLisp を使用していませんが、連想リストの操作に関する実際のパフォーマンスの問題は見つかりませんでした。そして、かなりの量の連想リスト操作を行うコードを書きました。

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

于 2008-11-04T17:54:42.753 に答える
0

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

于 2008-12-28T15:27:35.387 に答える