26

数字のリストが必要だとすると、2つの定義があります。

(def vector1 [1 2 3])
(def list2 '(1 2 3))

では、主な違いは何ですか？

4

4 に答える 4

35

はベクトル[1 2 3]ですが、はリストです。これら2つのデータ構造には異なるパフォーマンス特性があります。'(1 2 3)

ベクトルは、その要素への迅速なインデックス付きランダムアクセスを提供し、時間内にインデックスで(v 34)ベクトルの要素を返します。一方、ベクトルを変更する方が一般的にコストがかかります。v34O(1)

リストは（実装に応じて）先頭または末尾、あるいはその両方で簡単に変更できますが、要素への線形アクセスを提供します(nth (list 1 2 3 4 5) 3)。リストを順次スキャンする必要があります。

パフォーマンスのトレードオフの詳細については、「ベクトルとリストのパフォーマンス」などをグーグルで検索できます。

[ファローアップ]

では、もう少し詳しく見ていきましょう。まず第一に、ベクターとリストはClojureに固有ではない概念です。マップ、キューなどとともに、それらは抽象型のデータコレクションです。データを操作するアルゴリズムは、これらの抽象化の観点から定義されています。ベクトルとリストは、上記で簡単に説明した動作によって定義されます（つまり、サイズがある場合はベクトルであり、定数時間でその要素にアクセスしてインデックスを作成できます）。

Clojureは、他の言語と同様に、このように呼ばれるデータ構造を提供するときに、これらの期待に応えたいと考えています。inの基本的な実装を見ると、 nthvectorO（log 32 N）arrayForの複雑さを持つメソッドの呼び出しとO（1）であるJava配列のルックアップがわかります。

(v 34)なぜそれが実際にはO（1）であると言えるのでしょうか？Javaのログ32の最大値intは約7であるためです。これは、ベクトルへのランダムアクセスが事実上一定時間であることを意味します。

要約すると、vectorsとの主な違いはパフォーマンス特性です。さらに、Jeremy Heilerが指摘しているように、Clojureでは、動作に論理的な違いがあります。つまり、でコレクションを増やすことに関してです。listsconj

于 2012-07-16T13:18:32.563 に答える
9

リストとベクターには2つの主な違いがあります。

  1. リストは論理的に先頭で成長し、ベクトルは論理的に末尾で成長します。関数を使用すると、これが実際に動作していることがわかりconjます。与えられたコレクションの種類に応じてコレクションを増やしていきます。どちらの側でもコレクションを増やすことができますが、この方法で行うことはパフォーマンスが高くなります。

  2. リスト内のn番目のアイテムを取得するには、リストを先頭からトラバースする必要があります。一方、ベクトルはトラバースされず、O（1）のn番目のアイテムを返します。（実際にはO（log32n）ですが、これはコレクションが永続コレクションとして実装されているためです。）

于 2012-07-16T15:04:44.980 に答える
4

ベクトル評価時間はO（1）ではなくlog32Nです

ベクトル（IPersistentVector）ベクトルは、連続する整数でインデックス付けされた値のコレクションです。ベクトルは、log32Nホップのインデックスによるアイテムへのアクセスをサポートします。カウントはO（1）です。conjは、アイテムをベクトルの最後に配置します。ベクターは、アイテムを逆の順序で返すrseqもサポートしています。ベクトルは、1つの引数のinvoke（）に対してIFnを実装します。これは、インデックスであると想定し、n番目までに検索します。つまり、ベクトルはインデックスの関数です。

于 2012-07-16T14:28:04.507 に答える
4

  • ベクターは、メモリの隣接する領域にすべてのデータアイテムを保持するため、ベクター全体の転送が容易になり、リストと比較した場合、アイテムの挿入または削除にコストがかかります。

  • リストはアイテムを保持することはメモリの互いに素な領域であり、リスト全体の転送は高価になりますが、個々のアイテムの挿入と削除は比較的安価になります。

  • クラシックベクトルもサイズが固定されており、N個のアイテムに制限されていますが、リストは動的に拡大および縮小できます。

  • ベクトルは、要素アイテムへのインデックス付きアクセスも提供します。リストはそうではありません。古典的なベクトルの前身は配列です。
  • ベクトルの最近の実装は、多くの場合、同様の特性を提供することを目的としていますが、基礎となるデータ構造は実際にはリストまたはハッシュである可能性があり、これらのベクトルは通常、動的なサイズ変更をサポートします。
于 2014-02-04T12:51:10.390 に答える