SCALA: Какие структуры данных являются оптимальными, в каких ситуациях при использовании ".contains()" или ".exists()"?

Я хотел бы знать, в каких ситуациях структура данных оптимальна для использования проверок "содержит" или "существует".

Я спрашиваю, потому что я исхожу из фона 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

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

Примечание. Пожалуйста, дайте мне знать, если вы чувствуете, что этот вопрос слишком расплывчатый, поскольку я не уверен, что правильно его формулирую.

Ответ 1

Set и Map (с реализацией хэш-таблицы по умолчанию) на сегодняшний день являются самыми быстрыми в contains, поскольку они вычисляют значение хэша и сразу же переходят в нужное место. Например, если вы хотите найти произвольную строку из списка из тысячи, contains в наборе примерно в 100 раз быстрее, чем contains на List или Vector или Array.

С помощью exists вам действительно нужно заботиться о том, как быстро собирается собираться коллекция - вы все равно должны проходить все. Там List обычно является чемпионом (если вы не хотите перемещаться по массиву вручную), но только Set и т.д. Обычно являются особенно плохими (например, exists on List ~ 8 раз быстрее, чем на Set, когда каждый из них имеет 1000 элементов). Остальные находятся в пределах примерно 2,5x от List (обычно 1,5x, но Vector имеет базовую структуру дерева, которая не так быстро перемещается).

Ответ 2

Если вы хотите широко использовать contains, вы должны использовать Set (или a Map).

AFAIK нет никакой структуры данных, которая реализует эффективную (то есть быстрее, чем O (n)) exists, поскольку закрытие, которое вы проходите, может даже не быть связано с элементами внутри.