Какова временная сложность структуры векторных данных Scala?

Question

Я знаю, что большинство Vector методов по сути являются O (1) (постоянным временем) из-за дерева, которое они используют, но я не могу найти никакой информации о методе содержимого. Сначала я подумал, что для проверки всех элементов должен быть O (n), но я не уверен.

Answer 1

Отвечая на вопрос в названии, характеристики производительности ( версия 2.13 документа ) из базовых c операций head, tail, apply, update , prepend, append, insert перечислены как e C для Vector:

e C Операция фактически занимает постоянное время, но это может зависеть от некоторых допущений, таких как максимальная длина вектора или распределение га sh ключей.

Вы правы contains is O (N) , поскольку нет хеширования или чего-либо еще, что позволило бы избежать необходимости сравнивать все элементы. Тем не менее, если вы хотите быть уверены, лучше всего проверить реализацию.

Поскольку найти правильную реализацию в исходных текстах библиотеки может быть сложно из-за множества свойств и переопределений, используемых для реализации контейнеров, наилучшим способом чтобы проверить это отладчик. Используйте код, подобный следующему:

val v = Vector(0, 1, 2)
v.contains(1)

Используйте отладчик, чтобы перейти к v.contains, и источник, который вы увидите:

  def contains[A1 >: A](elem: A1): Boolean = exists (_ == elem)

Если вы все еще не уверены в этом, Еще один «шаг в» приведет вас к:

  def exists(p: A => Boolean): Boolean = {
    var res = false
    while (!res && hasNext) res = p(next())
    res
  }