快速查找大型数组中的重复项

Question

我有一个35k元素的数组.我怎样才能有效地找到重复项并返回重复项？

all = [*1..35000, 1]

此解决方案有效:

all.select { |v| all.count(v) > 1 }

但这需要很长时间.

Answer 1

如果您使用的是Ruby 2.4.0+,则可以使用group_by+ Hash#transform_values(可用的Ruby 2.4.0):

all.group_by(&:itself).transform_values(&:size).select { |_, freq| freq > 1 }

看到它的实际效果:

all.group_by(&:itself) 分组元素出现的次数:

{
  1 => [1, 1],
  2 => [2],

  ...

  35000 => [35000]
}

然后让我们将上面哈希的值转换为频率:

all.group_by(&:itself).transform_values(&:size):

{
  1 => 2,
  2 => 1,

  ...

  35000 => 1
}

基准测试:

def measure_execution_time
  started = Time.now
  yield
  Time.now - started
end

measure_execution_time do
  all.select { |value| all.count(value) > 1 }
end
=> 7.235489


measure_execution_time do
  all.group_by(&:itself).transform_values(&:size).select { |_, freq| freq > 1 }
end
=> 0.017887

Answer 2

你的代码正在执行eon,因为它正在count为每个元素执行,导致它的计算复杂度为O(n ²).

arr = [*1..35000, 1, 34999]

如果你想知道数组中出现的值至少两次......

require 'set'

uniq_set = Set.new
arr.each_with_object(Set.new) { |x,dup_set| uniq_set.add?(x) || dup_set.add(x) }.to_a
  #=> [1, 34999]

设置查找(在封面下使用哈希实现)非常快.

请参阅Set#add？并设置#add.

如果你想知道值出现在数组中的次数至少出现两次......

arr.each_with_object(Hash.new(0)) { |x,h| h[x] += 1 }.select { |_,v| v > 1 }
  #=> {1=>2, 34999=>2}

这使用计数哈希.当默认值作为参数时,请参阅Hash :: new.

如果你想知道数组中出现的值的索引至少两次......

arr.each_with_index.
    with_object({}) { |(x,i),h| (h[x] ||= []) << i }.
    select { |_,v| v.size > 1 }
  #=> {1=>[0, 35000], 34999=>[34998, 35001]}

当哈希h还没有密钥x时

(h[x] ||= []) << i
   #=> (h[x] = h[x] || []) << i
   #=> (h[x] = nil || []) << i
   #=> (h[x] = []) << i
   #=> [] << i where [] is now h[x]