Какова сложность big-O для проверки равенства двух хешей? - PullRequest
Новая
       39

Какова сложность big-O для проверки равенства двух хешей?

0 голосов
/ 05 октября 2019

Я предполагаю, что ответ O (hash_equals) = n, но я прав?

Например, в Ruby мы имеем: 

$ irb
2.6.3 :001 > {a: 1, b: 2, c:3} == {b:2, a:1, c:3}
 => true

Реализация этого == здесь: https://github.com/ruby/ruby/blob/trunk/hash.c#L3567

РЕДАКТИРОВАТЬ: Для @Schwern (в комментарии ниже), давайте предположим, плоский хеш с простыми значениями. Меня особенно интересует Ruby, но меня также интересует более общий вопрос о большинстве реализаций языков / хэшей.

1 Ответ

1 голос
/ 05 октября 2019

Сравнения хеша в среднем O (ключи) + ostCost (значение).

Если значения простые, то сравнение каждого значения равно O (1). Сравнение хешей: O (ключи) + ∑O (1), что равно O (ключи).

Ruby делает несколько дополнительных вещей, но основной алгоритм прост.

  1. Если они имеют одинаковый хэш, они равны .
  2. Если у них разное количество ключей, они не равны .
  3. Если какая-либо пара в hash1 отсутствует в hash2, они не равны .
  4. Они равны . 
def hash_eq(hash1, hash2)
  # O(1)
  return true if hash1.equal?(hash2)

  # O(1)
  return false if hash1.size != hash2.size

  # O(keys)
  hash1.each {|k,v|
    #               O(1)     O(value)
    return false if hash2[k] != v
  }

  return true
end

Проверка равенства объектов - это просто сравнение двух указателей, поэтому O (1).

Хэши Ruby сохраняют свой размер в num_entries, поэтому при сравнении их размер равен O (1).

Итерируя по ключам и значениям хэша, вы получаете O (ключи), в основном вы проходите массив.

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

Наконец, сравнение значений имеет свою стоимость. Для простых значений, таких как числа, это O (1). Все остальное имеет свою цену, которую я назову O (val). Это могут быть большие строки, которые представляют собой O (n), где n - размер строки, или сложные вложенные структуры данных. Мы должны сделать это для каждого значения, и каждое значение несет свою стоимость. Я запишу это как сумму всех этих затрат: ostCost (значение).

Таким образом, O (1) + O (1) + O (ключи) + ostCost (значение). O (1) S затопляются O (ключи) и исчезают, таким образом, O (ключи) + (Cost (значение).

Простой тест подтверждает это. 

require 'benchmark'

def benchmark_hash_eq(&block)
  # We can't use h2 = h1.clone because that will not clone
  # the values. Then Ruby can cheat and use object equality to
  # compare the values.
  h1 = block.call
  h2 = block.call

  puts "Size: #{h1.size}"
  puts Benchmark.measure {
    10_000.times { h1 == h2 }
  }
end

puts "With number values"
benchmark_hash_eq do
  Hash[(1..100).collect { |i| [i, i] }]
end
benchmark_hash_eq do
  Hash[(1..1_000).collect { |i| [i, i] }]
end
benchmark_hash_eq do
  Hash[(1..10_000).collect { |i| [i, i] }]
end

puts "With large, equal size strings"
benchmark_hash_eq do
  Hash[(1..100).collect { |i| [i, "a" * 1000] }]
end
benchmark_hash_eq do
  Hash[(1..1_000).collect { |i| [i, "a" * 1000] }]
end
benchmark_hash_eq do
  Hash[(1..10_000).collect { |i| [i, "a" * 1000] }]
end

With number values
Size: 100
  0.019237   0.000043   0.019280 (  0.019306)
Size: 1000
  0.195047   0.000515   0.195562 (  0.196367)
Size: 10000
  1.913112   0.003115   1.916227 (  1.920030)

With large, equal size strings
Size: 100
  0.065414   0.000225   0.065639 (  0.065839)
Size: 1000
  0.669863   0.001145   0.671008 (  0.672279)
Size: 10000
 10.041987   0.013201  10.055188 ( 10.066840)

Совершенно линейный, за исключением последнего, что может быть связано с размером хеша, достигающим некоторого порога памяти.

Обратите внимание, что Ruby может выполнять сравнение параллельно. Это не меняет сложности, но может заставить работать быстрее.

...