リストはcons
セルから構成されます。R 5 RSリストセクションから:
リストの連続するペアの car フィールド内のオブジェクトは、リストの要素です。たとえば、2 要素リストは、car が最初の要素であり、cdr が 2 番目の要素である car と cdr が空のリストであるペアです。リストの長さは要素の数であり、ペアの数と同じです。
たとえば、リスト(a b c)
は次の一連のペアと同等です。(a . (b . (c . ())))
そして、次の「ノード」によってメモリ内で表すことができます。
[p] --> [p] --> [p] --> null
| | |
|==> a |==> b |==> c
各ノードには、値へのポインター ( []
)と、次の要素への別のポインター ( ) が含まれています。p
car
cdr
これにより、リストを無制限の長さに拡張できますが、要求された要素を見つけるためにref
、リストの先頭から要素をトラバースする操作が必要になります。k
あなたが言ったように、これはO(n)です。
対照的に、ベクトルは基本的に、ポインターの配列として内部的に表現できる値の配列です。たとえば、ベクトルは次の#(a b c)
ように表されます。
[p p p]
| | |
| | |==> c
| |
| |==> b
|
|==> a
配列[]
には一連の 3 つのポインターが含まれ、各ポインターはベクトル内の値に割り当てられます。v
したがって、内部的には、表記法を使用してベクトルの 3 番目の要素を参照できますv[3]
。前の要素をトラバースする必要がないためvector-ref
、O(1) 操作です。
主な欠点は、ベクトルが固定サイズであるため、ベクトルが保持できるよりも多くの要素を追加する必要がある場合は、新しいベクトルを割り当て、古い要素をこの新しいベクトルにコピーする必要があることです。アプリケーションが定期的にこれを行う場合、これはコストのかかる操作になる可能性があります。
オンラインには多くのリソースがあります。Scheme Data Structuresに関するこの記事では、より詳細に説明し、いくつかの例を示していますが、リストに重点を置いています。
とは言っても、キーが整数である (または整数になる可能性がある) 場合で、固定数の要素を持っているか、適切な量のベクトル再割り当てで管理できる場合 (たとえば、起動時にベクトルをロードし、ほとんどの読み取りを実行する場合) vector は、連想リストの魅力的な代替手段になる可能性があります。