Можете ли вы получить силы в 10 раз быстрее, чем O (log n)? - PullRequest
Новая
       31

Можете ли вы получить силы в 10 раз быстрее, чем O (log n)?

2 голосов
/ 29 декабря 2011

Я знаю, что возведение в степень в большинстве случаев равно O (log n) или хуже, но я теряюсь, пытаясь понять, как числа представляются сами по себе. Возьмем, к примеру, JavaScript, потому что он имеет несколько форматов собственных чисел: 

100000 === 1E5 && 100000 === 0303240
>>> true

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

И, таким образом, вы ожидаете, что +("1E" + n) будет быстрее, чем Math.pow(10, n)?

В основном, этот вопрос о том, как работает 1E (n), но, пытаясь самостоятельно придумать ответ, мне стало более любопытно, как вначале анализируется и сохраняется число. Буду признателен за любые объяснения, которые вы можете предложить.

Ответы [ 4 ]

3 голосов
/ 29 декабря 2011

Я не думаю, что работа со строками может быть быстрее, потому что, по крайней мере, конкатенация создает новый объект (выделение памяти, больше работы для GC), Math.pow обычно сводится к одной машинной инструкции.

Кроме того, некоторые современные виртуальные машины JS выполняют оптимизацию горячих точек, производя машинный код из javascript. Шанс этого есть для Math.pow, но для струнной магии почти невозможно.

Если вы на 100% уверены, что Math.pow работает медленно в вашем приложении (я просто не могу в это поверить), вы можете использовать поиск по массиву, он должен работать максимально быстро: [1,10,100,1000,10000,...][n]. Массив будет относительно небольшим, а сложность O(1).

1 голос
/ 29 декабря 2011

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

Внутренне, не заканчиваются ли все они тем, что они хранятся и обрабатываются как двоичные значения, хранящиеся в памяти?

Да. В javascript есть только один тип чисел, 64-битный тип с плавающей запятой, поэтому 

1 === 1.0

http://www.hunlock.com/blogs/The_Complete_Javascript_Number_Reference

Если это так, может ли машина хранить десятичное и научное представление так же быстро, как и восьмеричное?

Да, опять же, потому что есть только один тип. (Может быть, есть минутная разница, но она должна быть незначительной)

Однако для этого конкретного случая существует ограничение на числа, которые могут быть представлены ~ 1e300, поэтому время выполнения равно O (~ 300) = O (1), все остальные числа представлены как +/- Infinity.

И, таким образом, вы ожидаете, что + ("1E" + n) будет быстрее, чем Math.pow (10, n)?

Не совсем! 1E100 быстрее, чем Math.pow (10, n) Однако + ("1E" + n) медленнее, чем Math.pow (10, n); Не из-за выделения строк и памяти, а потому, что интерпретатор JS должен проанализировать строку и преобразовать ее в число, что медленнее, чем собственная операция Math.pow (num, num).

jsperf test

1 голос
/ 29 декабря 2011

Я запустил jsperf для опций. 

var sum = 0;
for (var i = 1; i < 20; ++i){
  sum += +("1E" + i);
}

работает медленно из-за конкатенации строк. Поэтому 

var sum = 0;
for (var i = 0; i < 20; ++i){
  Math.pow(10, i);
}

быстрее, так как он работает натолько цифры. 

var sum = 0;
sum += 1e0;
sum += 1e1;
...
sum += 1e19;

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

Чтобы получить наилучшие результаты, вы можете заранее рассчитать ответы для себя.

0 голосов
/ 29 декабря 2011

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

"1E" + n выделит 2 ~ 3 строковых объекта, которые могут иметь довольно существенные накладные расходы памяти, уничтожит промежуточные и отформатирует их как числоВряд ли будет быстрее, чем пау.Я опять игнорирую время разбора.

...