有什么方法可以加快在大元组地图上工作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，我的方法在该地图中查找字符串键的值大大降低了工作速度。

您可以建议如何加快该代码的速度？

也许使用其他类型的地图？

也许还有其他收藏？

Answer 1

Map是否not具有线性时间查找。 Default的具体实现是Map

HashMap是不可变地图的接口而Map是具体的实现。

具有有效的常量查找时间，根据scala.collection.immutable.HashMap

collections performance characteristic

Answer 2

例如正如我想的那样，对于地图长度100和1个输入字符串，将尝试比较该字符串100次（1个地图值一次）。如您所猜测的10,000，将获得10,000的比较结果。

不，不会。那才是

                lookup  add  remove  min

HashSet/HashMap  eC     eC    eC     L

的重点。尽管它允许确实需要逐个检查每个值的实现（例如Map），但它们很少使用，并且默认情况下，在调用ListMap时会得到一个不需要的ListMap。它的查找是对数时间（基数较大），因此从10​​0到10000时，它基本上翻倍而不是增加100倍。

通过巨大的地图长度超过10.000，我的方法在该地图中查找字符串键的值大大降低了工作速度。

10000很小。

实际上，请看Map(...)。您还可以看到可变地图更快。请注意，此设置早于Scala 2.13中的集合更改，因此可能已更改。