Оптимизация проблемы миграции птиц

Question

В настоящее время я работаю над задачей , где рекомендации следующие:

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

Например, предположим, что ваши наблюдения птиц имеют типы arr = [1, 1, 2, 2, 3]. Есть два типа 1 и 2, и один тип 3. Выберите нижний из двух типов, которые встречались дважды: тип 1.

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

Мой код выглядит следующим образом:

def migratoryBirds(arr)
    sorted = Hash[arr.map { |x| [x, arr.select { |y| y==x }.count] }]
    return sorted.max_by { |k,v| v }[0]
end

Answer 1

Ваш sorted га sh можно записать немного более кратко, как:

sorted = arr.map { |x| [x, arr.count(x)] }.to_h

Для массива примера [1, 1, 2, 2, 3] это эквивалентно:

[
  [1, arr.count(1)], # counts all 1's in arr
  [1, arr.count(1)], # counts all 1's in arr (again)
  [2, arr.count(2)], # counts all 2's in arr
  [2, arr.count(2)], # counts all 2's in arr (again)
  [3, arr.count(3)]  # counts all 3's in arr
].to_h

Мало того, что он учитывается 1 и 2 дважды. Он также должен пересекать весь массив снова для каждого count вызова (или select в вашем коде).

Лучший подход - обойти массив один раз и использовать га sh для подсчета вхождений:

arr = [1, 1, 2, 2, 3]

sorted = Hash.new(0)
arr.each { |x| sorted[x] += 1 }

sorted #=> {1=>2, 2=>2, 3=>1}

Это также можно записать в одну строку через each_with_object:

sorted = arr.each_with_object(Hash.new(0)) { |x, h| h[x] += 1 }
#=> {1=>2, 2=>2, 3=>1}

Ruby 2.7 даже есть специальный метод tally для подсчета случаев:

sorted = arr.tally
#=> {1=>2, 2=>2, 3=>1}