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