有什么方法可以加快 Map.getOrElse(val, 0) 在大元组映射上的工作吗？

Question

我在 Scala 中有简单的不可变 Map：

// ... - mean and so on
val myLibrary = Map("qwe" -> 1.2, "qasd" -> -0.59, ...)

为此 myMap 我调用 MyFind 方法调用 getOrElse(val, 0):

def MyFind (srcMap: Map[String,Int], str: String): Int ={
    srcMap.getOrElse(str,0)
}

val res = MyFind(myLibrary, "qwe")

问题在于此方法针对不同的输入字符串调用了多次。例如。正如我假设的那样，对于地图长度 100 和 1 个输入字符串，它将尝试比较该字符串 100 次（1 个地图值）。正如您猜测的那样，对于 10,000，它将获得 10,000 次比较。

由于地图长度超过 10.000，我在该地图中查找字符串键值的方法显着减慢了工作速度。

What you can advice to speedup that code?

Maybe use another type of Map?

Maybe another collection?

Answer 1

Map 不有线性时间查找。 Map的具体实现是HashMap

Map is the interface for immutable maps while scala.collection.immutable.HashMap is a concrete implementation.

根据 collections performance characteristic

，

具有有效的恒定查找时间

                lookup  add  remove  min

HashSet/HashMap  eC     eC    eC     L

Answer 2

E.g. as i suppose for map length 100 and 1 input string it will be try to compare that string 100 times (ones for 1 map value). As you guess for 10,000 it will be gain 10,000 comparisons.

不，不会。这首先是 Map 的重点。虽然它允许需要逐一检查每个值的实现（例如 ListMap) they are very rarely used and by default when calling Map(...) you'll get a HashMap 不需要。它的查找是对数时间（基数很大），所以基本上当从 100 到 10000 时它会加倍而不是增加100倍。

By that with huge map length over 10.000 my method which find value of string keys in that map significantly slows down the work.

10000 很小。

其实，看看http://www.lihaoyi.com/post/BenchmarkingScalaCollections.html#performance。您还可以看到可变映射要快得多。请注意，这早于 Scala 2.13 中的集合更改，因此可能已经更改。

有什么方法可以加快 Map.getOrElse(val, 0) 在大元组映射上的工作吗？

Is any ways to speedup work of Map.getOrElse(val, 0) on big tuple maps?

scala

find

seq