JavaScript-цикл слишком медленный - PullRequest
Новая
       26

JavaScript-цикл слишком медленный

2 голосов
/ 29 октября 2019

Я работаю над задачей над кодовыми войнами и не могу понять, как заставить эту функцию работать быстрее для больших чисел <= 200000000000000. Цель этой функции очень проста - мне просто нужно подсчитать все вхождения «1» в двоичном видепредставления чисел между «левым» и «правым» (включая оба). </p> 

function countOnes(left, right) {
var sum=0;
for (var i=left; i<=right; i++){
    var h=i.toString(2);
    var len=h.length;
    for (var j=0; j<len; j++){
        if (h[j]==1){sum++;}
    }
}
return sum;
}

Заранее спасибо

Ответы [ 2 ]

1 голос
/ 29 октября 2019

Поскольку битовые операторы ограничены 32 битами (см. Примечания), это решение увеличивает этот предел до 2**53 -1, что является значением JS Number.MAX_SAFE_INTEGER
см. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number/MAX_SAFE_INTEGER 

const p32 = 2**32

function countOnes_John_MJojo(left, right )
  {
  let sum = 0
  for (let V=left; V<=right; V++)
    {
    for (let N=V;N; N&=N-1) sum++
    for (let N=Math.trunc(V/p32);N; N&=N-1) sum++
    } 
  return sum
  }

/ - history: - \
\ -------------- /

Чуть быстрее используются побитовые операторы:
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Bitwise_Operators

-> логическое И
-> Логическое смещение вправо 

function countOnesBin( left, right )
  {
  let sum = 0
  for (let N=left; N<=right; N++)
    {
    let Bin = N
    for(let x = N.toString(2).length;x--;)
      {
      if ( Bin & 1 ) sum++ 
      Bin = Bin >>1
      } 
    } 
  return sum
  }

при @ CodeBling предполагают, что это может быть лучше! 

function countOnes_CodeBling  (left, right)
  {
  let sum = 0
  for (let N=left; N<=right; N++)
    {
    for(let Bin = N; Bin > 0; Bin = Bin >> 1)
      { if ( Bin & 1 ) sum++  } 
    } 
  return sum
  }

этот самый лучший! Я не знал возможности: Спасибо @ Джон 

function countOnes_John (left, right)
  {
  let sum = 0
  for (let V=left; V<=right; V++)
    {
    for (let N=V;N; N&=N-1) sum++
    } 
  return sum
  }
0 голосов
/ 29 октября 2019

Вы можете избежать второй итерации, используя функцию разбиения и добавляя к своей сумме количество кусков минус один: 

function countOnes(left, right) {
  var sum=0;
  for (var i=left; i<=right; i++){
    var h=i.toString(2);
    sum += h.split('1').length -1;
  }
  return sum;
}

Это все равно будет медленным, но намного быстрее, чем ваш исходный код.

...