Оптимизация JavaScript в 10-20 раз, фантастика? А вот нет!!
 

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

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

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

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

Попробую коротко изложить суть, мы хотим в памяти отложить например 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 милисекунд против всего четырех!, кому интересно на их сайте выложен микро скрипт

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

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

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

суть укладывается в 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 будет возвращать 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. но что это значит ? возьму тот же промежуток.
если мы сделаем 2 >> 1, то сдвинем биты в числе 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. уменьшением количества итераций в несколько раз

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

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

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

Особое спасибо за вот этот момент.

я опустил такие уточнения, вроде "Boolean(1) будет true". надеюсь, всем будет понятно то, что я описал.

PS. кстати, имя темы говорит об увеличении производительности в 20 раз, а на практике коэффициент меняется от 1.82 (FF) до 2.5 (CH)

melky, жаль не могу плюсануть рейтиг за столь исчерпывающий пост, форум не позволяет. Хотел бы кое-что добавить по сдвигам.

alert(16 >> 1); // 16 / 2
alert(16 << 1); // 16 * 2

Насколько мне известно, побитовые сдвиги - одни из самых быстрых операций в компутере ;)
Да эт сразу понятно было, что утка.

Что? a >> i — деление a на 2^i с отбрасыванием остатка же.

Да наверно перегнул, посмотрев на их результаты, но в любом случаем чем больше данных обрабатываем тем больше и прирост

melky, что ж вы как декремент обидели. Он может быть в 2-2.5 раза быстрее.

function stringFill2(x, n){ 
	var s = x, needLength = x.length * n;
	while(s.length < needLength)
		s += s;
	return s.substr(0,needLength);
}

Хотя это уже и не декремет вовсе получается, блин...
Но этот способ не так сильно отстаёт от побитового.

В продолжении темы
Думаю, в данном случае, это можно обозвать как "проверка бит по маске", хотя чаще используют их сброс или установку. Не самый удачный пример, но тем не менее :)

// Преобразование строки (lat.) в верхний регистр с помощью побитового оператора и (&), т.е. сброс бит по маске
// ----------------------
// имеем символ "a", код:  01100001 (97)
// сброс бит по маске:     11011111 (223)
// итог - символ "A", код: 01000001 (65)
// ----------------------
var x = prompt("Введите тект английскими буквами в нижнем регистре", "melky")
for(var j = [], i = 0; i < x.length; i++) {
	j[i] = x.charAt(i).charCodeAt(); // получить символ и его код
	j[i] &= 223; // сброс бит по маске 11011111 (двоичное представление числа 223)
	j[i] = String.fromCharCode(j[i]); // получить символ из таблицы Unicode-символов
}
alert(j.join(""));

ключевые слова похоже и итератор :)
спасибо. не знал!

А есть ли возможность перевести поиск по тексту на такой принцип? и будет ли он эффективнее регулярных выражений?

Посимвольным считыванием потока данных занимаются конечные автоматы