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

我正在做一个挑战，它要求一种方法来乘以数组中最大的两个元素，并找到一个不到一秒钟的解决方案。
这是我现在大约1.6秒的时间

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

我怎样重写才能加快速度？

最佳答案

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

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

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包含在这个测试中，因为数组将在预热时被排序到适当的位置，从而使它在测试中超快地计数。

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)

如您所见，sort !的结果与使用benchmark获得的结果不同，因为fruity是sort!中的最后一个，是benchmark中的第一个。我想我知道为什么fruity在sort!中看起来那么好。fruity的github page声明，“我们首先确定获得有意义的时钟测量所需的内部迭代次数…”我怀疑，对于fruity，这一初始步骤会发生变异，使随后报告的测试结果出现偏差。
值得一提的是，sort!的结果是我所期望的（除了arr4比benchmark稍快）。