Какова временная сложность сопоставления с образцом в scala? - PullRequest
Новая
       12

Какова временная сложность сопоставления с образцом в scala?

1 голос
/ 06 июня 2019

Зависит ли сложность времени от того, что сопоставляется, или оно компилируется в какую-то форму таблицы поиска, которая может выполнять O (1) поиск?

Ответы [ 2 ]

3 голосов
/ 06 июня 2019

Некоторые Scala * match операторы могут быть скомпилированы в тот же байт-код, что и Java * switch операторов . Для этого существует аннотация .
Но в большинстве случаев, особенно сложных, таких как деконструкции, он будет скомпилирован в тот же байт-код, что и серия if / else операторов .

В общем, я не ожидал бы, что они будут "постоянной" операцией, а скорее "линейной" операцией. В любом случае, поскольку максимальное количество проверок не будет меняться для ввода, и обычно оно будет не более десяти из них. Формально можно сказать, что он имеет O (1) сложность.
См. Ответ yǝsʞǝlA для более подробного объяснения этого.

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

1 голос
/ 06 июня 2019

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

Поскольку сопоставление с образцом достигается путем вызова метода unapply для сопоставленного объекта docs и, при необходимости, сравнения извлеченных значений, временная сложность будет зависеть от реализации метода unapply s и может быть любой сложности. Оптимизация компилятора в общем случае невозможна, поскольку некоторые совпадения с образцами зависят от данных, передаваемых им.

Сравните эти сценарии: 

List(1, 2, 3) match {
  case  _ :+ last => ... // O(n) with respect to list length
  case head :: tail => ... // O(1) w.r.t. list length
  case _ => ... // O(1) - default case, no operation needs to be done
}

В большинстве случаев мы сопоставляем шаблон с чем-то вроде списка, чтобы разделить голову и хвост с помощью :: - O(1), потому что unapply просто возвращает head, если он существует.

Обычно мы не используем :+, потому что это не распространено и дорого (код библиотеки): 

/** An extractor used to init/last deconstruct sequences. */
object :+ {
  /** Splits a sequence into init :+ last.
   * @return Some((init, last)) if sequence is non-empty. None otherwise.
   */
  def unapply[T,Coll <: SeqLike[T, Coll]](
      t: Coll with SeqLike[T, Coll]): Option[(Coll, T)] =
    if(t.isEmpty) None
    else Some(t.init -> t.last)
}

Чтобы получить последний элемент последовательности (t.last), нам нужно выполнить цикл, то есть O(n).

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

Дополнительно:

В худшем случае здесь будет m шаблонов, каждый из которых выполняет в среднем c операций, чтобы выполнить сопоставление (предполагается, что unapply имеет постоянное время, но есть исключения). Кроме того, будет объект с n свойствами, которые мы должны сопоставить с этими шаблонами, что дает нам в общей сложности: m * c * n операций. Однако, поскольку m действительно мал (шаблоны никогда не растут динамически и обычно пишутся человеком), мы можем смело назвать его постоянной b, что дает нам: T(n) = b * c * n. С точки зрения биг-о: T(n) = O(n). Таким образом, мы установили теоретическую границу O(n), то есть для случаев, когда нам нужно проверить все n свойства объекта. Как я указывал выше, в большинстве случаев нам не нужно проверять все свойства / элементы, например, когда мы используем head :: tail, где n заменяется константой, и мы получаем O(1). Только если мы всегда будем делать что-то вроде head :+ tail, мы получим O(n). Я считаю, что амортизированная стоимость по-прежнему составляет O(1) для всех случаев в вашей программе.

...