1

シーケンスが順番に処理される場合はリストを優先し、要素にランダムにアクセスする必要がある場合は配列を優先する必要があると思いました。

そこで、自分の考えを確認するために数行のコードを記述します。まず、ポイントマルチプルをテストする関数を作成しました。そしてそれはそれがリストでより速く動くことを示します。

でもそれからソート機能を試してみました。ソート関数は要素にランダムにアクセスする必要があるため、配列でより高速に実行されると思います。しかし、結果は逆です。

(defun test-performance-map-mapcar ()
  (let* ((lst (generate-random 1000000))
     (arr (lst-to-arr lst)))
    (time (atom (sort lst #'>)))
    (time (atom (sort arr #'>)))))

それで、ソート関数はリストに適応するためにある種のアルゴリズムを適用しますか、それともリストはlispの配列よりもはるかに効率的ですか？

4

2 に答える 2

4

再現できません。

乱数のベクトルのソートは、LispWorks で乱数のリストをソートするよりも高速です。

(defun test ()
  (let* ((list (loop repeat 10000000 collect (random 1000000)))
         (vector (coerce list 'vector)))
    (time (sort list #'>))
    (time (sort vector #'>))
    (values)))

例：

CL-USER 9 > (test)
Timing the evaluation of (SORT LIST (FUNCTION >))

User time    =        8.697
System time  =        0.027
Elapsed time =        8.626
Allocation   = 170168 bytes
145 Page faults
Timing the evaluation of (SORT VECTOR (FUNCTION >))

User time    =        5.951
System time  =        0.018
Elapsed time =        5.904
Allocation   = 120512 bytes
86 Page faults

ベクトルの場合は 5.951 秒、リストの場合は 8.697 秒です。

Common Lisp では、1 次元配列は正確にベクトルです。SORT他の多次元配列でも機能しません。

CL-USER 10 > (vector 'a 'b 'c)
#(A B C)

CL-USER 11 > (describe *)

#(A B C) is a (SIMPLE-VECTOR 3)
0      A
1      B
2      C

CL-USER 12 > (arrayp **)
T

CL-USER 13 > (typep (vector 'a 'b 'c) '(array symbol (3)))
T

したがって、3 つのシンボルのベクトルは、長さ 3 の element-type の 1 次元配列でもありSYMBOLます。

私の例 (Intel i7 プロセッサを搭載した Apple Macbook Air) の場合:

Implementation   | faster | seconds
-----------------+--------+--------
LispWorks 64bit  | vector |  5.951
Clozure CL 64bit | vector |  6.727
SBCL 1.1 64bit   | list   |  8.890
CLISP            | list   | 42.968
于 2012-10-22T10:33:25.527 に答える
3

配列対リストについて既に述べたことに加えて、「最速」のソートアルゴリズムなどはありません。これは最終的に、どのデータをソートするかによって異なります。同様の値を含むコレクションでパフォーマンスが向上するアルゴリズムもあれば、ほぼソートされた値を含むコレクションでパフォーマンスが向上するアルゴリズムもあります。

実際には、並べ替え中に追加のコンスが作成されたり、配列の並べ替え中に追加のメモリが割り当てられたりするなど、他の複雑な問題が発生する場合があります。絶対に潮流をひっくり返すかもしれない GC への呼び出しを必要とする何か。

並べ替えが必要な特定の実際的な問題がある場合は常に、状況と扱うデータの種類を考慮する必要があります。たとえば、アニメーションのレンダリング中の 3 次元空間での Z 頂点の並べ替えは、リンクされたリストとほぼ並べ替えられたデータで動作するアルゴリズムからおそらく最も恩恵を受けるでしょう。以前はソートされていなかったほとんどが一意のデータ。一部の特定のソフトウェアは、ベクトル化された挿入ソートを実行できます。これは、操作アルゴリズムごとに単一の値よりも何倍も高速です。

乱数のコレクションをソートすることは、通常、コードが実際のデータに対してどのように実行されるかを示す指標にはなりません。

于 2012-10-22T01:13:49.073 に答える