Как быстро умножить два самых больших элемента массива

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 камень.

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. fruity0: «Мы сначала определяем количество внутренних итераций, необходимых для получения значимого измерения часов ...» Я подозреваю, что для sort! этот начальный шаг мутирует arr4, искажая результаты приведенного теста.

Для чего это стоит, то benchmark результаты, что я ожидал (для sort будучи немного быстрее, чем sort! кроме