优化鸟类迁徙挑战

Question

我目前正在编写一个挑战，指南如下：

你被要求帮助研究在大陆上迁徙的鸟类的数量。您感兴趣的每一种鸟都将被一个整数值所识别。每次发现一种特定的鸟，它的id号就会被添加到你的目击记录中。你会想要找出哪种鸟是最常见的，给出一张目击名单。您的任务是打印该鸟类的类型号，如果两个或多个类型的鸟类相同，则选择ID号最小的类型。 例如，假设您的鸟类目击事件属于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哈希可以写得更简洁一些，如下所示：

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 )，它还必须再次遍历整个数组。

一种更好的方法是遍历数组一次，并使用散列来计数出现的情况：

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}

Ruby2.7甚至有一个专门的方法tally来统计出现的情况：

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