Упростите функцию с помощью вызовов Math.pow () и Math.floor () внутри цикла. - PullRequest
Новая
       22

Упростите функцию с помощью вызовов Math.pow () и Math.floor () внутри цикла.

0 голосов
/ 03 июня 2018

Как мне упростить следующую функцию и повторные вызовы на Math.pow()? 

function x(a, b, c) {
    rv = Math.floor(a * Math.pow(2, b));

    for (i = 1; i < c; i++) {
        rv += Math.floor(a * Math.pow(1.2, b + i));
    }

    return rv;
}

Ответы [ 2 ]

0 голосов
/ 04 июня 2018

Исходя из тегов в вашем вопросе, я предполагаю, что вы хотите улучшить производительность этого кода.

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

✏️ Основы:

Во-первых, как Sterling Archer предложил в комментарии, вы должны использовать локальные переменные вместо глобальных, поэтому добавьте let перед ними.

прирост производительности для выполненияэто, вероятно, можно пренебречь, но это не единственная причина изменить его: использование глобальных переменных считается плохой практикой, поскольку они загрязняют глобальное пространство имен и усложняют поддержание вашего кода: Почему глобальные переменные считаются плохой практикой?

⛓️ Запоминание экспоненты:

Вместо выполнения Math.pow(1.2, b + i) на каждой итерации, которую вы можетевычислите текущее значение итерации, используя предыдущее, так как умножение должно быть значительно быстрее возведения в степень: 

let exp = Math.pow(1.2, b);

for (let i = 1; i < c; ++i) {
    exp  *= 1.2;
    rv += Math.floor(a * exp);
}

Этот метод называется memoization .

? Floorс побитовым оператором NOT (~):

Если a положителен, а значения, которые вы используете, всегда равны < 2147483648, вы можете использовать побитовое НЕ (~) Math.floor(), как вы можете видеть здесь: 

console.log(`Math.floor(4.01)  =  ${ Math.floor(4.01) }`);
console.log(`Math.floor(4.99)  =  ${ Math.floor(4.99) }`);
console.log(`Math.floor(-4.01) = ${ Math.floor(-4.01) }`);
console.log(`Math.floor(-4.99) = ${ Math.floor(-4.99) }`);

console.log(`~~4.01  =  ${ ~~4.01 }`);
console.log(`~~4.99  =  ${ ~~4.99 }`);
console.log(`~~-4.01 = ${ ~~-4.01 }`);
console.log(`~~-4.99 = ${ ~~-4.99 }`);

console.log(`Math.floor(2147483647.99) = ${ Math.floor(2147483647.99) }`);
console.log(`Math.floor(2147483648.01) = ${ Math.floor(2147483648.01) }`);
console.log(`~~2147483647.99 = ${ ~~2147483647.99 }`);
console.log(`~~2147483648.01 = ${ ~~2147483648.01 }`);
.as-console-wrapper {
  max-height: 100vh !important;
}

Однако, если вы попытаетесь найти значение >= 2147483648, ~~ обернет и вернет неправильное значение, так как побитовые операторы работают с 32-битнымицелые числа, поэтому максимальное значение, которое вы можете безопасно использовать, составляет 2 31 -1 или 2147483647.

? Этаж с побитовыми операторами альтернативный:

В этом случаевы можете использовать Math.trunc() вместо Math.floor(), что немного быстрее, как вы можете видеть здесь: https://jsperf.com/number-truncating-methods/1

? Экспонента по основанию 2 с оператором левого сдвига:

Аналогично,если b является целым числом st 1 <= b <= 30, вы можете использовать сдвиг влево (<<) вместо первого Math.pow(2, b): 2 << (b - 1): 

for (let i = 0; i <= 31; ++i) {
  console.log(`Math.pow(2, ${ i }) === 2 << (${ i } - 1)? ${ Math.pow(2, i) === 2 << (i - 1) ? 'Yes' : 'No'}.` );
}
.as-console-wrapper {
  max-height: 100vh !important;
}

➰ Используйте цикл while:

Заметили ли вы, что после применения метода запоминания мы не используем переменную i внутрицикл больше?Теперь вы можете заменить for на while, что не даст большого прироста, но все же стоит упомянуть эту опцию: 

while (--c) {
    exp *= 1.2;
    rv += ~~(a * exp);
}

? Окончательный результат:

В целом ваш сверхбыстрый код будет выглядеть так: 

function original(a, b, c) {
  rv = Math.floor(a * Math.pow(2, b));

  for (i = 1; i < c; i++) {
    rv += Math.floor(a * Math.pow(1.2, b+i));
  }

  return rv;
}

function faster(a, b, c) {
  let rv = ~~(a * (2 << (b - 1)));
  let exp = Math.pow(1.2, b);
  
  while (--c) {
    exp *= 1.2;
    rv += ~~(a * exp);
  } 

  return rv;
}

const expected = original(2, 2, 113);
const actual = faster(2, 2, 113);
const ok = expected === actual ;


if (ok) {
  // BEFORE:
  
  const t0b = performance.now();
  
  for (let i = 0; i < 100000; ++i) {
    original(2, 2, 113);
  }
  
  const tb = performance.now() - t0b;
  
  // AFTER:
  
  const t0a = performance.now();
  
  for (let i = 0; i < 100000; ++i) {
    faster(2, 2, 113);
  }
  
  const ta = performance.now() - t0a;
  
  console.log(` BEFORE = ${ tb }s`);
  console.log(`  AFTER = ${ ta }s`);
  console.log(`SPEEDUP = ${ Math.round(100 * tb / ta) / 100 } = ${ Math.round((1 - ta / tb) * 10000) / 100 }% faster!`);
  
} else {
  console.log(`Faster version = ${ actual } does not return the same as before = ${ expected }`);
}
.as-console-wrapper {
  max-height: 100vh !important;
}

un Развертывание цикла:

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

Подробнее о развертывании цикла можно прочитать здесь .

Однако, есливы не представляли результаты, вы могли бы сохранить много вычислений: 

function faster (a, b, c) {
    let rv = a * (2 << (b - 1));
    let exp = Math.pow(1.2, b);

    const r = c % 4;

    if (r === 0) {
        exp *= 1.728;
        rv += a * a * a * exp;
    } else if (r === 1) {
        c += 3;
    } else if (r === 2) {
        exp *= 1.2;
        rv += a * exp;
        c += 2;
    } else if (r === 3) {
        exp *= 1.44;
        rv += a * a * exp;
        c += 1;
    }

    a = Math.pow(a, 4);
    c /= 4;

    while (--c) {
        exp *= 2.0736;
        rv += a * exp;
    }

    return rv;
}

Как вы видите, преимущество в том, что вы сможете комбинировать вычисления нескольких итераций в одномодин, вместо того, чтобы просто дублировать их, как вы должны сделать в исходном коде.Только для демонстрационных целей: 

function original(a, b, c) {
  rv = Math.floor(a * Math.pow(2, b));

  for (i = 1; i < c; i++) {
    rv += Math.floor(a * Math.pow(1.2, b+i));
  }

  return rv;
}

function faster(a, b, c) {
  let rv = ~~(a * (2 << (b - 1)));
  let exp = Math.pow(1.2, b);
  
  const r = c % 4;
  
  if (r === 0) {
    exp *= 1.2;
    rv += ~~(a * exp);
    exp *= 1.2;
    rv += ~~(a * exp);
    exp *= 1.2;
    rv += ~~(a * exp);
  } else if (r === 1) {
    c += 3;
  } else if (r === 2) {
    exp *= 1.2;
    rv += ~~(a * exp);
    c += 2;
  } else if (r === 3) {
    exp *= 1.2;
    rv += ~~(a * exp);
    exp *= 1.2;
    rv += ~~(a * exp);
    c += 1;
  }
  
  c /= 4;
  
  while (--c) {
    exp *= 1.2;
    rv += ~~(a * exp);
    exp *= 1.2;
    rv += ~~(a * exp);
    exp *= 1.2;
    rv += ~~(a * exp);
    exp *= 1.2;
    rv += ~~(a * exp);
  }

  return rv;
}

const expected = original(2, 2, 113);
const actual = faster(2, 2, 113);
const ok = expected === actual;

if (ok) {
  // BEFORE:
  
  const t0b = performance.now();
  
  for (let i = 0; i < 100000; ++i) {
    original(2, 2, 113);
  }
  
  const tb = performance.now() - t0b;
  
  // AFTER:
  
  const t0a = performance.now();
  
  for (let i = 0; i < 100000; ++i) {
    faster(2, 2, 113);
  }
  
  const ta = performance.now() - t0a;
  
  console.log(` BEFORE = ${ tb }s`);
  console.log(`  AFTER = ${ ta }s`);
  console.log(`SPEEDUP = ${ Math.round(100 * tb / ta) / 100 } = ${ Math.round((1 - ta / tb) * 10000) / 100 }% faster!`);
  
} else {
  console.log(`Faster version = ${ actual } does not return the same as before = ${ expected }`);
}
.as-console-wrapper {
  max-height: 100vh !important;
}

☝️ Совет:

Кроме того, вы должны прочитать https://stackoverflow.com/help/how-to-ask перед тем, как писать другой вопрос, чтобы люди не понизили его..

0 голосов
/ 04 июня 2018

Если вы беспокоитесь о том, чтобы вычислить все 1.2 ^ (b + i) для больших диапазонов, подумайте, что нижележащие слои могут вывести результат из предыдущего в оптимизации компиляторов.Однако, если вы хотите помочь ему явно, вы можете сделать что-то вроде 

function x (a, b, c) {
  var rv = Math.floor(a * Math.pow(2, b))
  var multiplier = Math.pow(1.2, b + 1)
  for (i = 1; i < c; i++) {
    rv += Math.floor(a * multiplier);
    multiplier *= 1.2
  }
  return rv;
}

просто математика.

...