Концептуально простой и понятный способ вычисления коэффициентов заданного числа n может выглядеть следующим образом:
# ruby
def factors(n)
(1..n).select { |int| n % int == 0 }
end
// javascript
function factors(n) {
return Array(n).fill().map((_, idx) => idx + 1)
.filter(int => n % int === 0);
}
Эти примеры кода выполняют свою работу. Они перебирают полный список чисел от 1 до n, выбирая только те числа, на которые n можно разделить без остатка. Как и ожидалось, возвращенный результат представляет собой массив факторов n. Хотя этот подход работает, это то, что мы называем подходом «грубой силы», и он очень медленный. Скорость кода может не иметь большого значения, когда мы вычисляем коэффициенты относительно небольшого числа. Однако, если на входе очень большое число, неэффективность этого алгоритма становится очевидной. Мы можем быть более умными, чем это.
Более быстрый подход
Вместо того, чтобы перебирать каждое число от 1 до n, мы можем остановиться после достижения квадратного корня из n. Или, точнее, пол квадратного корня из n (в случае квадратного корня, который не является целым числом). Например, квадратный корень из 48 равен 6,92820323028. При вычислении коэффициентов 48 мы должны выполнять итерацию от 1 до 6.
При использовании этого подхода мы можем добавлять до двух чисел в наш список факторов на каждой итерации. Концептуально это помогает думать о наших факторах как о парах. Представьте себе двумерный массив, содержащий все множители числа 24: [[1, 24], [2, 12], [3, 8], [4, 6]] , почему бы не добавить оба элемента пары одновременно? (примечание: приведенный ниже код создает плоский массив факторов). По мере того, как мы итерируем от 1 до квадратного корня из n, когда мы найдем целый делитель n (пусть это будет i), мы добавим i в список множителей вместе с числом, на которое мы должны умножить i, чтобы вернуть продукт n.
Есть одно исключение. При нахождении множителей квадратного числа вы, вероятно, захотите включить квадратный корень только один раз. Мы учитываем это в строке 8 приведенного ниже кода.
# ruby
def factors(n)
factors = []
limit = Math.sqrt(n).floor
(1..limit).each do |i|
if n % i == 0
factors.push(i)
factors.push(n / i) if (n / i) != i
end
end
factors
end
Вот тот же подход, написанный на JavaScript:
// javascript
function factors(n) {
const factors = [];
const limit = Math.floor(Math.sqrt(n));
for (let i = 1; i <= limit; i++) {
if (n % i == 0) {
factors.push(i);
if (n / i !== i) { factors.push(n / i) }
}
}
return factors;
}
Если вы протестируете этот код с небольшими числовыми аргументами, вы вряд ли заметите разницу в скорости кода. Вы можете посмотреть на увеличенное количество строк в более эффективном коде и подумать: а оно действительно необходимо?. Попробуйте вместо этого запустить эти примеры кода с гораздо большим вводом — factors(108800324) — и вы заметите большую разницу. Фактически, исходная реализация JavaScript factors может вызвать ошибку — JavaScript heap out of memory.
Бенчмаркинг
Вы можете изучить разницу в скорости двух наших ruby-методов, factors, с помощью модуля Benchmark. Это довольно просто! Ниже я переименовал наши два метода ruby, чтобы различать их, и использовал модуль Benchmark для анализа их скорости.
require 'benchmark'
def slow_factors(n)
(1..n).select { |int| n % int == 0 }
end
def faster_factors(n)
factors = []
limit = Math.sqrt(n).floor
(1..limit).each do |i|
if n % i == 0
factors.push(i)
factors.push(n / i) if (n / i) != i
end
end
factors
end
Benchmark.bm do |bm|
bm.report { slow_factors(108_800_324) }
bm.report { faster_factors(108_800_324) }
end
Вот сообщаемые данные:
user system total real 8.250000 0.010000 8.260000 ( 8.265131) 0.000000 0.000000 0.000000 ( 0.000724)
Какая разница! В этом примере используется очень большой ввод, но вы все равно увидите разницу при использовании небольшого ввода:
Benchmark.bm do |bm|
bm.report { slow_factors(6024) }
bm.report { faster_factors(6024) }
end
# data:
user system total real
0.000000 0.000000 0.000000 ( 0.000467)
0.000000 0.000000 0.000000 ( 0.000018)
В JavaScript методы console.time и console.timeEnd забавны. Использование аргумента 108800324 с нашей более медленной функцией factor привело к ошибке, поэтому нам придется сравнить наш код с чем-то меньшим.
Я переименовал две функции JavaScript factor, чтобы различать их, и запустил их с помощью приведенного ниже кода:
console.time("slow factors");
slowFactors(1800324);
console.timeEnd("slow factors");
console.time("faster factors");
fasterFactors(1800324);
console.timeEnd("faster factors");
Результат:
slow factors: 1455.518ms faster factors: 0.143ms
Вы можете увидеть существенную разницу в скорости здесь, даже с гораздо меньшим числовым аргументом.
Как начинающий программист или когда вы впервые задумываетесь о том, как подойти к проблеме, с которой вы раньше не сталкивались, я рекомендую сначала обрисовать в общих чертах самый простой возможный подход — даже если это «грубая сила». Не пытайтесь быть слишком умным сразу. Обратите особое внимание на требования задачи и используйте методичный пошаговый план для решения некоторых более простых тестовых случаев. После того, как вы подтвердите свое понимание проблемы, более подробно изучите, как вы можете оптимизировать свой код, чтобы выполнять работу более эффективно.
Пример создания списка множителей для числа n довольно прост, но я обнаружил, что этот шаблон полезен при работе с задачами всех уровней сложности. Я надеюсь, что это простое пошаговое руководство было полезным для тех, кто пытается установить подобный шаблон в своей работе!
Хотите стать участником Medium?
Если вы хотите узнать больше здесь, на Medium, вы можете зарегистрироваться по моей реферальной ссылке. Обратите внимание, что я получу часть членского взноса.
