判断数组中所有元素是否都为特定值的最快方法

Question

我需要一种非常快速的方法来确定一个数组是否仅包含值为9的整数。这是我当前的解决方案：

input = [9,9,9,9,9,9,9,9,9,9,9,9]
input.uniq == [9]

你能更快地完成吗？

- astropanic

---

为了恰当地回答这个问题，我们需要知道实际数组的大小和非9值出现的概率。对于不同类型的输入，更快的解决方案可能会更慢。 - Mark Thomas

那么，听起来你想要优化非9值的拒绝，就像@steenslag的解决方案一样。完整的数组扫描是昂贵的。 - Mark Thomas

@bashman：你真的期望2M个元素中有10%的概率任何一个元素都具有给定的值吗？ :) - Olivier L.

看起来人们忽略了我的答案，因为它没有得到任何投票，尽管它提供了最佳性能。在这里放置这个评论是为了邀请人们来看一下。 - Olivier L.

有趣的是，最快的jruby解决方案比1.9.2中的相同解决方案更快。 - Mark Thomas

Answer 1

require 'benchmark'

n = 50000
Benchmark.bm do |x|
  x.report "uniq  " do
    n.times do 
      input = [9,9,9,9,9,9,9,9,9,9,9,9]
      input.uniq == [9]
    end
  end
  x.report "delete" do
    n.times do 
      input = [9,9,9,9,9,9,9,9,9,9,9,9]
      input.delete 9
      input == []
    end  
  end
  x.report "count " do
    n.times do
      input = [9,9,9,9,9,9,9,9,9,9,9,9]
      input.count(9)==input.size
    end
  end
  x.report "select" do
    n.times do
      input = [9,9,9,9,9,9,9,9,9,9,9,9]
      input.select{|x| x != 9}.empty?
    end
  end  
  x.report "detect" do
    n.times do
      input = [9,9,9,9,9,9,9,9,9,9,9,9]
      input.detect { |i| i != 9 }.nil?
    end
  end 

  x.report "all?  " do
    n.times do
      input = [9,9,9,9,9,9,9,9,9,9,9,9]
      input.all?{|x| x == 9} 
    end
  end 

end

这是对以上答案以及我自己的一些基准测试结果。

        user       system      total        real
uniq    0.313000   0.000000   0.313000 (  0.312500)
delete  0.140000   0.000000   0.140000 (  0.140625)
count   0.079000   0.000000   0.079000 (  0.078125)
select  0.234000   0.000000   0.234000 (  0.234375)
detect  0.234000   0.000000   0.234000 (  0.234375)
all?    0.219000   0.000000   0.219000 (  0.218750)

如果 input = [1]+[9]*9：

        user     system      total        real
uniq    0.328000   0.000000   0.328000 (  0.328125)
delete  0.188000   0.000000   0.188000 (  0.203125)
count   0.187000   0.000000   0.187000 (  0.218750)
select  0.281000   0.016000   0.297000 (  0.296875)
detect  0.203000   0.000000   0.203000 (  0.203125)
all?    0.204000   0.000000   0.204000 (  0.203125)

如果 input = [9]*9 + [1]：

        user     system      total        real
uniq    0.313000   0.000000   0.313000 (  0.328125)
delete  0.187000   0.000000   0.187000 (  0.187500)
count   0.172000   0.000000   0.172000 (  0.187500)
select  0.297000   0.000000   0.297000 (  0.312500)
detect  0.313000   0.000000   0.313000 (  0.312500)
all?    0.281000   0.000000   0.281000 (  0.281250)

如果 input = [1,2,3,4,5,6,7,8,9]:

        user     system      total        real
uniq    0.407000   0.000000   0.407000 (  0.406250)
delete  0.125000   0.000000   0.125000 (  0.125000)
count   0.125000   0.000000   0.125000 (  0.125000)
select  0.218000   0.000000   0.218000 (  0.234375)
detect  0.110000   0.000000   0.110000 (  0.109375)
all?    0.109000   0.000000   0.109000 (  0.109375)

- Vasiliy Ermolovich

---

你能否也针对元素都不同的情况生成结果？在这种情况下，“all?”解决方案比“uniq”更快。 - Wayne Conrad

如果您能标记报告（例如 x.report "detect" do），并且还可以针对未通过测试的数组进行测试（例如 [1]+[9]*9 和 [9]*9+[1]），那么这将是一个非常好的答案。 - Phrogz

把这些结果平均一下是个好主意，这样人们就不需要查阅四张基准时间表了。除此之外，非常好！ - Aaa

Answer 2

你有几个选项：

>> input.count(9)==input.size
=> true

或者

>> input.select{|x| x != 9}.empty?
=> true

或者您之前提供的解决方案。

- yan

---

谢谢，第一个是目前最快的（:)），第二个非常慢。 - astropanic

当您将非常大的输入放入其中时，第一个解决方案会很慢。这里的其他解决方案会更快。 - Mark Thomas

Answer 3

这个循环遍历数组，当找到非九的元素时中断(返回false)。

[9,9,9,9,9,9,9,9,9,9,9,9].all?{|x| x == 9} # => true

- steenslag

---

当输入非常大且很可能包含非9值时，速度快。 - Mark Thomas

Answer 4

编辑：在此处查找完整的源代码here。感谢@nash提供的原始想法。

---

迭代并在找到一个不匹配的元素时立即返回false。

def all_matches(arr, match)
  arr.each do |element|
    return false if element != match
  end
  true
end

使用从0到9的2M个随机整数，50次循环（n=50）：

        用户       系统       总计       实际
去重    5.230000   0.010000   5.240000 (  5.219444)
计数    2.680000   0.010000   2.690000 (  2.677923)
选择  7.580000   0.060000   7.640000 (  7.634620)
检测  0.000000   0.000000   0.000000 (  0.000068)
全部?  0.000000   0.000000   0.000000 (  0.000046)
我的  0.000000   0.000000   0.000000 (  0.000032)
删除  5.090000   0.020000   5.110000 (  5.101290)
任意?  0.000000   0.000000   0.000000 (  0.000041)

用于生成数组的代码：

input = []
2000000.times { input << (rand*10).to_i }

---

2M 9（所有9）50次迭代结果如下：

        用户       系统      总计         实际
去重    4.900000   0.000000   4.900000 (  4.890030)
计数    0.350000   0.000000   0.350000 (  0.351340)
选择   5.400000   0.010000   5.410000 (  5.393489)
检测   6.720000   0.000000   6.720000 (  6.685539)
是否全为9  6.070000   0.000000   6.070000 (  6.061914)
查找我的  5.510000   0.010000   5.520000 (  5.500186)
删除   1.080000   0.010000   1.090000 (  1.084125)
是否存在  6.200000   0.000000   6.200000 (  6.197529)

- Olivier L.

---

请注意，“mine”基准测试结果是我的算法的结果。 - Olivier L.

还要注意，如果您将 return false if arr.empty? 添加到我的方法中（这可能是必需的），它仍然比不执行此操作的 all? 方法表现更好。 - Olivier L.

我不明白为什么最近一次基准测试的计数速度这么快。 - steenslag

@steenslag：一定与分支预测有关。 - Olivier L.

Answer 5

我猜你的意思是input.uniq == [9]，因为实际上这个代码对我来说返回的是false。你所说的更快是什么意思？这段代码需要非常快地运行吗？我想detect更快，因为它会返回第一个符合测试条件的元素：

input = [9,9,9,9,9,9,9,9,9,9,9,9]
input.detect { |i| i != 9 }.nil?

- muffinista

---

http://pastie.org/1961526，你的代码与我的代码，感谢关于大括号的信息，我已经更正了上面的例子。 - astropanic

你的想象力无法与实际基准相比。 :) - Phrogz

Answer 6

也许是最慢的，但这就是我想到的。

input = [9,9,9,9,9,9,9,9,9,9,9,9]
!(input.any { |a| a != 9 })

- rubyprince

---

又是另一种方法！ :) 请查看我的答案以获取比较基准（我刚刚添加了您的方法，标记为“any?”）。 - Olivier L.

Answer 7

这个很好用：

> array = ['apple', 'banana']
> includes = array.uniq.include? 'banana'
> => true

此外，通过扩展，我们可以检查所有值是否相同，而不知道它们是什么：

> array = ['apple', 'banana', 'apple']
> all_same_values = (array.uniq.length > 1) ? false : true
> => false

这里有一个相关的答案：https://dev59.com/OnI-5IYBdhLWcg3wKVE9#1986398

- Tom

Answer 8

这里有另一种更快的方法（上面的计数方法仍然是最快的）：

arr = [9,9,9,9,9,9,9,9,9,9,9,9]
arr.reject { |i| i==9 }.count == 0

还有一个速度稍慢的：

arr.inject(:&) == 9

这是关于“水果”宝石的比较：

require 'fruity'
compare do
  count { arr.count(9) == arr.size }
  uniq { arr.uniq == [9] }  
  bitwise_and { arr.inject(:&) == 9 }  
  reject { arr.reject { |i| i==9 }.count == 0 }
end  


Running each test 8192 times. Test will take about 3 seconds.
count is faster than reject by 39.99999999999999% ± 10.0%
reject is faster than uniq by 10x ± 1.0
uniq is faster than bit_and by 30.000000000000004% ± 1.0%

- Abdo