Оптимальная проверка, если число является Палиндромом в JS

Question

У меня проблема, с которой я сижу последние несколько дней.

Я хочу написать оптимальную (в JS) программу для проверки, является ли число палиндромом.

Мой текущий подход:

function isPalidrom2(pali){
//MOST time consuming call - I am splitting the digit into char array. 
  var digits = (""+pali).split("");
//To get the length of it. 
  var size = digits.length;
  var isPali = true;
  for(var i = 0; i<Math.floor(size/2); i++){
    //I am comparing digits (first vs last, second vs last-1, etc.) one by one, if ANY of the pars is not correct I am breaking the loop. 
    if(parseInt(digits[i]) != parseInt(digits[size-i-1])){
      isPali = false;
      break;
    }
  }
  return isPali;
}

Это не оптимально.Наибольшее количество времени, которое я затягиваю, - это переход с INT на STRING.

И у меня нет идей - я пытался понять операторы BIT, но не могу.- Я пытался гуглить и искать альтернативные подходы - но я ничего не могу найти.- Я пытался играть с разными алгоритмами - но этот самый быстрый, который я смог применить.

Итак, вкратце - мой вопрос: "Как я могу сделать это быстрее?"

РЕДАКТИРОВАТЬ:

Итак, задачу, которую я хочу решить:

Найти все простые числа в диапазоне всех пятизначных чисел.Среди всех множителей (i * j), которые они находятся между ними, найти наиболее значимый палиндром.

Мой текущий подход:

function isPrime(number){
  var prime = true;
  var i
  for(i = 2; i<= number/2; i++){
if((number%i)==0){
  prime = false;
  break;
}
  }
  return prime;
}

function get5DigitPrimeNr(){
  var a5DigitsPrime = [];
  var i;
  for(i = 10000; i<100000; i++){
if(isPrime(i)){
  a5DigitsPrime.push(i)
}
  }
  return a5DigitsPrime;
}

function isPalidrom(pali){
  var digits = (""+pali).split("");
  //we check if first and last are the same - if true, we can progress
  size = digits.length;
  return
(digits[0]==digits[size-1]) &&
(parseInt(digits.slice(1, Math.floor(size/2)).join("")) ==
  parseInt(digits.reverse().slice(1, Math.floor(size/2)).join("")))
}

function isPalidrom2_48s(str) {
  var str = str.toString();
  const lower = str.substr(0, Math.floor(str.length / 2));
  const upper = str.substr(Math.ceil(str.length / 2));
  return lower.split("").reverse().join("") === upper;
}

function isPalidrom_22s(pali){
  var digits = (""+pali).split("");
  var size = digits.length;
  for(var i = 0; i<Math.floor(size/2); i++){
//console.log("I am comparing: "+i+", and "+(size-i-1)+" elements in array")
//console.log("I am comparing digit: "+digits[i]+", and "+digits[(size-i-1)]+"")
if(digits[i] !== digits[size-i-1]){
  //console.log('nie sa rowne, koniec')
  return false;
}
  }
  return true;
}

function isPalidrom2_80s(pali){
  return parseInt(pali) == parseInt((""+pali).split("").reverse().join(""))
}

function runme(){
  var prime5digits = get5DigitPrimeNr();
  var size = prime5digits.length;
  var max = 0;
  var message = "";
  for(var i = 0; i<size; i++){
for(var j = 0; j<size; j++){
  var nr = prime5digits[i]*prime5digits[j];
  if(nr>max && isPalidrom2(nr)){
    max = nr;
    message = 'biggest palidrome nr: '+nr+', made from numbers: '+prime5digits[i]+' x '+prime5digits[j];
  }
}
  }
  console.log(message)
}

function timeMe(){
  var t0 = performance.now();
  runme();
  var t1 = performance.now();
  console.log("Function took " + millisToMinutesAndSeconds(t1 - t0) + " s to find the perfect palindrom.")
}

//helper functons:

function millisToMinutesAndSeconds(millis) {
  var minutes = Math.floor(millis / 60000);
  var seconds = ((millis % 60000) / 1000).toFixed(0);
  return minutes + ":" + (seconds < 10 ? '0' : '') + seconds;
}

Answer 1

Код:

Существует несколько методов, которые вы можете использовать (не знаю, являются ли они оптимальными):

Palindrom = _ => (_=''+_) === [..._].sort(_=>1).join``

Некоторые другие:

let isPalindrome = __ => (_=(__=__+'').length)==0||_==1?!0:__[0]==__.slice(-1)?isPalindrome(__.slice(1,-1)):!1

let isPalindrome = (s,i) => (i=i||0)<0||i>=(s=''+s).length>>1||s[i]==s[s.length-1-i]&&isPalindrome(s,++i);

let isPalindrome = (str) => {
  var len = ~~((str=str+'').length / 2);
  for (var i = 0; i < len; i++)
    if (str[i] !== str[str.length - i - 1])
      return false;
  return true;
}

Обновление теперь принимает числа в качестве ввода

Answer 2

Чтобы сохранить дух вашего кода, вы можете выйти из цикла с return вместо break и использовать строку напрямую без преобразования в массив.Строки в виде массивов имеют возможность доступа к одному символу с индексом.

function isPalidrom2(value) {
    var digits = value.toString(),
        length = digits.length,
        i, l;

    for (i = 0, l = length >> 1; i < l; i++) {
        if (digits[i] !== digits[length - i - 1]) {
            return false;
       }
    }
    return true;
}

console.log(isPalidrom2(1));
console.log(isPalidrom2(12));
console.log(isPalidrom2(1221));
console.log(isPalidrom2(123));

Answer 3

Если вы пытаетесь ускорить процесс, вы можете сэкономить еще несколько секунд, оптимизировав свою функцию isPrime(n).

• Вам не нужно проверять каждый фактор, толькопростые множители меньше sqrt(n)
• Если вы проверяете каждое число от 2 до 99999 в порядке возрастания, вы можете сохранять результаты по ходу, поэтому вам не нужно продолжать пересчитывать список предыдущихпростые числа

Примерно так:

var savedPrimes = [2]

function isPrime(n){
    // call this method with increasing values of n (starting at 2), saving primes as we go,
    // so we can safely assume that savedPrimes contains all primes less than n
    for(var i=0; i<savedPrimes.length; i++)
    {
        var f = savedPrimes[i];
        if ((n % f) == 0)
            return false; // found a factor
        if (f*f>=n)
            break; // stop checking after f >= sqrt(n)
    }
    // no prime factors - we found a new prime
    savedPrimes.push(n);
    return true;
}


function get5DigitPrimeNr(){
    var a5DigitsPrime = [];
    var i;

    // first find all the primes less than 10000
    for(i = 3; i<10000; i++){
        isPrime(i);
    }

    // now find (and keep) the rest of the primes up to 99999
    for(i = 10000; i<100000; i++){
        if(isPrime(i)){
            a5DigitsPrime.push(i)
        }
    }
    return a5DigitsPrime;
}

РЕДАКТИРОВАТЬ - когда я запускаю ваш код с помощью этого метода, я получаю время 10 сек

Answer 4

Быстрее всего, вероятно, полагаться на нативные методы javascripts:

 function isPalindrome(str) {
   const lower = str.substr(0, Math.floor(str.length / 2));
   const upper = str.substr(Math.ceil(str.length / 2));

   return lower.split("").reverse().join("") === upper;
}

Или исключить все ненужные преобразования из вашего кода:

function isPlaindrome(str) {
  const half = str.length / 2;
  for(var i = 0; i < half; i++)
    if(str[i] !== str[str.length - i - 1])
       return false;
  return true;
}