Scalaでキーを効率的に検索する方法は、順序付けられたマップで知ることができますか？

Question

Scalaでキーを効率的に検索する方法を知っていますか？ は、私が地図を持って想像：

val unorderdMap: Map[Int, String] = ... 
val orederedMap: Map[Int, String] = unorderedMap.sort 

はorderedMapで高速化キーのルックアップ操作ですか？

unorderedMap.get(i) //Slower??? 
orderedMap.get(i) //Faster??? 

効率的に検索する方法をコンパイラが知っていますか？

コンパイラは、それぞれの場合で異なる検索操作を実行しますか？

* EDIT： 私は が、それは次のようにそれから地図を作るために、より良いです（これは私は興味を持って何が）キーで高速検索操作を持ちたい

case class A(key: Int, value1: String, value2: String, ...) 
val SeqA: Seq[A] = Seq(A(1, "One", "Uno", ...), A(2, "Two", "Duo",...), ..., A(20000,... ,...)) 

あります

を

val mapA = SeqA.map(a => a.key -> a)(collection.breakOut) 

または、それをシーケンスとして残しておく方がいいですか？ それから私はそれを注文する必要がありますマップを作るかどうか？ *エレメントは約 です。20K〜30Kエレメント！

Answer 1

ソートマップは通常、どの言語のハッシュマップよりも（*）遅くなります。これは、ソートされたマップがO（1）の複雑さを償却するハッシュマップと比較して、複雑さがO（log n）であるためです。

詳細な説明については、関連するwikiページをご覧ください。

（*）マップのサイズなど、多くの要因によって異なります。小さなセットの場合、バイナリ検索でソートされた配列は、キャッシュに収まる方が良いでしょう。