Как определить большую O O сложность разности массивов в Ruby

Question

Как определить большую сложность O Разницы во множестве в Ruby?

Например:

array_1 = [1,2,3]
array_2 = [5,4,3,2,1]

array_2 - array_1 #gives [5,4]

Как работает array_2 - array_1 и какова сложность времени?

Answer 1

Мой вопрос: как array_2 - array_1 работает

Спецификация Ruby не предписывает какой-либо конкретный способ реализации Array#-. Это только предписывает результат. Поэтому любой разработчик Ruby может свободно реализовать Array#- так, как он хочет, и он может изменить свою реализацию в любое время и по любой причине.

и какова его временная сложность?

Спецификация Ruby не предписывает никакой конкретной временной сложности для Array#-. Это только предписывает результат. Таким образом, любой разработчик Ruby может свободно реализовывать Array#- с любой временной сложностью, какой пожелает, и он может изменять сложность времени в любое время и по любой причине.

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

Показательный пример: Рубиниус первоначально использовал реализацию Hash, которая очень похожа на ту, которую использует YARV, но с тех пор они переключились на реализацию, основанную на Hash-Array Mapped Tries. Таким образом, в зависимости от используемой вами версии Rubinius, Hash es могут быть реализованы с использованием совершенно разных алгоритмов. Фактически, в течение переходного периода Рубиниус предоставил как старую, так и новую реализацию, и вы могли переключаться между ними с помощью параметра командной строки.

В качестве примера, - это текущая реализация Array#- в Рубиниусе :

def -(other)
  other = Rubinius::Type.coerce_to other, Array, :to_ary

  array = []
  im = Rubinius::IdentityMap.from other

  each { |x| array << x unless im.include? x }

  array
end

Как видите, сложность шага a - b равна & Theta; (| a | + | b |) для этой конкретной версии Rubinius. Но позвольте мне повторить: это верно только для этой конкретной версии Рубиния. Другие версии Rubinius или другие реализации Ruby могут (и почти наверняка do ) иметь другие реализации.

Правильно ли я считаю вас программистом на C ++? Спецификация библиотеки C ++ довольно специфична тем, что на самом деле действительно предписывает сложность алгоритмов, а разработчики должны реализовывать алгоритмы, которые удовлетворяют этим сложностям. Это не относится к Ruby, а на самом деле к большинству других языков.

Answer 2

Наивный способ написать метод Array#- заключается в следующем.

class Array
  def -(other)
    each_with_object([]) { |e,a| a << e unless other.include?(e) }
  end
end

array_1 = [1, 2, 3]
array_2 = [5,4,3,2,1,4]

array_2 - array_1
  #=> [5, 4, 4] 

Метод повторяется по каждому элементу в array2 и для каждого из этих элементов он повторяется по некоторым или всем элементам array_1. Поэтому вычислительная сложность равна O(array_1.size * array_2.size).

Для больших массивов мы можем ускорить это, заменив other.include?(e) на other_set.include?(e), где other_set - набор уникальных значений в other. Наборы реализованы с помощью хэшей под крышками, поэтому поиск наборов, например, поиск ключей хеша, очень быстрый, обычно считается, что он имеет вычислительную сложность O(1) (постоянное время). Поэтому мы могли бы переписать этот метод следующим образом.

require 'set'

class Array
  def -(other)
    other_set = other.to_set
    each_with_object([]) { |e,a| a << e unless other.include?(e) }
  end
end

array_2 - array_1
  #=> [5, 4, 4] 

Этот метод имеет вычислительную сложность O(array_1.size + array_2.size), где array_2.size - вычислительная сложность операции other_set = array_2.to_set.

Я не могу сказать, что именно так Ruby реализует Array#-, но я уверен, что это более или менее так, как я это сделал, поскольку любой метод, имеющий меньшую вычислительную сложность, не сможет проверить все элементы в array_1 или array_2, что, очевидно, должно быть сделано для получения результата.

Обратите внимание, что other.include?(e) использует Array # include? , тогда как other_set.include?(e) использует Set # include? .