Заметки идущего Технические заметки по веб-технологиям

Игры с JavaScript

TL;DR Не работайте в глобальном окружении.

Задача #

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

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

Первое что пришло в голову это шесть вложенных друг в друга циклов, внутри последнего проверяется условие и при его выполнении увеличивается счетчик. Достаточно просто.

Язык - JavaScript, платформа FF4 + Firebug.

var title = "Без оптимизации";
console.time(title);

var s = -1;
for (var i1 = 0; i1 < 10; i1++)
for (var i2 = 0; i2 < 10; i2++)
for (var i3 = 0; i3 < 10; i3++)
for (var i4 = 0; i4 < 10; i4++)
for (var i5 = 0; i5 < 10; i5++)
for (var i6 = 0; i6 < 10; i6++)
if (i1 + i2 + i3 == i4 + i5 + i6) {
s++;
}
console.log(s, 1e6 / s, (s / 1e6) * 100 + "%");

console.timeEnd(title);
// Выполняется 2400 мс

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

И вот такая история получилась: #

Сначала я вынес var в начало и переделал цикл for на while #

var title = "Заменил for на while";
console.time(title);
var s = 0,
i1 = 0,
i2 = 0,
i3 = 0,
i4 = 0,
i5 = 0,
i6 = 0;

while (i1++ < 10) {
while (i2++ < 10) {
while (i3++ < 10) {
while (i4++ < 10) {
while (i5++ < 10) {
while (i6++ < 10) {
if (i1 + i2 + i3 == i4 + i5 + i6) {
s++;
}
}
i6 = 0;
}
i5 = 0;
}
i4 = 0;
}
i3 = 0;
}
i2 = 0;
}

if (s != 55252) {
console.error("Неправильно посчиталось");
} else {
console.log(s, 1e6 / s, (s / 1e6) * 100 + "%");
}

console.timeEnd(title);
// 2150

Это дало 11% прироста производительности. Скрипт выполняется чуть больше двух секунд - 2150 мс. Уже неплохо, поехали дальше.

Ввел кеширование промежуточных сумм #

Чтобы в последнем цикле (а он выполняется миллион раз) исключить одни и те же арифметические операции.

var title = "Ввел кеширование";
console.time(title);

var s = 0,
i1 = 0,
i2 = 0,
i3 = 0,
i4 = 0,
i5 = 0,
i6 = 0;
var s2 = 0,
s3 = 0,
s5 = 0; // Кеш

while (i1++ < 10) {
while (i2++ < 10) {
s2 = i1 + i2; // Кеш суммы первых двух цифр
while (i3++ < 10) {
s3 = s2 + i3; // Сумма первых трех цифр
while (i4++ < 10) {
while (i5++ < 10) {
s5 = i4 + i5; // Кеш суммы четрвертой и пятой цифры
while (i6++ < 10) {
if (s3 === s5 + i6) {
s++;
}
}
i6 = 0;
}
i5 = 0;
}
i4 = 0;
}
i3 = 0;
}
i2 = 0;
}

if (s != 55252) {
console.error("Неправильно посчиталось");
} else {
console.log(s, 1e6 / s, (s / 1e6) * 100 + "%");
}

console.timeEnd(title);
// 1300

1300 мс!! Вау, почти в два раза. Мы на правильном пути.

Добавил условие в предпоследний цикл #

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

var title = "Ввел пропуск заведомо несчастливых билетов";
console.time(title);

var s = 0,
i1 = 0,
i2 = 0,
i3 = 0,
i4 = 0,
i5 = 0,
i6 = 0;
var s2 = 0,
s3 = 0,
s5 = 0; // Кеш

while (i1++ < 10) {
while (i2++ < 10) {
s2 = i1 + i2; // Кеш суммы первых двух цифр
while (i3++ < 10) {
s3 = s2 + i3; // Сумма первых трех цифр
while (i4++ < 10) {
while (i5++ < 10) {
s5 = i4 + i5; // Кеш суммы четрвертой и пятой цифры
if (s3 >= s5) {
while (i6++ < 10) {
if (s3 === s5 + i6) {
s++;
}
}
i6 = 0;
}
}
i5 = 0;
}
i4 = 0;
}
i3 = 0;
}
i2 = 0;
}

if (s != 55252) {
console.error("Неправильно посчиталось");
} else {
console.log(s, 1e6 / s, (s / 1e6) * 100 + "%");
}

console.timeEnd(title);
// 1150

Вынес функцию. #

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

var title = "Вынес расчет последних 3 цифр в функцию";
console.time(title);

var s = 0, i1 = 0, i2 = 0, i3 = 0;
var s2 = 0, s3 = 0; // Кеш

function CalcLast3Digits(s3) {
var i4 = 0, i5 = 0, i6 = 0;
var s5 = 0;
while (i4++ < 10) {
while (i5++ < 10) {
s5 = i4 + i5; // Кеш суммы четрвертой и пятой цифры
if (s3 >= s5) {
while (i6++ < 10) {
if (s3 === s5 + i6) {
s++;
}
}
i6 = 0;
}
}
i5 = 0;
}
}

while (i1++ < 10) {
while (i2++ < 10) {
s2 = i1 + i2;
while (i3++ < 10) {
s3 = s2 + i3;
CalcLast3Digits(s3); // Вот тут
}
i3 = 0;
}
i2 = 0;
}

if (s != 55252) {
console.error("Неправильно посчиталось");
} else {
console.log(s, 1e6 / s, (s / 1e6) * 100 + "%");
}

console.timeEnd(title);
// 34 мс

34 мс. Ээээ...не понял, еще раз. 34 мс. Результат тот же. Что произошло я сразу не понял.

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

Обернуть функцией #

Так, а если попробовать вообще все завернуть в одну анонимную функцию?

var title = "Переделал все в анонимную функцию";
console.time(title);
(function () {
var s = 0, i1 = 0, i2 = 0, i3 = 0, i4 = 0, i5 = 0, i6 = 0;

var s2 = 0, s3 = 0, s5 = 0;

while (i1++ < 10) {
while (i2++ < 10) {
s2 = i1 + i2;
while (i3++ < 10) {
s3 = s2 + i3;
while (i4++ < 10) {
while (i5++ < 10) {
s5 = i4 + i5; // Кеш суммы четрвертой и пятой цифры
if (s3 >= s5) {
while (i6++ < 10) {
if (s3 === s5 + i6) {
s++;
}
}
i6 = 0;
}
}
i5 = 0;
}
}
i3 = 0;
}
i2 = 0;
}

if (s != 55252) {
console.error("Неправильно посчиталось");
} else {
console.log(s, 1e6 / s, (s / 1e6) * 100 + "%");
}
})();

console.timeEnd(title);
// 8 мс

8 мс. Ожидаемо. В принципе это почти мгновенно, вряд ли можно еще ускорить, да и незачем.

Возвращаемся к началу #

Чисто ради интереса, а что будет если наш самый первый, простой и жутко тормозной вариант просто обернуть функцией?

var title = "Неоптимизированный код в анонимной функции";
console.time(title);

(function () {
var s = -1;
for (var i1 = 0; i1 < 10; i1++)
for (var i2 = 0; i2 < 10; i2++)
for (var i3 = 0; i3 < 10; i3++)
for (var i4 = 0; i4 < 10; i4++)
for (var i5 = 0; i5 < 10; i5++)
for (var i6 = 0; i6 < 10; i6++)
if (i1 + i2 + i3 == i4 + i5 + i6) {
s++;
}
console.log(s, 1e6 / s, (s / 1e6) * 100 + "%");
})();

console.timeEnd(title);
// 14 мс

14 мс. Ндаа.. Спрашивается, зачем все остальная оптимизации?

Вывод #

Вывод из всего этого (очевидно для опытного, но новичкам будет полезно):

  1. Старайтесь не работать в глобальном контексте без крайней необходимости;
  2. Смысла экономить на мелкой оптимизации для редко используемого кода нет. Но имеет смысл, если операция повторяется много раз;
  3. Прерывайте выполнение потока программы, если результат все равно однозначен;
  4. Используйте кеширование.

P.S. нашел пару страничек с решениями задачи:

  1. http://habrahabr.ru/blogs/zadachki/42682/
  2. http://www.ega-math.narod.ru/Quant/Tickets.htm

Статьи на тему: