如何快速乘以两个最大的数组元素

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

允许可枚举的 #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热身.我们不能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结果从那些使用获得的不同fruity在于sort!,它是持续的benchmark,是第一个在fruity.我想我知道为什么sort!看起来这么好fruity.fruity的github上页指出:'我们首先确定获得有意义的时钟测量所需的内部迭代次数......’我怀疑的是,对于sort!这第一步变异arr4,歪斜下面的试验报告的结果.

对于它的价值,benchmark结果是我的预期(除了sort比...稍快)sort!.