Как упростить проверку числа на палиндром и увеличить скорость выполнения кода?

Question

[Pavel Shevelev]

const isPalindroms = (num) => {
  let newArr = num.toString();
 return newArr === newArr.split('').reverse().join('');
};

console.log(isPalindroms(12)); // false
console.log(isPalindroms(121)); // true

Answer 1

[Rsa97]

const isPalindrom = (num) => num === Number(num.toString().split('').reverse().join(''));

Comments

[Pavel Shevelev]

Немного лучше, а есть предложение, как увеличить скорость выполнения?

Answer 2

[WbICHA]

const isPalindrome = num => {
    let revNum = 0;
    for(let j = num; j > 0; j = Math.trunc(j / 10)) {
      revNum = revNum * 10 + (j % 10);
    }
    return num === revNum;
  }

Answer 3

[Дмитрий Беляев]

Задача проверки последовательности на палиндром решается за O(n/2). Но для этого нужно иметь последовательный доступ к обоим концам последовательности за O(1).
Если такой возможности нет и имеется доступ только к одному из концов последовательности, то придется обойти всю последовательность, а это уже O(n). Один из таких, достаточно оптимальных алгоритмов для цифр целого числа уже представил WbICHA.

Чтоб решить эту задачу за O(n/2) нужно понять, как получить крайние цифры числа за O(1).
Крайнюю справа цифру можно получить простым остатком от деления на основание системы счисления, то есть, в случае десятичной системы счисления, на 10.
Для получения крайней справа цифры нужно знать ее порядок (считая справа начиная с 0). Это можно сделать взяв целую часть от логарифма по основанию системы счисления (10). На JS такая операция будет выглядеть так:
Math.trunc(Math.log10(num))
Целая часть от деления числа на 10 в степени порядка правой цифры даст саму эту цифру. На JS это выражается так:

Math.trunc(num / 10 ** Math.trunc(Math.log10(num)))

Так же алгоритм требует равномерного перемещения по последовательности от краев к центру.
Для правой цифры опять все просто, можно брать целую часть от деления числа на основание (10).
Для левой нужно умножить ее на основание в степени порядка и вычесть результат из самого числа, то есть:

num - leftDigit * 10 ** Math.trunc(Math.log10(num))

Осталось учесть пограничные условия:
1. Если крайний левый и крайний правый элемент не равны, то последовательность не является палиндромом
2. Последовательность из одного элемента (число из одной цифры) всегда палиндром.
3. При равенстве крайних элементов последовательность будет палиндромом если палиндромом так же является подпоследовательность без этих элементов.

Пункт 3 подразумевает рекурсию, но такая рекурсия легко разворачивается в цикл, что конечно же более оптимально.

По итогу получим такую функцию:

const isPalindrome = num => {
    let n = num;
    while (n >= 10) {
        const order = 10 ** Math.trunc(Math.log10(n));
        const leftDigit = Math.trunc(n / order);
        const rightDigit = n % 10;
        if (leftDigit !== rightDigit) return false;
        n -= leftDigit * order;
        n /= 10;
        n = Math.trunc(n);
    }
    return true;
};

P.S. варианты с приведением числа к строке, а тем более с последующим разбиением на массив чисел и разворотом его, просто отвратительны.
Приведение числа к строке - это O(n) если не больше, так как в JS тип number - это по сути float64 и алгоритм приведения учитывает, что число может быть с дробной частью.
Разбиение строки на массив символов (split) - O(n) и требует доп памяти под этот массив.
Реверс массива - O(n/2)
Склейка (join) - опять O(n)
Сравнение строк - еще раз O(n)
И хотя суммарная сложность останется O(n), количество проходов по цифрам числа будет в 5 раз больше, хотя даже на строках можно уложится в 1.5 обхода:

const isPalindrome = num => {
    const s = String(num);
    for (let i = 0; i < s.length / 2; i++) {
        if (s[i] !== s[s.length - i - 1]) return false;
    }
    return true;
};

Comments

[WbICHA]

Оптимизировал немного:

const isPalindrome = num => {
    let n = num;
    let order = 10 ** ~~(Math.log10(n));
    
    while (n >= 10) {
      const leftDigit = ~~(n / order);
      const rightDigit = n % 10;
      
      if (leftDigit !== rightDigit) {
        return false;
      }
      
      n = Math.trunc((n - leftDigit * order) / 10);
      order /= 100;
    }

    return true;
};

Но стоит отметить, что оно всё равно намного медленнее моего решения, даже если первый же символ отличается.
Честно говоря, я не очень понимаю почему, однако это так, что в фф, что в хроме.

П.с.: транк в фф ппц медленный... Добавление одного транка в цикл замедляет функцию в 4-5 раз.

[Дмитрий Беляев]

WbICHA, хм, если числа только положительные, то можно Math.floor попробовать.
И что-то мне подсказывает, что order нужно делить на 10, а не на 100 на каждом шаге.
Еще как вариант, попробовать bigint использовать, с ним можно будет уйти от округлений и внутреннего перерасчета экспоненты числа при делении.

[Дмитрий Беляев]

WbICHA, если честно я подошел к задаче чисто с точки зрения алгоритмов, не делая бенчмарки и т.д.
Встреться у меня подобная задача на реальном проекте, я бы вообще все переписал на Си или Раст и загнал бы в wasm. Есть особенность в x86-64 процах, что такие числодробилки в разы шустрее работают, если все вычисления будут в int32.
Основная проблема в JS с вычислениями в том, что number это float64.

[WbICHA]

Дмитрий Беляев,

если числа только положительные, то можно Math.floor попробовать.

В фф все функции округления тормознутые.)

И что-то мне подсказывает, что order нужно делить на 10, а не на 100 на каждом шаге.

Нет, мы удаляем 2 цифры на каждом шаге.)

если честно я подошел к задаче чисто с точки зрения алгоритмов, не делая бенчмарки и т.д.

Да это понятное дело, алгоритм однозначно лучше, но суровая реальность...)