8 апреля 2011 г.

Игры с JavaScript

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

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

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

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



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

И вот такая история получилась:
1. Сначала я вынес var в начало и переделал цикл for на while:

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

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

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

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


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

34 мс. Ээээ...не понял, еще раз. 34 мс. Результат тот же. Что произошло я сразу не понял. Оказывается доступ к глобальным переменным горазда дороже с точки зрения производительности, чем к локальным.

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

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

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

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

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

P.S. нашел пару стриничек с решениями задачи:
1. http://habrahabr.ru/blogs/zadachki/42682/
2. http://www.ega-math.narod.ru/Quant/Tickets.htm

Комментариев нет:

Отправить комментарий