Javascript-форум (https://javascript.ru/forum/)
-   Общие вопросы Javascript (https://javascript.ru/forum/misc/)
-   -   Оптимизация JavaScript в 10-20 раз, фантастика? А вот нет!! (https://javascript.ru/forum/misc/24228-optimizaciya-javascript-v-10-20-raz-fantastika-vot-net.html)

m4gz 22.12.2011 04:56

Оптимизация JavaScript в 10-20 раз, фантастика? А вот нет!!
 
Искал всевозможные способы обработки байтовой информации в javascript и наткнулся на это. Сначала эта теория меня сильно озадачила, разобравший во всем поподробней пришел к выводу, что это реально! И скрипт может работать и в 20 раз быстрее, все дело в низкоуровневой обработки данных, и даунгрейде, что вы думаете насчет этого?
http://www.webreference.com/programm...pt/jkm3/3.html очень занимательно, кому интересно могу расписать тут, а так все очень понятно по линку!

trikadin 22.12.2011 22:53

Меня как-то напрягают в последнее время такие посты... От них веет неадекватностью..

Nekromancer 22.12.2011 23:49

trikadin,
Мне например ничего не понятно линку. Я конечно просто пробежался мельком, но увидел лишь какую то попытку, что то делать с числами.

trikadin 23.12.2011 02:06

Nekromancer, вот вот. Я тоже почитал, но ничего не понял. Частично дело в незнании английского, но даже из того, что я понял, желание переводить полностью не появилось.

m4gz 23.12.2011 05:45

Попробую коротко изложить суть, мы хотим в памяти отложить например 100 бит - что делает современная машина- 1+2+3+4+5+6+7 до нашего числа N. Получаем в итоге формулу N(N+1)/2 это тоже что и O(N^2) как видим мы постоянно высчитываем квадратный корень, получается для того чтобы записать ячейку размером в 100 нам потребуется работа 10000 ячеек, а 200 уже 40000, т.e. Чем длинее строка тем больше в геометрической прогрессии потребуется затрат. Только так было не всегда, на заре компьютерной эры, когда эвм были очень хилинькие ,применялся совершенно другой подход - первое условие не создавать новые ячейки, а переписывать старые, точнее не переписывать а увеличивать по довольно интересной схеме - оперируя по очереди двумя переменными- увеличивая одну в два раза и после прибавляя другую, мы экономим огромное количество памяти, приведу пример с этого сайта - мы хотим получить переменную в 9 символов - стандартным методом будет выглядеть так: = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 9 в сумме получаем 45 задействованных блоков памяти, а по этой методике получается так:1 + 2 + 4 + 8 + 9 сумма 24. Но чем больше данных тем больше прирост, как пишут по результатам тестов цифры такие - 88 милисекунд против всего четырех!, кому интересно на их сайте выложен микро скрипт

nerv_ 23.12.2011 08:34

m4gz, чтобы не быть голословным, приведите пример, где сравнивается производительность обычного* способа и Вашего хау-ноу :)

*даже и не знаю, что под этим понимать ^_^

m4gz 23.12.2011 08:55

1 это не ноухау а во2 пройди по ссылке, там скрипт, это все стоит на обработке байтов, если делать изначально систему битовой то будет все работать

melky 23.12.2011 09:56

суть укладывается в 2 строчки

x = 'x'; 
s = ''; 
s += x; /* Now s = 'x' */ 
x += x; /* Now x = 'xx' */ 
x += x; /* Now x = 'xxxx' */ 
x += x; /* Now x = 'xxxxxxxx' */ 
s += x; /* Now s = 'xxxxxxxxx' as desired */

it's bullshit.
function stringFill3(x, n) {
    var s = '';
    for (;;) {
        if (n & 1) s += x;
        n >>= 1;
        if (n) x += x;
        else break;
    }
    return s;
}

it's better.
(по скорости, конечно же)
и всё.
осталось только проанализировать, КАК побитовые операции с числами могут иметь какой-то толк с НЕчислами.

PS насчёт скорости. разница в 1.8 раза в FF. в хроме коэффициент 2.5.

PSS краткий разбор (если можно так назвать) этого кода.
function stringFill3(x, n) {
    var s = '';
    for (;;) {
        if (n & 1) s += x;
        n >>= 1;
        if (n) x += x;
        else break;
    }
    return s;
}

сначала создаёт s (результат), далее идёт "бесконечный" цикл (потому что будет работать, пока не прервёшь). таким образом, можно было не выпендриваться и написать цикл через while. и смотрелось бы понятнее.

в каждой итерации цикла к строке s прибавляется, если n & 1. да, конечно, мы все знаем, что & возвращает единичку только для единичек, но что это значит на практике ?
распишем двоичные представления чисел от 1 до 5 (включительно)
Код:

1      0001
2      0010
3      0011
4      0100
5      0101

операция <число> & 1 будет возвращать 1 для тех чисел, у которых последняя цифра (1 для 5, 0 для 4) совпадает с 1 (т.к. единица осталась единицей, то совпадение считается только по последней колонке. если бы вместо единицы с правой стороны оператора было какое-нибудь 0101110, то совпадения высчитывалось для всех пар)
т.е. если мы пройдёмся по всем цифрам из [1,5] с & 1 , то получим это :
1  1
2  0
3  1
4  0
5  1

проверку на нечётность не напоминает ? таким образом , <число> & 1 эквивалентно проверке числа на нечётность. (<число> % 2)

идём дальше.

n >> 1 будет, как известно, будет сдвигать биты один раз (с правой стороны) в числе n. но что это значит ? возьму тот же промежуток.
Код:

1      0001
2      0010
3      0011
4      0100
5      0101

если мы сделаем 2 >> 1, то сдвинем биты в числе 2 в двоичном представлении вправо один раз.
Код:

1 = 0001
1 >> 1
0000 (0)

2  = 0010
2 >> 1
0001 (1)

5 = 0101
5 >> 1
0010 (2)

в итоге, для того промежутка <число> >> 1 будет иметь такой результат :
0 0
1 0
2 1
3 1
4 2
5 2

похоже на итератор (--,++)

if (n) x += x; будет работать, пока n не дойдёт до нуля. т.к. перед этой проверкой стоит сдвиг вправо, то, можно сказать, цикл кончится (там break дальше, я не включил), когда n станет равным 0. т.е. на каждой итерации к строке добавления (строка результата - s) будет добавляться она же. что это значит?
посмотрим.
x = 'x';
n = 5;
s = '';

// I итерация, n = 5
n & 1 == 1 /*=>*/ s = s + x; // s = 'x'.
n = n >> 1; // n = 2
x = x+x; // 'xx';

// II, n = 2
n & 1 === 0;
n = n >> 1; // n = 1
x = x+x;// 'xx' + 'xx' => 'xxxx'

// III, n = 1
n & 1 /*=>*/ s = s+x; // 'x'+'xxxx' => 'xxxxx'
n = n >> 1 // n = 0
n == 0 /*=>*/ break

// res : 'xxxxx'.


Вывод :

обычный цикл для повторения строки, но оптимизированный :
  1. заменой всех операций с числами на побитовые (переход от десятичной системе к двоичной)
  2. уменьшением количества итераций в несколько раз

nerv_ 23.12.2011 10:53

melky, спасибо за тест. Проверял в FF 8.0.1, IE8, да, разница действительно, около 2х. В Opera 10.62 результат обратный, т.е. 1-ый способ быстрее второго, но уже на в два раза.

melky 23.12.2011 10:57

Цитата:

Сообщение от nerv_ (Сообщение 145456)
melky, спасибо за тест. Проверял в FF 8.0.1, IE8, да, разница действительно, около 2х. В Opera 10.62 результат обратный, т.е. 1-ый способ быстрее второго, но уже на в два раза.

после того, как я понял, как работает код, выяснилось, что те два кода на jsperf неэквивалентны.

вот сейчас совсем другое дело.


Часовой пояс GMT +3, время: 16:38.