回答編集履歴
4
用語の変更
answer
CHANGED
|
@@ -1,4 +1,4 @@
|
|
|
1
|
-
Arrayは順番付きの静的な列を効率よく実現できるデータ構造ですけど、
|
|
1
|
+
Arrayは順番付きの静的な列を効率よく実現できるデータ構造ですけど、構造の共有に適した構造ではありません。例えばJavascriptのArrayやPythonのlistでLispのリストを実現したとしますと以下のことが簡単には実現できないと思います。
|
|
2
2
|
|
|
3
3
|
```lisp
|
|
4
4
|
(setq a '(a b c)) ;; a = (a b c)
|
3
追記
answer
CHANGED
|
@@ -8,4 +8,9 @@
|
|
|
8
8
|
|
|
9
9
|
lispでも何でもかんでも構造の共有を起こすわけではなく、他のリストと共通部分を持たないという仮定を置くべきケースと共通部分を持つという前提のものが両方出てきます。しかしながら少なくとも後者が充分効率的に実装できる必要があります。
|
|
10
10
|
|
|
11
|
-
その理由で一般の配列は向いておらずlinked listつまりドット対のようなデータ構造にする必要があると考えるとよいと思います。
|
|
11
|
+
その理由で一般の配列は向いておらずlinked listつまりドット対のようなデータ構造にする必要があると考えるとよいと思います。
|
|
12
|
+
|
|
13
|
+
---
|
|
14
|
+
ただ・・・ドット対はランダムアクセスに向いた構造ではないとかメモリー効率がよくないといった理由で、Lispの実装でも「他と共有部分がない」とか「cdrでリストの部分列をトラバースするのではなく要素をインデックスでアクセスするのが主」というケースでは内部的に配列を用いるような最適化は考えられると思います。さらに構造を変更しないという前提が置けるケースではcdrの結果として「実体の配列とその何番目以降を指しているかのインデックス」を用いてリストの部分共有を実現するなどといった工夫も考えられると思います。
|
|
15
|
+
|
|
16
|
+
Lispのドット対は外部仕様は極めて単純ながら内部の実装はこういった様々な工夫をする余地があるような気がします。個々の実装について詳しくないですがそうしたアイデアの記事を見かけたことはあります（ずいぶん昔に見たものなので今日のポピュラーな実装でそのような実装が行われているかどうかについてはすみませんがわかりません）
|
2
例をよりわかりやすくする
answer
CHANGED
|
@@ -3,7 +3,7 @@
|
|
|
3
3
|
```lisp
|
|
4
4
|
(setq a '(a b c)) ;; a = (a b c)
|
|
5
5
|
(setq b (cdr a)) ;; b = (b c)
|
|
6
|
-
(setf (car b) '
|
|
6
|
+
(setf (car b) 'bb) ;; b = (bb c) かつ a = (a bb c)
|
|
7
7
|
```
|
|
8
8
|
|
|
9
9
|
lispでも何でもかんでも構造の共有を起こすわけではなく、他のリストと共通部分を持たないという仮定を置くべきケースと共通部分を持つという前提のものが両方出てきます。しかしながら少なくとも後者が充分効率的に実装できる必要があります。
|
1
誤記訂正
answer
CHANGED
|
@@ -1,5 +1,3 @@
|
|
|
1
|
-
Lispの前に列の実現について・・・
|
|
2
|
-
|
|
3
1
|
Arrayは順番付きの静的な列を効率よく実現できるデータ構造ですけど、要素の共有に適した構造ではありません。例えばJavascriptのArrayやPythonのListでLispのリストを実現したとしますと以下のことが簡単には実現できないと思います。
|
|
4
2
|
|
|
5
3
|
```lisp
|