Проблема производительности счетчика Ruby Enumerable # в алгоритме

Question

Я решил эту проблему из LeetCode , используя Ruby, но у меня возникли некоторые проблемы с производительностью, которые я не понимаю.

Вот мой код:

def word_subsets(a, b)
    occurrence_map = max_occurrences(b)
    a.select do |w|
        word_occurrence = letter_occurrence(w)
        occurrence_map.all? { |k, v| v <= word_occurrence[k]  }
    end
end

def letter_occurrence(word)
    Hash.new(0).tap do |occurrences|
        word.each_char { |c| occurrences[c] += 1 }
    end
end

def max_occurrences(b)
    Hash.new(0).tap do |occurrences|
        b.each do |word|
            word_occurrences = letter_occurrence(word)
            word.each_char { |c| occurrences[c] = [occurrences[c], word_occurrences[c]].max }
        end
    end
end

Этот код работает, но у него не самое лучшее время выполнения, и я пытаюсь понять, почему.Читая еще одно решение Ruby, я понял, что самое запутанное: если я внесу это изменение в метод max_occurferences:

def max_occurrences(b)
    Hash.new(0).tap do |occurrences|
        b.each do |word|
            word.each_char { |c| occurrences[c] = [occurrences[c], word.count(c)].max }
        end
    end
end

Это приведет к значительному повышению производительности, и я действительно не понимаю, почему.Я не понимаю почему, потому что оригинальный способ, которым я это написал, не вызывает метод count для каждого символа.Я думал, что вызов этого метода будет повторять массив, поэтому вместо этого я вычисляю все вхождения только один раз.Но мой подход кажется хуже, и я не знаю, почему.

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

Answer 1

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

Ruby's String#count (который используется в другой версии) реализовано в C .Это и тот факт, что он не создает временный хеш, может объяснить разницу в производительности.

Answer 2

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

a = ["dangled", "glad", "gladden", "dogged"] 
b = ["gad", "lag", "dad"]

ba = b.map { |w| w.each_char.with_object(Hash.new(0)) { |c,h| h[c] += 1 } }
  #=> [{"g"=>1, "a"=>1, "d"=>1}, {"l"=>1, "a"=>1, "g"=>1}, {"d"=>2, "a"=>1}]
a.select do |w|
  ah = w.each_char.with_object(Hash.new(0)) { |c,h| h[c] += 1 }
  ba.all? { |wh| wh.all? { |c,cnt| ah.fetch(c,0) >= cnt } }
end
  #=> ["dangled", "gladden"]

Когда w = "dogged" в a.select do |w|..., мыполучить следующее для ah:

ah = w.each_char.with_object(Hash.new(0)) { |c,h| h[c] += 1 }
  #=> {"d"=>2, "o"=>1, "g"=>2, "e"=>1}

Когда wh = {"g"=>1, "a"=>1, "d"=>1},

wh.all? { |c,cnt| ah.fetch(c,0) >= cnt }

впервые выполнит

c = "g"
cnt = 1 
ah.fetch("g", 0) >= 1 #=> 2 >= 1 => true

Поскольку "g" проходит тест, мыследующий расчет

c = "a"
cnt = 1 
ah.fetch("a", 0) >= 1 #=> 0 >= 1 => false

ah.fetch("a", 0) возвращает 0, поскольку ah не имеет ключа "a".

Поскольку h.fetch("a", 0) >= 1 возвращает false, wh.all? { ... } возвращаетfalse, поэтому w = "dogged" не выбран.

Производительность может быть улучшена путем переупорядочения хэшей в ba (скажем, путем уменьшения длины слова) и / или переупорядочения пары ключ / значение в каждом элементеba (уменьшением значений или увеличением частоты в текстах на английском языке ['z' first, 'e' last], скажем).