В ожидании официальных результатов, неофициально протестировал двух лидеров на 300 сидах. Для [использующего рандом] решения 5991606f3cc1d6947da0b875 я сделал 2 прогона тестов, и по итогам первой сотни оно опередило конкурента (набравшего на одном из сидов 0 очков) в среднем на 570 очков (более 1%). Казалось бы, убедительное превосходство. Но на второй сотне превосходства уже не было: тут 5991606f3cc1d6947da0b875 на одном из сидов набирает 0 очков (как я говорил в одном из каментов выше, на некоторых сидах надолго залипать на месте нельзя), а 5995c8e13cc1d6947da0b89b в среднем набрало на этой сотне на 39 очков больше конкурента. На третьей сотне лидирующие решения ни на одном из сидов настолько явно не проваливаются, тем не менее разрыв между ними внезапно оказался наибольшим: 5995c8e13cc1d6947da0b89b набрало в среднем на 665 очков больше (чуть меньше 1.2% преимущества — если рассматривать в отрыве от остальных тестовых сотен, то тоже вроде бы «убедительно») и по сумме всех 300 сидов вышло вперед на 134 очка (менее 0.1% преимущества — явно меньше статистической погрешности). В общем, не только от сида к сиду, и не только от двадцатки сидов к двадцатке, но даже от сотни к сотне результаты очень сильно колеблются (даже сильнее, чем из-за рандома). Похоже, сиды, специфика которых выявляет слабые места того или иного из лидирующих решений, встречаются редко и разбросаны по тестовому набору слишком неравномерно (грубо говоря, если сиды какого-то типа встречаются в среднем раз в 100 случаев, то в одной сотне их может оказаться 2, а то и 3, а в каких-то других сотнях не оказаться вовсе, и если этот тип оказывается намного удобнее для одного из решений, то такое решение на конкретной сотне получает большое преимущество).
Кстати, сиды, на которых решения не могут позволить себе залипнуть на 600 ходов, всё же существуют (хотя встречаются редко и в тестовый набор не попали). Например, 1711738677 и 1907642739. Игроку там необязательно бежать с первого же хода, но и долго оставаться на месте тоже опасно.
Я потестил два лидирующих решения и хочу поделиться наблюдением, которое мне кажется важным с точки зрения определения победителя конкурса.
Я заметил два случайных фактора, которые оказывают очень большое влияние на результаты — достаточно большое, чтобы реальная средняя разница между двумя решениями просто «утонула» в нем.
Во-первых, насколько я понимаю, решение 5991606f3cc1d6947da0b875 использует рандом и поэтому его результаты весьма нестабильны.
Во-вторых, очень многое зависит от набора сидов. То есть не просто, как сказано в посте, «на некоторых уровнях лучший результат показывает одно из двух решений, на других — другое», но даже на целых двадцатках-тридцатках сидов то одно, то другое решение может существенно превзойти конкурента. Например, на первой двадцатке сидов решение 5991606f3cc1d6947da0b875 у меня превосходило конкурента в среднем примерно на 65 очков, но при расширении набора сидов до 50 картина менялась на противоположную: на дополнительных 30 сидах уже 5995c8e13cc1d6947da0b89b выигрывает в среднем 150 очков. При этом лучший за 10 тестов результат 5991606f3cc1d6947da0b875 на 30 дополнительных сидах превосходит его же худший результат на 261 очко! То есть по сути тестирование на 20-50 сидах оказывается в бОльшей степени «измерением везения», чем измерением реальной разницы между решениями. Поэтому мне кажется, что два лидирующих решения (если никто другой к ним не подберется на 50 сидах, но, по-моему, этого не должно случиться) стоит протестировать по крайней мере на нескольких сотнях сидов, чтобы влияние рандома и удачности того или иного набора сидов для конкретного решения перестали оказывать доминирующее влияние на результат и стала заметной реальная средняя разница между этими решениями. До четверга еще три дня и за это время, в принципе, можно и на тысяче сидов сравнить пару решений :)
Прежде всего, спасибо организаторам за интересный конкурс!
Мое последнее отправленное решение, к сожалению, даже не прошло тесты на корректность из-за незамеченного вовремя бага в коде, ответственном за мемоизацию (наложились друг на дружку три моих ошибки: одна пропущенная проверка в коде, из-за чего на определенных данных запоминались не те правила, которые следовало запомнить + слабое место в моих тестах на корректность, в которых отсутствовали те самые правила, на которых проявлял себя баг + отправка решения за 20 минут до дедлайна, когда уже не было времени перепроверить всё вдоль и поперек). Тем не менее, алгоритм получился не совсем уж провальным: на бенчмарке, предоставленном организаторами, мое решение примерно вдвое медленее победителя, а на моем бенчмарке, который меряет только время выполнения функции filter(...), алгоритм работает примерно в 1,5-2 раза быстрее решения победителя (на тех же тестовых данных, которые использовались организаторами). То есть сам алгоритм, в принципе, неплох, поэтому я рискну о нем рассказать.
Вместо регулярок я использовал дерево, в котором каждому узлу соответствует определенный символ из одного или нескольких [имеющих общее начало] фильтров. Дочерние элементы узлов хранятся в массивах, а код следующего символа в анализируемом адресе служит индексом в таком массиве, что позволяет находить подходящий следующий узел за минимальное время, а на сравнение адреса с большинством неподходящих фильтров время не тратится вовсе. Решение на основе дерева оказалось [на использованных мной тестовых наборах и на моем бенчмарке] примерно в 12-14 раз быстрее «тупого» решения с регулярками, а если вычесть «неизбежные» расходы, которые являются общими для обоих решений и считать только время сравнения строки с фильтрами, то прирост скорости достигал примерно 25 раз. Правда, я допускаю, что мое «тупое» решение с регэкспами тоже можно было бы оптимизировать и разрыв был бы меньшим, но все равно вариант с деревом, по-моему, намного быстрее. На тестовых данных организаторов + моем бенчмарке этот вариант (т.е. вообще без мемоизации) показывает примерно такое же время, как решение победителя. Но на бенчмарке организаторов он демонстрирует жуткий провал, несмотря на отсутствие сообщений «disabled optimization...», связанных с моими функциями. Поскольку в рамках этого конкурса я впервые попробовал поработать с Node.js, да и вообще с оптимизацией производительности кода на javascript, то подобная ситуация для меня пока является странной и непонятной.
Что касается мемоизации, то на нее у меня оставалось мало времени и некоторые идеи так и не были опробованы. Из того, что я попробовал, но мне не понравилось — запоминание списка правил для пары адресов from+to. На тех тестовых данных, которые я использовал для разработки, такая мемоизация показывала худшие результаты, чем раздельное сохранение списков подходящих правил для from- и to-адресов с последующим их пересечением. Возможно, я плохо продумал такой вариант мемоизации или просто тестовые данные были неподходящими для него, но в итоге я от этого отказался и сделал отдельную мемоизацию для каждого адреса, а не для пар адресов. Причем для мемоизации from и to я использовал разные подходы.
Тут стоит сделать шаг назад и рассмотреть способ формирования «финального результата». Перед разбором очередного «письма» я инициализировал буфер, в котором i-й байт соответствовал i-му правилу и мог иметь одно из 4 значений: 0 — это правило не подходит этому письму, 1 — правило подходит адресу from, но не to, 2 — наоборот, 3 — правило подходит обоим адресам и должно присутствовать в финальном результате. Во время обхода дерева, когда мы достигаем конца проверяемой строки (адреса), то берем хранящиеся в соответствующем узле дерева номера правил и увеличиваем значения соответствующих этим номерам байтов в буффере на 1 или 2 в зависимости от того, анализируем ли мы сейчас from- или to-адрес. Мы также обновляем «счетчик подходящих правил», когда очередной байт становится равным 3 (это нужно для последующей аллокации результирующего массива нужной длины). В самом начале анализа письма мы инициализируем все байты в буфере либо нолями, либо единичками (если правило имеет тривиальный from-паттерн (например, пропущенный), которому подходят любые from-адреса), либо двойками (если правило имеет тривиальный to-паттерн), либо тройками (если правилу подходят все письма). Затем этот буфер передается функции, которая сравнивает адрес to со всеми нетривиальными to-фильтрами (и увеличивает на 2 байты в буфере, соответствующие подошедшим фильтрам), затем то же самое проделывается с from-адресом и нетривиальными from-фильтрами, после чего у нас будет буфер, в котором все байты, соответствующие подошедшим правилам, будут равны 3. Дальше мы проходим по этому буферу от начала до конца и добавляем в результирующий массив все правила, для которых соответствующие байты равны 3.
Возвращаясь к мемоизации: при запоминании списка правил, подходящих to-адресу, я просто сохранял состояние буфера после сравнения адреса с нетривиальными to-паттернами. Для from-адресов такой подход не применим, т.к. они обрабатываются во вторую очередь и состояние буфера после их обработки зависит также от того, какой to-адрес анализировался перед этим. Поэтому для мемоизации from-правил приходилось отслеживать изменения в буфере (номера байтов, изменившихся при сравнении from-адреса с нетривиальными from-паттернами) и сохранять множество номеров изменившихся байтов. (В этом месте как раз и закрался ранее упомянутый баг — не влияющий на скорость, легко исправимый, но обнаруженный уже после дедлайна).
Поскольку мемоизация очень хороша для повторяющихся адресов, но предположительно очень плоха, например, для спама, то оставался вопрос «как нам по тестовым данным определить, включать для них мемоизацию или нет?». Довольно быстро пришло понимание того, что еще лучше не включать/выключать мемоизацию в целом, а делать ее выборочно: для одних адресов сохранять результаты их обработки, а для других — нет. С учетом нехватки времени, все сложные идеи отсеялись и осталась самая простая: почему бы не сохранять результаты обработки адресов, начиная, например, со второго или третьего их обнаружения? Тогда весь одноразовый спам пролетал бы мимо мемоизации и сопутствующих ей немалых расходов, а вся регулярная переписка быстро попадала бы в «кэш». Неэффективным такой подход был бы только на довольно специфических наборах данных (только спам, только повторяющаяся переписка, либо — самый неудобный случай — «все адреса встречаются по несколько раз, но не более того»), но нам-то обещали смесь спама с нормальной перепиской, а на таких данных выборочная мемоизация должна быть практически идеальной, не допуская провала ни на спам-подмножестве данных, ни на «нормальной переписке». Что и было зафиксировано при проверке производительности на разных наборах данных: на «максимально пригодных для мемоизации» результаты были почти на уровне «всегда включенной мемоизации», на «максимально непригодных» — ощутимо (на треть) уступали версии без мемоизации, но зато в разы превосходили версию с безусловной мемоизацией, а на смешанном наборе «спам + нормальная переписка» показали самый лучший результат из всех опробованных вариантов. Поэтому эта версия и была отправлена организаторам как финальная. К сожалению, с незамеченным багом :(
В общем, это было интересное интеллектуальное упражнение. Оно подтолкнуло к тому, чтобы наконец-то пощупать Node.js, лишний раз напомнило о том, как важно хорошо продуманное тестирование и почему не стоит затягивать работу до дедлайна :) А также поставило перед вопросом «почему один и тот же код на одних и тех же данных, но при другом бенчмарке показывает такой провал в производительности без очевидных [во всяком случае мне, неопытному в этом деле] проблем с деоптимизацией?», с которым я попробую на досуге разобраться.
p.s. Поскольку в комментариях подняли эту тему, то замечу, что на моем бенчмарке + тестовых данных от организаторов лучшим из призеров оказался Юрий Килочек (примерно на 17% обойдя официального победителя). Впрочем, мой алгоритм на моем бенчмарке еще в 1,5 раза быстрее. Впрочем, мне это уже не поможет. Впрочем, и Юрию, скорее всего, тоже :)
Правда, иногда он начинает перебрасывать на главную при попытке зайти на страницу выдачи, но это со временем проходит, потом опять начинается, потом опять проходит и так далее. В общем, если повезет и попадаете на удачный период, то можно уже поэкспериментировать с запросами.
Я заметил два случайных фактора, которые оказывают очень большое влияние на результаты — достаточно большое, чтобы реальная средняя разница между двумя решениями просто «утонула» в нем.
Во-первых, насколько я понимаю, решение 5991606f3cc1d6947da0b875 использует рандом и поэтому его результаты весьма нестабильны.
Во-вторых, очень многое зависит от набора сидов. То есть не просто, как сказано в посте, «на некоторых уровнях лучший результат показывает одно из двух решений, на других — другое», но даже на целых двадцатках-тридцатках сидов то одно, то другое решение может существенно превзойти конкурента. Например, на первой двадцатке сидов решение 5991606f3cc1d6947da0b875 у меня превосходило конкурента в среднем примерно на 65 очков, но при расширении набора сидов до 50 картина менялась на противоположную: на дополнительных 30 сидах уже 5995c8e13cc1d6947da0b89b выигрывает в среднем 150 очков. При этом лучший за 10 тестов результат 5991606f3cc1d6947da0b875 на 30 дополнительных сидах превосходит его же худший результат на 261 очко! То есть по сути тестирование на 20-50 сидах оказывается в бОльшей степени «измерением везения», чем измерением реальной разницы между решениями. Поэтому мне кажется, что два лидирующих решения (если никто другой к ним не подберется на 50 сидах, но, по-моему, этого не должно случиться) стоит протестировать по крайней мере на нескольких сотнях сидов, чтобы влияние рандома и удачности того или иного набора сидов для конкретного решения перестали оказывать доминирующее влияние на результат и стала заметной реальная средняя разница между этими решениями. До четверга еще три дня и за это время, в принципе, можно и на тысяче сидов сравнить пару решений :)
Мое последнее отправленное решение, к сожалению, даже не прошло тесты на корректность из-за незамеченного вовремя бага в коде, ответственном за мемоизацию (наложились друг на дружку три моих ошибки: одна пропущенная проверка в коде, из-за чего на определенных данных запоминались не те правила, которые следовало запомнить + слабое место в моих тестах на корректность, в которых отсутствовали те самые правила, на которых проявлял себя баг + отправка решения за 20 минут до дедлайна, когда уже не было времени перепроверить всё вдоль и поперек). Тем не менее, алгоритм получился не совсем уж провальным: на бенчмарке, предоставленном организаторами, мое решение примерно вдвое медленее победителя, а на моем бенчмарке, который меряет только время выполнения функции filter(...), алгоритм работает примерно в 1,5-2 раза быстрее решения победителя (на тех же тестовых данных, которые использовались организаторами). То есть сам алгоритм, в принципе, неплох, поэтому я рискну о нем рассказать.
Вместо регулярок я использовал дерево, в котором каждому узлу соответствует определенный символ из одного или нескольких [имеющих общее начало] фильтров. Дочерние элементы узлов хранятся в массивах, а код следующего символа в анализируемом адресе служит индексом в таком массиве, что позволяет находить подходящий следующий узел за минимальное время, а на сравнение адреса с большинством неподходящих фильтров время не тратится вовсе. Решение на основе дерева оказалось [на использованных мной тестовых наборах и на моем бенчмарке] примерно в 12-14 раз быстрее «тупого» решения с регулярками, а если вычесть «неизбежные» расходы, которые являются общими для обоих решений и считать только время сравнения строки с фильтрами, то прирост скорости достигал примерно 25 раз. Правда, я допускаю, что мое «тупое» решение с регэкспами тоже можно было бы оптимизировать и разрыв был бы меньшим, но все равно вариант с деревом, по-моему, намного быстрее. На тестовых данных организаторов + моем бенчмарке этот вариант (т.е. вообще без мемоизации) показывает примерно такое же время, как решение победителя. Но на бенчмарке организаторов он демонстрирует жуткий провал, несмотря на отсутствие сообщений «disabled optimization...», связанных с моими функциями. Поскольку в рамках этого конкурса я впервые попробовал поработать с Node.js, да и вообще с оптимизацией производительности кода на javascript, то подобная ситуация для меня пока является странной и непонятной.
Что касается мемоизации, то на нее у меня оставалось мало времени и некоторые идеи так и не были опробованы. Из того, что я попробовал, но мне не понравилось — запоминание списка правил для пары адресов from+to. На тех тестовых данных, которые я использовал для разработки, такая мемоизация показывала худшие результаты, чем раздельное сохранение списков подходящих правил для from- и to-адресов с последующим их пересечением. Возможно, я плохо продумал такой вариант мемоизации или просто тестовые данные были неподходящими для него, но в итоге я от этого отказался и сделал отдельную мемоизацию для каждого адреса, а не для пар адресов. Причем для мемоизации from и to я использовал разные подходы.
Тут стоит сделать шаг назад и рассмотреть способ формирования «финального результата». Перед разбором очередного «письма» я инициализировал буфер, в котором i-й байт соответствовал i-му правилу и мог иметь одно из 4 значений: 0 — это правило не подходит этому письму, 1 — правило подходит адресу from, но не to, 2 — наоборот, 3 — правило подходит обоим адресам и должно присутствовать в финальном результате. Во время обхода дерева, когда мы достигаем конца проверяемой строки (адреса), то берем хранящиеся в соответствующем узле дерева номера правил и увеличиваем значения соответствующих этим номерам байтов в буффере на 1 или 2 в зависимости от того, анализируем ли мы сейчас from- или to-адрес. Мы также обновляем «счетчик подходящих правил», когда очередной байт становится равным 3 (это нужно для последующей аллокации результирующего массива нужной длины). В самом начале анализа письма мы инициализируем все байты в буфере либо нолями, либо единичками (если правило имеет тривиальный from-паттерн (например, пропущенный), которому подходят любые from-адреса), либо двойками (если правило имеет тривиальный to-паттерн), либо тройками (если правилу подходят все письма). Затем этот буфер передается функции, которая сравнивает адрес to со всеми нетривиальными to-фильтрами (и увеличивает на 2 байты в буфере, соответствующие подошедшим фильтрам), затем то же самое проделывается с from-адресом и нетривиальными from-фильтрами, после чего у нас будет буфер, в котором все байты, соответствующие подошедшим правилам, будут равны 3. Дальше мы проходим по этому буферу от начала до конца и добавляем в результирующий массив все правила, для которых соответствующие байты равны 3.
Возвращаясь к мемоизации: при запоминании списка правил, подходящих to-адресу, я просто сохранял состояние буфера после сравнения адреса с нетривиальными to-паттернами. Для from-адресов такой подход не применим, т.к. они обрабатываются во вторую очередь и состояние буфера после их обработки зависит также от того, какой to-адрес анализировался перед этим. Поэтому для мемоизации from-правил приходилось отслеживать изменения в буфере (номера байтов, изменившихся при сравнении from-адреса с нетривиальными from-паттернами) и сохранять множество номеров изменившихся байтов. (В этом месте как раз и закрался ранее упомянутый баг — не влияющий на скорость, легко исправимый, но обнаруженный уже после дедлайна).
Поскольку мемоизация очень хороша для повторяющихся адресов, но предположительно очень плоха, например, для спама, то оставался вопрос «как нам по тестовым данным определить, включать для них мемоизацию или нет?». Довольно быстро пришло понимание того, что еще лучше не включать/выключать мемоизацию в целом, а делать ее выборочно: для одних адресов сохранять результаты их обработки, а для других — нет. С учетом нехватки времени, все сложные идеи отсеялись и осталась самая простая: почему бы не сохранять результаты обработки адресов, начиная, например, со второго или третьего их обнаружения? Тогда весь одноразовый спам пролетал бы мимо мемоизации и сопутствующих ей немалых расходов, а вся регулярная переписка быстро попадала бы в «кэш». Неэффективным такой подход был бы только на довольно специфических наборах данных (только спам, только повторяющаяся переписка, либо — самый неудобный случай — «все адреса встречаются по несколько раз, но не более того»), но нам-то обещали смесь спама с нормальной перепиской, а на таких данных выборочная мемоизация должна быть практически идеальной, не допуская провала ни на спам-подмножестве данных, ни на «нормальной переписке». Что и было зафиксировано при проверке производительности на разных наборах данных: на «максимально пригодных для мемоизации» результаты были почти на уровне «всегда включенной мемоизации», на «максимально непригодных» — ощутимо (на треть) уступали версии без мемоизации, но зато в разы превосходили версию с безусловной мемоизацией, а на смешанном наборе «спам + нормальная переписка» показали самый лучший результат из всех опробованных вариантов. Поэтому эта версия и была отправлена организаторам как финальная. К сожалению, с незамеченным багом :(
В общем, это было интересное интеллектуальное упражнение. Оно подтолкнуло к тому, чтобы наконец-то пощупать Node.js, лишний раз напомнило о том, как важно хорошо продуманное тестирование и почему не стоит затягивать работу до дедлайна :) А также поставило перед вопросом «почему один и тот же код на одних и тех же данных, но при другом бенчмарке показывает такой провал в производительности без очевидных [во всяком случае мне, неопытному в этом деле] проблем с деоптимизацией?», с которым я попробую на досуге разобраться.
p.s. Поскольку в комментариях подняли эту тему, то замечу, что на моем бенчмарке + тестовых данных от организаторов лучшим из призеров оказался Юрий Килочек (примерно на 17% обойдя официального победителя). Впрочем, мой алгоритм на моем бенчмарке еще в 1,5 раза быстрее. Впрочем, мне это уже не поможет. Впрочем, и Юрию, скорее всего, тоже :)
Например, www.wolframalpha.com/input/?i=weather+rome+madonna+date+of+birth — погода в Риме в день рождения Мадонны и сверху — работающая поисковая строка ;)
Правда, иногда он начинает перебрасывать на главную при попытке зайти на страницу выдачи, но это со временем проходит, потом опять начинается, потом опять проходит и так далее. В общем, если повезет и попадаете на удачный период, то можно уже поэкспериментировать с запросами.