arrays - 制作 uniq 数组最快的方法是什么？

Question

我有以下情况。我有一大堆随机字符串。应尽快使该数组唯一。

现在通过一些基准测试，我发现 ruby​​ 的 uniq 非常慢:

require 'digest'
require 'benchmark'

#make a nice random array of strings
list = (1..100000).to_a.map(&:to_s).map {|e| Digest::SHA256.hexdigest(e)}
list += list
list.shuffle

def hash_uniq(a)
  a_hash = {}
  a.each do |v|
    a_hash[v] = nil
  end
  a_hash.keys
end

Benchmark.bm do |x|
  x.report(:uniq) { 100.times { list.uniq} }
  x.report(:hash_uniq) { 100.times { hash_uniq(list) } }
end

要点 -> https://gist.github.com/stillhart/20aa9a1b2eeb0cff4cf5

结果很有趣。难道是ruby的uniq太慢了？

          user     system      total        real
uniq      23.750000   0.040000  23.790000 ( 23.823770)
hash_uniq 18.560000   0.020000  18.580000 ( 18.591803)

现在我的问题:

1. 有没有更快的方法使数组唯一？

2. 我做错了什么吗？

3. Array.uniq方法有问题吗？

我正在使用 ruby​​ 2.2.3p173(2015-08-18 修订版 51636)[x86_64-linux]

Answer 1

大数据集上的字符串解析操作当然不是Ruby的亮点。如果这是业务关键，您可能想用 C 或 Go 之类的语言编写扩展，或者让另一个应用程序处理它，然后再将其传递给您的 Ruby 应用程序。

就是说。您的基准测试似乎有些奇怪。使用 Ruby 2.2.3 在我的 MacBook Pro 上运行同样的程序会呈现以下结果:

          user        system    total     real
uniq      10.300000   0.110000  10.410000 ( 10.412513)
hash_uniq 11.660000   0.210000  11.870000 ( 11.901917)

建议 uniq 稍微快一些。

如果可能，您应该始终尝试使用正确的集合类型。如果您的收藏真正独一无二，请使用 Set 。它们具有更好的内存配置文件和更快的 Hash 查找速度，同时保留了一些 Array 直觉。

但是，如果您的数据已经在 Array 中，这可能不是一个好的权衡，因为插入到 Set 中也相当慢，如您所见这里:

              user        system    total     real
uniq          11.040000   0.060000  11.100000 ( 11.102644)
hash_uniq     12.070000   0.230000  12.300000 ( 12.319356)
set_insertion 12.090000   0.200000  12.290000 ( 12.294562)

我在其中添加了以下基准:

x.report(:set_insertion) { 100.times { Set.new(list) } }