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

Игры с 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

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