arrays - 如何快速将两个最大的数组元素相乘

Question

我正在做一个挑战，它要求一种方法将数组的两个最大元素相乘，并找到一个不到一秒的解决方案。

这是我目前在 ~1.6 秒时的结果

def max_product(a)
  a.sort[-1] * a.sort[-2]
end 

如何重写它以加快速度？

Answer 1

a = [3,4,2,5,2,6]

def max_product(a)
  a.max(2).reduce(:*)
end

max_product(a)
  #=> 30

Enumerable#max在 Ruby v.2.2 中允许有参数。 min、max_by 和 min_by 相同。

请注意，Enumerable#max 将受益于即将推出的 Ruby v2.4 中的性能改进。

让我们将其与仅排序和取最后两个值以及按照@ZbyszekKr 建议的自己滚动进行比较。

def max_product_sort(a)
  a.sort.last(2).inject(:*)
end

def max_product_sort!(a)
  a.sort!
  a[-2] * a[-1]
end

def max_product_rolled(arr)
  m1 = arr.max
  max_loc = arr.index(m1)
  arr[max_loc] = arr[0,2].min - 1
  m2 = arr.max
  arr[max_loc] = m1 # to avoid mutating arr
  m1 * m2
end

首先让我们使用 fruity gem 进行比较。

require 'fruity'

arr = 1_000_000.times.map { rand 2_000_000 }
arr1 = arr.dup
arr2 = arr.dup
arr3 = arr.dup
arr4 = arr.dup

compare(
  max_2:  -> { max_product(arr1) },
  rolled: -> { max_product_rolled(arr2) },
  sort:   -> { max_product_sort(arr3) },
  sort!:  -> { max_product_sort!(arr4) }
)
Running each test once. Test will take about 8 seconds.
sort! is faster than max_2 by 4x ± 0.1
max_2 is faster than rolled by 2x ± 0.1
rolled is faster than sort by 2.1x ± 0.1

接下来使用 benchmark 进行比较。

arr = 1_000_000.times.map { rand 2_000_000 }
arr1 = arr.dup
arr2 = arr.dup
arr3 = arr.dup
arr4 = arr.dup

require 'benchmark'

Benchmark.bm do |x|
  x.report("max_2")  { max_product(arr1) }
  x.report("rolled") { max_product_rolled(arr2) }
  x.report("sort")   { max_product_sort(arr3) }
  x.report("sort!")  { max_product_sort!(arr4) }
end

          user      system     total       real
max_2   0.060000   0.010000   0.070000 (  0.066777)
rolled  0.110000   0.000000   0.110000 (  0.111191)
sort    0.210000   0.000000   0.210000 (  0.218155)
sort!   0.210000   0.010000   0.220000 (  0.214664)

最后，让我们尝试使用 benchmark 进行热身。我们不能在此测试中包含 sort !，因为数组将在预热中就地排序，使其在重要的测试中超快。

arr = 1_000_000.times.map { rand 2_000_000 }
arr1 = arr.dup
arr2 = arr.dup
arr3 = arr.dup

Benchmark.bmbm do |x|
  x.report("max_2")  { max_product(arr1) }
  x.report("rolled") { max_product_rolled(arr2) }
  x.report("sort")   { max_product_sort(arr3) }
end

Rehearsal ------------------------------------------
max_2    0.060000   0.000000   0.060000 (  0.066969)
rolled   0.110000   0.000000   0.110000 (  0.117527)
sort     0.210000   0.020000   0.230000 (  0.244783)
--------------------------------- total: 0.400000sec

             user     system      total        real
max_2    0.050000   0.000000   0.050000 (  0.059948)
rolled   0.100000   0.000000   0.100000 (  0.106099)
sort     0.200000   0.000000   0.200000 (  0.219202)

如您所见，benchmark 结果不同于在 sort! 中使用 fruity 获得的结果，后者在 benchmark 中排在最后，是fruity中的第一个。我想我知道为什么 sort! 在 fruity 中看起来这么好。 果味的github page状态，“我们首先确定获得有意义的时钟测量所需的内部迭代次数......”我怀疑，对于 sort!，这个初始步骤会改变 arr4，歪曲随后报告的测试结果。

就其值(value)而言，基准测试 结果符合我的预期(除了 sort 比 sort! 稍微快一点。