はじめに
ElixirのListは[1, 2, 5, 4, 3]とデータがならんでいる配列のように記述しています。
また、[head | tail]と最初のデータをhead(1)と残りをtail([2, 5, 4, 3])となっています。
ここでは、どうしてこのように書く必要があるのか、データ構造を含め、説明したいと思います。
リストって何だろう
メモリ上、リストって以下のような構造になっています。
次のデータを指す情報(ポインタ)とデータと繋がっています。
[1, 2, 5, 4, 3]は
となり、便宜上、データが並んでいる配列のように書き、リストとしています。
縦一列に並んでいる人を真正面から見る
メモリの構造、ポインタといっても良くわからないので、例として、縦一列に並んでいる人を考えます。
真正面から見た時、先頭の顔しか見えず、その後ろの人が誰なのかわかりません。
そして、次の人が誰であるかは先頭の人が回れ右と後ろに向き直し、と次の人を見て初めてわかります。
次の人が誰かはその前の人しか、わからないんです。
[1, 2, 5, 4, 3]のリストは先頭(head)は何かはわかるが、後残り(tail)は何かわからず、並んでいる列(リスト)でしかありません。そして、先頭(head)を読んで、初めて次のデータが読むとの順番で繰り返しとなります。
[head | tail] = [1, 2, 5, 4, 3]ではhead: 1、tail: [2, 5, 4, 3] (リスト)と、先頭データと残りリストとなり、記号,でなく、記号|で繋ぎます。
この事から[1, 2, 5]は実際には[1 | [2 | [5 | []] ] ]となりますが、便宜上、[1, 2, 5]と書きます。
では、配列の場合はどうなんでしょう。配列は横一列に並んでいて、左から何番目(添字)の人が誰かわかると言ったものになります。
a[5] = [1, 2, 5, 4, 3]でa[0]:1、a[1]:2、a[2]:5、...となります。
配列にしないのはなぜ?
今、a[4] = [1, 2, 4, 3]と言う配列があるとします。ここで2と4の間に5を割り込んで入れる事とします。
5を途中に入れるため、厄介な事に4、3をずらす必要があります。a[3]:3 -> a[4]、a[2]:4 -> a[3]、5 -> a[2]
[1, 2, 5, 4, 3]となる。つまり、追加または削除したデータ以降の番号付けをすべて変える必要があります。
リストの場合は、[2] -> [4]の間に[2]の繋がる先を[5]に変え、[5]の繋がる先を[4]にする、繋ぎを変更するだけとなり、データの追加、削除が簡単になります。
もうひとつの利点は配列の場合、データのサイズによりどのように保存するかが問題となりますが、リストの場合、データはどこにあっても良く、サイズには影響はありません。データが新たな違うリストでも構わないんです。[1, 2, [5, 4], 3]
最後尾から見るなんて無茶な
[1, 2, 5, 4, 3]の3番目は何かを見ようとすると、先頭から順番に見ていくため、3回目で初めて、5なんだとわかります。
このリストを最後尾から順番に見ていこうとすると、先頭から順番に見て、5回目に3とわかり、次に再度先頭から順番に見て4回目に4とわかると言った毎回先頭からとなり、先頭を読むまで、5 + 4 + 3 + 2 + 1 = 15回も検索する必要があります。
従って、リスト(片方向リスト)では最後尾から読んでいく場合、一旦reverse()によりリストを並び替えるのが一般的です。
縦一列に並んでいる人全員が一旦後ろに向き直し、後ろが順番に見ていくと上記の場合、5回で済みます。
ついでに、Mapデータってハッシュテーブルなんだ
Listデータの他にMapデータがあります。
map = %{:foo => "bar", "hello" => :world}
ハッシュテーブルとはkeyデータを元にハッシュ計算により求めた指定位置にデータが保存しているものです。
これにより、データの数が何個あっても、keyにより、一回でデータを求める事ができます。
Mapデータはこのハッシュテーブルにより、keyとデータとの関連テーブルが作られています。
従って、データ数により、回数が変わるListとは違い、Mapの場合は一回となります。それと同時にデータの順番は全く意味がなくなります。
まとめ
- Listデータは片方向リストで
[先頭データ | 残りリスト]の構造になっていて、配列とは違うもの。 - 検索はデータ数で決まる。
- 先頭から処理するのが普通だが、最後尾からする場合は一旦reverse()により並び変えてからする。
- Mapデータはkeyによる一回で検索するデータで、データの順番は関係がない。
となります。