4

Lisp のリスト プリミティブでは、演算子の長さが次のように定義されています。

(define (length lst)
  (if (null? lst) 0 (+ 1 (length (cdr lst)))))

一部の Lisp の実装者は、長さを一定時間で計算されるプリミティブにできないのはなぜですか?

ありがとう

4

4 に答える 4

11

その理由は、Lispでのリストの「従来の」実装です。他の場所では、リストは配列と同様に実装されることがあります。したがって、リストを作成するとき、それは単一の自己完結型のものです。

An array-like list: [ 1 2 3 4 5 6 ]

アイテム（たとえば「0」）をそのリストの先頭に追加したい場合（そしてリストの実装が単純であると仮定すると）、リスト内のすべてのアイテムが上（右）にシフトされます。次に、「0」が新しい場所にインストールされます。

Step 0. [ 1 2 3 4 5 6 ]
Step 1. [   1 2 3 4 5 6 ] (Shift Right)
Step 2. [ 0 1 2 3 4 5 6 ] (Insert)

それは（従来の）Lispリストのやり方ではありません。リストのすべてのアイテムは、次のアイテムを指す個別のピースです。リストの一部は「conses」と呼ばれます。（これはリンクリストと呼ばれます。）

[1] -> [2] -> [3] -> [4] -> [5] -> [6] -> nil

は？さて、それらのアイテムのそれぞれは短所セルです。また、各consセルには、carとcdrの2つの値があります。（consセルをリストで使用する場合は、「car」と「cdr」を「first」と「rest」と考えるとよいでしょう。「First」は、数値やリンクなど、リストに保持するデータをすべて保持します。他のリスト。「Rest」はリストの残りを保持します。実際には「rest」の部分に好きなものを入れることもできますが、ここでは無視します。）「Nil」は「空のリスト」であり、基本的には「空のリスト」です。 「リストが終了しました！」という意味です。

では、「0」を再び前面に追加したい場合はどうでしょうか。

[0] -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> nil

見る？古いリストの先頭を指す新しいconsセルを作成しました。人々がこれを「consing」という価値を前面に出すのを聞くでしょう。ただし、リストの残りの部分は変更されていないことに気付くでしょう。

さて、しかしなぜ誰かがこれを望んでいるのですか？リストを共有できます。2つの基本的に同一のリストが必要だと想像してください。今だけ、1つのリストを「7」で開始し、もう1つのリストを「4」で開始したいとしましたか？配列のような方法では、2つのリストが必要になります。

[ 7 0 1 2 3 4 5 6 ]
[ 4 0 1 2 3 4 5 6 ]

「5」を「13」に置き換えて、変更を共有した場合はどうなりますか？

[ 7 0 1 2 3 4 13 6 ]
[ 4 0 1 2 3 4 5 6 ]

2つの完全に別個のリストがあります。変更を共有する場合は、両方のリストで変更を加える必要があります。

従来のLispリストはどうなりますか？まず、「7」と「4」を前面に貼り付けます。

[7]
   \
    ----> [0] -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> nil
   /
[4]

うん。どちらも古いリストを指している2つのコンスを作成しました。リストの残りの部分は共有されます。そして、「5」を「13」に置き換えると、次のようになります。

[7]
   \
    ----> [0] -> [1] -> [2] -> [3] -> [4] -> [13] -> [6] -> nil
   /
[4]

残りは共有されているため、両方のリストが変更されます。

このすべてのポイントは、多くの人々が期待するものとは異なり、従来のLispリストは単一のものではないということです。それらは、リストであるチェーンを形成するために互いに指し示す小さなもの（conses）の束です。チェーンの長さを取得したい場合は、最後に到達するまで、すべての小さなリンクをたどる必要があります、nil。したがって、O（n）の長さ。

Lispリストは、配列のように実行された場合、O（1）にすることができます。いくつかのあいまいなLispがこれを行い、リンクリスト（conses）を完全に取り除くと確信しています。しかし、consesは、基本的にすべての人気のあるLisp方言に浸透するものの1つであるように思われます。O（1）の長さとルックアップが必要な場合、それらのほとんどは配列またはベクトルも提供します。

リンクリストの楽しみ：

 -----------------<------------------------<----------
|                                                     |
 --> [0] -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -->

このリンクリストは、最終的にはそれ自体を指します。長さ関数を使用すると、それは永久にループし、終わりを探しますが、それを見つけることはありません。

于 2011-06-21T07:28:48.850 に答える
3

ほとんどのLisp方言には、プリミティブデータ型としてのリストがありません。たとえば、Common Lispでは、リストはconsセルと空のリスト（別名NIL）で構成されています。consセルは、CARとCDRの2つのフィールドを持つデータ構造です。短所セルとNILを使用すると、単一リンクリスト、連想リスト、循環リスト、ツリーなど、多くのデータ構造を提供できます。

Lispは別の方法で（consesなしで）リストを実装できたかもしれませんが、一般的にはそうではありません。

ところで、CommonLispにはフィルポインタ付きの調整可能な配列があります。塗りつぶしポインタは、O（1）の長さを提供します。

于 2011-06-20T23:20:37.173 に答える
1

プレーンリンクリストの場合はO（n）ですが、他のデータ構造も利用できます。たとえば、ClojureはO（1）カウントでListとVectorを実装します。

于 2011-06-20T20:50:33.770 に答える
1

スペースのコストを正当化するのに十分なほど頻繁にリストの長さを尋ねる人はいないからです。もしそうなら、あなたはそれを間違っています。

于 2011-06-20T20:53:09.417 に答える