6

スキーム R5RS 標準の6.3.6 ベクトルセクションでは、ベクトルについて次のように述べています。

ベクトルは、要素が整数でインデックス付けされた異種構造です。通常、ベクターは同じ長さのリストよりも少ないスペースを占有し、ランダムに選択された要素にアクセスするために必要な平均時間は、通常、リストよりもベクターの方が短くなります。

このベクトルの説明は少し曖昧です。

および操作とその複雑さに関して、これが実際に何を意味するのか知りたいです。どちらのプロシージャも、ベクトルとリストの k 番目の要素を返します。ベクトル演算は O(1) で、リスト演算は O(n) ですか? ベクトルはリストとどう違うのですか? これに関する詳細情報はどこにありますか?vector-reflist-ref

現在、簡単に検索できるようにキーと値のペアを格納するためのデータ構造として、連想リストを使用しています。キーが整数の場合は、ベクトルを使用して値を格納する方がよいでしょう。

4

2 に答える 2

4

との非常に具体的な詳細は実装vector-refにlist-ref依存します。つまり、各スキ​​ーム インタープリターは適切と思われる仕様を実装できるため、質問に対する回答を R5RS に準拠するすべてのインタープリターに一般化することはできません。実際のインタープリターに依存します。再利用。

vector-refしかし、はい、まともな実装では、操作がO(1)であり、list-ref操作がおそらくO(n)であると想定するのが安全な賭けです。なんで？ベクターは、実装言語にネイティブなデータ構造を使用して実装する必要があるため、インデックスを指定した要素 (たとえば、プリミティブ配列) への O(1) アクセスを許可するため、実装がvector-ref簡単になります。一方、Lisp のリストはconsセルをリンクすることによって作成され、特定のインデックスで要素を見つけるには、リスト内のその前のすべての要素をトラバースする必要があります。したがって、O(n) の複雑さです。

補足として - はい、キーが整数であり、インデックスを作成する要素の数が事前にわかっている限り、キーと値のペアの連想リストを使用するよりもベクトルを使用する方が高速な代替手段になります (Scheme ベクトルはその作成後のサイズ)。一般的なケース (整数以外のキー、可変サイズ) では、インタプリタがハッシュ テーブルをサポートしているかどうかを確認するか、ハッシュ テーブルを提供する外部ライブラリ ( SRFI 69など) を使用します。

于 2013-04-17T13:57:13.447 に答える
1

リストはconsセルから構成されます。R 5 RSリストセクションから：

リストの連続するペアの car フィールド内のオブジェクトは、リストの要素です。たとえば、2 要素リストは、car が最初の要素であり、cdr が 2 番目の要素である car と cdr が空のリストであるペアです。リストの長さは要素の数であり、ペアの数と同じです。

たとえば、リスト(a b c)は次の一連のペアと同等です。(a . (b . (c . ())))

そして、次の「ノード」によってメモリ内で表すことができます。

[p] --> [p] --> [p] --> null
 |       |       |
 |==> a  |==> b  |==> c

各ノードには、値へのポインター ( [])と、次の要素への別のポインター ( ) が含まれています。pcarcdr

これにより、リストを無制限の長さに拡張できますが、要求された要素を見つけるために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 は、連想リストの魅力的な代替手段になる可能性があります。

于 2013-04-17T13:56:57.247 に答える