20

「含む」または「存在する」チェックを使用するのに最適なデータ構造がどのような状況であるかを知りたいです。

私は Python のバックグラウンドを持っており、すべてに式を使用することに慣れているため、質問if x in something:します。たとえば、どの式が最も速く評価されるか:

val m = Map(1 -> 1, 2 -> 2, 3 -> 3, 4 -> 4)
                                          //> m  : scala.collection.immutable.Map[Int,Int] = Map(1 -> 1, 2 -> 2, 3 -> 3, 4
                                          //|  -> 4)
val l = List(1,2,3,4)                     //> l  : List[Int] = List(1, 2, 3, 4)
val v = Vector(1,2,3,4)                   //> v  : scala.collection.immutable.Vector[Int] = Vector(1, 2, 3, 4)

m.exists(_._1 == 3)                       //> res0: Boolean = true
m.contains(3)                             //> res1: Boolean = true
l.exists(_ == 3)                          //> res2: Boolean = true
l.contains(3)                             //> res3: Boolean = true
v.exists(_ == 3)                          //> res4: Boolean = true
v.contains(3)                             //> res5: Boolean = true

直観的には、ランダム チェックではベクトルが最も速く、チェックされた値がリストの先頭にあり、多くのデータがあることがわかっている場合はリストが最も速いと思います。ただし、確認または修正は大歓迎です。また、他のデータ構造に自由に拡張してください。

注: この質問が漠然としすぎていると思われる場合は、私に知らせてください。正しい言い回しをしているかわからないからです。

4

2 に答える 2

20

SetおよびMap(デフォルトのハッシュ テーブルの実装では)containsハッシュ値を計算し、すぐに正しい場所にジャンプするため、はるかに高速です。たとえば、1000 個のリストから任意の文字列を見つけたい場合、 on セットはonまたはまたはcontainsよりも約 100 倍高速です。containsListVectorArray

ではexists、コレクションがどれだけ速くトラバースするかだけが重要です。とにかく、すべてをトラバースする必要があります。List通常はチャンプ (配列を手動でトラバースしたい場合を除きます) がありますが、通常特に悪いのは on だけですSet(たとえば、それぞれに 1000 要素がある場合、 existsonListは a よりも ~8 倍高速です)。Set他のものは約 2.5 倍以内ですList(通常は 1.5 倍ですVectorが、基本的なツリー構造があり、トラバースがそれほど高速ではありません)。

于 2013-05-08T16:39:30.387 に答える
1

contains広範囲に使用したい場合は、 Set(またはMap) を使用する必要があります。

私の知る限り、効率的な (つまり、O(n) よりも高速な) を実装するデータ構造はありません。これは、exists渡すクロージャーが内部の要素に関連していない可能性があるためです。

于 2013-05-08T15:35:20.850 に答える