Есть ли способы ускорить работу Map.getOrElse (val, 0) на больших картах кортежей?

Question

У меня есть простой неизменный Map в Scala:

// ... - 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")

* 1010 Проблема в том, что этот метод вызывается несколько раз для разных строк ввода. Например, я предполагаю, что для длины карты 100 и 1 входной строки будет попытаться сравнить эту строку 100 раз (для 1 значения карты). Как вы предполагаете, для 10 000 будет получено 10 000 сравнений.

Таким образом, при огромной длине карты более 10.000 мой метод, который находит значение строковых ключей на этой карте, значительно замедляет работу.

Что вы можете посоветовать для ускорения этого кода?

Может быть, использовать другой тип карты?

Может быть, еще одна коллекция?

Answer 1

Например, как я полагаю, для длины карты 100 и 1 входной строки, она будет пытаться сравнить эту строку 100 раз (единицы для 1 значения карты). Как вы предполагаете, для 10 000 будет получено 10 000 сравнений.

Нет, не будет. Это скорее точка Map во-первых. Хотя он позволяет реализации, которые требуют проверки каждого значения по одному (например, ListMap), они используются очень редко, и по умолчанию при вызове Map(...) вы получите HashMap что нет. Его поиск - логарифмическое время c (с большой базой), поэтому при переходе от 100 к 10000 он удваивается, а не увеличивается в 100 раз. метод, который находит значение строковых ключей в этой карте, значительно замедляет работу.

10000 довольно мало.

Собственно, посмотрите на http://www.lihaoyi.com/post/BenchmarkingScalaCollections.html#performance. Вы также можете видеть, что изменяемые карты намного быстрее. Обратите внимание, что это предшествовало изменениям коллекции в Scala 2.13, поэтому, возможно, изменилось.

Answer 2

Map не не имеют линейный поиск по времени. По умолчанию конкретная реализация Map равна HashMap

Map - это интерфейс для неизменяемых карт, а scala.collection.immutable.HashMap - конкретная реализация.

с эффективным постоянным временем поиска в соответствии с характеристиками производительности коллекций c

                lookup  add  remove  min

HashSet/HashMap  eC     eC    eC     L