codewars: square every digit
⚠️ Статья наполнена спойлерами. Если вы хотите сами решить задачу, то вернитесь к статье только после того как решите ее сами или если у вас закончится терпение 😉
Недавно я откапал свой логин/пароль к codewars и наткнулся на задачку с таким описанием:
You are asked to square every digit of a number and concatenate them. For example, if we run 9119 through the function, 811181 will come out, because 9^2 is 81 and 1^2 is 1. Note: The function accepts an integer and returns an integer
Смысл в том, что на вход функции поступает число, каждый разряд которого нужно возвести в квадрат. Полученные квадраты разрядов нужно объединить и вернуть из функции.
На входе и на выходе должны быть именно числа (typeof x === 'number'). Примеры:
fn(3212) // 9414 fn(9119) //811181
Я решил задачку по-своему - так, как считал оптимальным, затем посмотрел как решили другие, сделал определенные выводы, которые показались мне интересными. Затем задал вопрос подписчикам моего telegram-канала - как они решили бы эту задачу. Собрал варианты, которые они предложили, сгруппировал их, и в этой статье хочу сравнить их. Все решения будем сравнивать относительно моего (его приведу ближе к концу).
Замеры я производил на основе 1,000,000 заранее сгенерированных чисел от 0 до 1,000,000
Итак. Конечно же, первое, что приходит в голову - это решение при помощи строк. Оно просто и короткое:
- превратили число в строку
- смапили символы-разряды на их квадраты
- соединили
Но здесь не все так однозначно и решение на строках может быть разным.
Рассмотрим пример:
const fn = val => +[...'' + val].map(n => n ** 2).join('');Это простое решение не эффективно с точки зрения утилизации ресурсов.
Здесь мы делаем много лишних действий:
- преобразуем число в строку
- преобразуем строку в массив
- каждый символ строки преобразуем в число (
n ** 2) - преобразуем получившийся массив в строку
- преобразуем получившуюся строку в число
Этот вариант в 6.9 медленнее эталона 📉
Из этого делаем вывод, что преобразования - это плохо для производительности и нам нужно постараться свести их к минимуму.
Попробуем еще одно решение на строках, но с меньшим количеством преобразований:
function fn(val) {
let res = '';
val = val + '';
for (let i = 0; i < val.length; i++) {
res += val[i] ** 2;
}
return +res;
}- преобразуем число в строку (
val + '') - преобразуем каждый символ в число и обратно (
res += val[i] ** 2) - преобразуем строку в число (
+res)
Этот вариант уже в 3.6 раза медленнее эталона 📉
Роман Дворнов предложил интересное решение
function fn(val) {
return +String(val).replace(/./g, m => m * m);
}Здесь мы используем замену по регулярному выражению, чтобы заменить все числа на их квадраты. Не смотря на небольшое количество преобразований, оно в 10.9 раз медленнее эталона из-за регулярных выражений 📉
Так же Роман предложил развитие идеи:
const xs = ["0", "1", "4", "9", "16", "25", "36", "49", "64", "81"];
function fn(val) {
return +String(val).replace(/[2-9]/g, m => xs[m]);
}Суть в том, что мы заранее высчитываем квадраты чисел от 0 до 9 и записываем их в массив в виде строк (это важно!).
В самой функции мы заменяем числа от 2 до 9 на их предрассчитанные значения из массива. Единицы и нули не имеет смысла заменять, т.к. они останутся без изменений в какую бы степень мы их не возвели.
Предрассчитанные квадраты чисел хранятся в массиве в виде строк чтобы при замене не было приведения числа к строке.
Этот вариант в 9.8 раз медленнеее эталона 📉
Не смотря на низкую производительность, мы вернемся к этому варианту позже.
Очевидно, что преобразования на строках - это не лучшее решение с точки зрения производительности.
Если важна скорость и что-то можно сделать при помощи математики, то лучше деать это при помощи математики.
Возьмем для примера число 3212, оно должно превратиться в 9414.
Как можно проделать с ним все нужные нам операции без пробразований?
Число можно разделить на разряды:
- 9 - разряд тысяч
- 4 - разряд сотен
- 1 - разряд десятков
- 4 - разряд единиц
Как собрать число имея каждый разряд по отдельности?
Необходимо найти сумму произведений каждого разряда на значение этого разряда. Проще говоря:
9414 = (4 * 1) + (1 * 10) + (4 * 100) + (9 * 1000)
Как получить то же самое из числа 3212?
9414 = (2^2 * 1) + (1^2 * 10) + (2^2 * 100) + (3^2 * 1000)
Как реализовать это в виде кода?
function fn(num) {
let multiplier = 1;
let res = 0;
while (num !== 0) {
const digit = num % 10;
const sqr = digit ** 2;
num = ~~(num / 10);
res += sqr * multiplier;
multiplier *= (sqr < 10 ? 10 : 100);
}
return res;
}Если у вас есть вопросы по логике кода, пожалуйста, пишите в комменты.
Подписчики предлагали похожие решения, например:
function fn(n) {
let pow = 0;
const getNum = () => {
let res = Math.floor(n / (10 ** pow));
return res > 0 ? res % 10 : 0;
}
let num;
let result = 0;
let resultPow = 0;
while ((num = getNum()) > 0) {
result += (num * num) * (10 ** resultPow);
resultPow += (num > 3) ? 2 : 1;
pow++;
}
return result;
}Но не смотря на то, что здесь нет преобразований, этот вариант в 6.2 раз медленнее эталона и в 1.7 раз медленне оптимального варианта со строками 📉. Это позволяет сделать вывод, что наличие большого количества операций и вызова функций (добавляют манипуляций со стеком) может нивелировать профит от отсутствия преобразований.
Ближе всего к моему варианту был такой пример:
function fn6(number) {
let result = 0;
let signs = 1;
while (number > 0) {
let digit = number % 10;
result += digit * digit * signs;
signs *= digit > 3 ? 100 : 10;
number = Math.floor(number / 10);
}
return result;
}Он всего на 10% медленнее моего . Но за счет чего?
Дело в том, что Math.floor - это дополнительная логика под капотом и если заменить Math.floor(number / 10) на ~~(number / 10) то мы получим ту же производительность.
Бонус
А теперь давайте вернемся к варианту, который предлагал Роман Дворнов и позаимствуем оттуда идею с предрассчитанными квадратами, объединим с моим вариантом и получим более производительную функцию:
const xn = [0, 1, 4, 9, 16, 25, 36, 49, 64, 81];
function fn(num) {
let multiplier = 1;
let res = 0;
while (num !==0) {
const digit = num % 10;
num = ~~(num / 10);
res += xn[digit] * multiplier;
multiplier *= (num < 4 ? 10 : 100);
}
return res;
}Этот вариант на ~13% быстрее моего изначального варианта за счет того, что мы избавились от математической операции 📈
Ну а позже Роман предложил еще один вариант, до которого у меня самого дошли только мысли, но не руки - заменить часть ариметики на побитовые операции:
const xn = [0, 1, 4, 9, 16, 25, 36, 49, 64, 81];
function fn(num){
let multiplier = 1;
let res = 0;
while(true) {
const digit = num % 10;
res += xn[digit] * multiplier;
if (num === digit) break;
num = ~~(num / 10);
multiplier = digit < 4 ?
(multiplier << 3) + (multiplier << 1) :
(multiplier << 6) + (multiplier << 5) + (multiplier << 2);
}
return res;
}Плюс ко всему, за счет break, мы можем не высчитывать num и multiplier на последней итерации.
Хотя такой код и труднее читать, он на ~20% быстрее моего изначального варианта 📈
Подводя итог
К сожалению, JS в какой-то степени расслабляет и часто мы пишем простой, но не производительный код.
Если вашему коду жизненно важна производительность, то ее надо буквально "выгрызать" любыми доступными способами, экономя любые операции. Но если нужно просто написать производительный код, то пишите его так, чтобы не было лишних операций и тем более ненужных преобразований. Соблюдайте баланс между производительностью и читаемостью.