Производительность JavaScript Math.sqrt

Профилируя код, я нашел файл Math.sqrt. функция конкретно является основным узким местом в большом двойном вложенном цикле, который выполняется на каждом временном шаге в моей программе. Есть ли способ улучшить его производительность? Должен ли я встроить какой-то итеративный расчет или расчет на основе таблицы поиска?

Любая помощь будет принята с благодарностью!

Вместо этого я не могу заменить его вычислением квадратов, так как это не сравнение.

EDIT: соответствующая часть кода выглядит примерно следующим образом.

var width = 2000;
var height = 2000;

function update() {
    for (var j = 0; j < height; ++j) {
        for (var i = 0; i < width; ++i) {
            array[i][j] = Math.sqrt(/* some expression involving i and j */);
        }
    }
}

var fps = 60;
setInterval(update, 1000 / fps);

person user76284    schedule 24.05.2016    source источник
comment
я люблю этот вопрос   -  person Joe Thomas    schedule 25.05.2016
comment
Квадратный корень занимает больше времени, чем простые операции. Как именно выглядит код? Не видя, что именно вы делаете, маловероятно, что кто-то сможет вам помочь. Вы мало что можете сделать с тем, как работают функции Math.   -  person Pointy    schedule 25.05.2016
comment
Так вы просите алгоритмы для вычисления квадратных корней? Какой уровень точности требуется? Для какого диапазона значений необходимо вычислять квадратные корни?   -  person RobG    schedule 25.05.2016
comment
Я не уверен, что Javascript использует числа с плавающей запятой двойной точности для хранения нецелых чисел, а Math.sqrt использует инструкцию FPU en.wikipedia.org/wiki/Double-precision_floating-point_format, который эквивалентен возможному умножению от 4 до 10 @Pointy как-медленно-сколько-циклов-вычисляет-квадратный-корень   -  person reuns    schedule 25.05.2016
comment
@user1952009 user1952009 JavaScript использует числа с плавающей запятой двойной точности для хранения всех чисел. Я бы сказал, что время, затрачиваемое на умножение в два или четыре раза больше, будет считаться более длительным, не так ли? И вы до сих пор не опубликовали код.   -  person Pointy    schedule 25.05.2016
comment
@Пойнти: ??? я сказал что-то плохое? Я отправил его вам, потому что вы говорили о количестве циклов, которое требуется, что подробно описано в ссылке, которую я дал. а вы уверены в целых числах?   -  person reuns    schedule 25.05.2016
comment
@user1952009 user1952009 В ссылке, на которую вы указали, указано, что функция квадратного корня в 4-13 раз медленнее, чем сложение. Это означает, что это медленнее, чем простые операции.   -  person Mike Cluck    schedule 25.05.2016
comment
@Pointy: да, вы правы для целых чисел, которые хранятся как двойные, спасибо. Я проверил a = Math.floor(Math.pow(2,31)); б = а * а; с = б+1; мы получаем c==b, следовательно, он не использует int64 и не использует int32, потому что a = Math.floor(Math.pow(2,22)); б = а * а; с = б+1; мы получаем b != c.   -  person reuns    schedule 25.05.2016
comment
@user1952009 user1952009 да, я до боли осознаю тот факт, что числа в JavaScript всегда двойные :) Внутренние вычисления выполняются как целые числа, но числа в состоянии покоя являются двойными. В любом случае, этот вопрос трудно решить, если у нас нет кода.   -  person Pointy    schedule 25.05.2016
comment
@Pointy: я глупо подумал, что, например, V8 оптимизирует такие базовые вещи, как хранение целых чисел как целых чисел ...   -  person reuns    schedule 25.05.2016
comment
@Pointy: и я только что вспомнил, что есть (очень особенный) UInt8Array, который не хранит целые числа как двойные! stackoverflow.com/a/33578970/1952009   -  person reuns    schedule 25.05.2016
comment
@user1952009 user1952009 V8 действительно оптимизирует основные целочисленные операции, такие как сравнения! Я получил много ненависти за то, что задал вопрос об этом. stackoverflow.com/questions/37336371/   -  person Joe Thomas    schedule 25.05.2016
comment
@wateriswet : так как вы объясните, что я получил с моим тестом Math.floor(Math.pow(2,k))+1; ?? может быть, кому-то стоит посмотреть исходный код V8   -  person reuns    schedule 25.05.2016
comment
@ user1952009 Я не могу. Я не прочесывал источник v8. Я просто знаю из своих тестов, что V8, похоже, выполняет какую-то оптимизацию с целыми числами. Да, кто-то должен.   -  person Joe Thomas    schedule 25.05.2016
comment
Да, получить квадратный корень сложно. Однако, если вы используете только определенные целые числа. Допустим, вы используете math.random 0-100. Тогда вы, вероятно, сможете написать гораздо более быструю таблицу назначения массивов для используемых значений.   -  person David    schedule 25.05.2016
comment
Я протестировал как ручной метод Ньютона с пониженной точностью, так и печально известный инверсный метод землетрясений, и ни один из них не может сравниться с производительностью родного квадратного корня. Интересно, что обратное землетрясение в javascript лучше всего работает с собственным квадратным корнем в хроме. Однако (y * quake(y)) по-прежнему медленнее, чем Math.sqrt(y) в моем тестировании   -  person JonSG    schedule 25.05.2016
comment
@Pointy Добавлен код к вопросу.   -  person user76284    schedule 25.05.2016
comment
Если кто-то хочет увидеть, как метод Quake синхронизируется с нативным sqrt(), дайте мне знать, и я опубликую код. Поскольку это медленнее, на самом деле это не ответ, поэтому я не стал его публиковать.   -  person JonSG    schedule 25.05.2016
comment
Что такое /* какое-то выражение, включающее i и j */ точно?   -  person Woody    schedule 09.09.2016
comment
Если ваш аргумент sqrt часто один и тот же, вы можете рассмотреть возможность использования таблицы поиска.   -  person kvantour    schedule 04.12.2018


Ответы (1)


При выполнении итерации в двумерном массиве вы можете уменьшить число итераций на ~2.

Например:

если ваше выражение i x j, а ваш массив имеет размер 3-3, начиная с 0, вы собираетесь вычислять в своем цикле:

  • 0*1 И 1*0
  • 0*2 И 2*0
  • 1*2 И 2*1

что то же самое

0x0 1x0 2x0

0x1 1x1 2x1

0x2 1x2 2x2

person Woody    schedule 20.07.2016
comment
Алгоритм по-прежнему будет O (n ^ 2), поэтому это предложение не слишком поможет. В данном примере у него 2000 х 2000, то есть 4 000 000 итераций. Уменьшить его на 2000 было бы каплей в море. Было бы лучше атаковать сам алгоритм, если это возможно. Выполнение 4 000 000 вызовов Math.sqrt() каждые 16 мс немного... требовательно. - person Sam; 01.04.2017
comment
На самом деле количество итераций будет ((N ^ 2 - N)/2) + N (верхний треугольник + диагональ), что довольно эквивалентно N ^ 2/2. Например, матрица 2000 x 2000 может быть уменьшена примерно до 2 000 000 итераций. - person Woody; 03.04.2017
comment
Вуди, ты не знаком с нотацией Big O? - person Sam; 03.04.2017