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

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的宝石。使用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看起来很好。 fruity的github page指出：“我们首先确定获得有意义的时钟测量所需的内部迭代次数......”我怀疑，对于sort!，这个初始步骤变异为arr4，使所报告的测试结果出现偏差。

对于它的价值，在benchmark结果是我的预期（除了sort比sort!稍快一些什么