12.01.2016 11:58
tymofey 10 8100 Источник
В ноябре прошлого (уже) года, Hola объявила конкурс по программированию почтовых фильтров на js, и недавно опубликовала его результаты.

Я разделил второе место с Ильей Макаровым, и сейчас я расскажу…

Как это было


Решив принять участие в конурсе и задумавшись над поставленной задачей, я довольно быстро осознал, что заданные шаблоны email'ов могут быть преобразованы в регулярные выражения простой заменой '*' на '.*' и '?' на '.' и экранированием всех специальных символов. На этом можно было и успокоиться, как и поступил Надав Ивги, получивший специальный приз за самое короткое решение.

Но это решение обладает фатальным недостатком — сложностью O((кол-во правил)*(кол-во сообщений)), так как каждое сообщение нужно проверить на соответствие каждому правилу.

Есть лучший путь. Во первых, две регулярки для полей .from и .to, можно соединить в одну, отделив их друг от друга неиспользуемым символом (скажем '\x1F', так как по условию используются только символы от '\x20' до '\x7F' включительно), и то же самое проделывать с соответствующими полями сообщений:

     {from: 'john.doe@foo.org', to: '*@hola.*', action: 'act1'}
->
     {signature: 'alex@foo.org\x1F*@hola.*', action: 'act1'}

Это уменьшает количество необходимых тестов вдвое.

Во вторых, эти регулярки можно скомпилировать в один детерминированный конечный автомат (DFA), сложность работы которого не зависит от их колчества. Здесь стандартный RegExp нам уже не поможет.

Именно это и делала первая версия моего решения.

Успешно протестировав её на данных из задания я решил автоматизировать процесс и реализовал генератор исходных данных и сравнение результатов с reference implementation. Как оказалось не зря, в процедуре минимизации DFA обнаружился баг, и я временно исключил её из алгоритма (её наличие не влияет на корретность, только производительность).

Мой скрипт долбился в reference implementation с масимально возможно частотой, и через пару дней Hola ввели ограничение на частоту запросов. Хех. Я пожал плечами и ввел задержку между запросами. Тестирование стало проходить медленнее, но жить было можно.

Тут началась оптимизация. Первая идея состояла в компиляции DFA в огромный switch на js, как это делает lex и другие подобные инструменты.

Реализовав такой кодогенератор, я понял что не имею возможности оценить, улучшил ли я результат, и что для этого мне нужен куда более объемный набор тестовых данных. Я решил, что не смогу так просто сгенерировать датасет со вменяемыми статистическими характеристиками, и неплохо бы использовать реальный. Довольно быстро я нашёл Enron Email Dataset — email архив обанкротившейся компании с соответствующим названием. Пара скриптов на Python извлекли сообщения и сгенерировали из их адресов правила, и бенчмарк был готов.

Я запустил его и… подрвался на комбинаторной мине. Дело в том, что алгоритм построения DFA имеет экспоненциальную сложность (O(2^(кол-во состояний недетерминированного конечного автомата (NFA)))) и я недооценил насколько это ужасно. Я не мог дождаться конца завершения построения автомата для всего лишь двадцати правил. Вместо того чтобы решать эту алгоритмическую проблему, я потратил время на оптимизацию и без того высокопроизводительной части системы. Воистину, premature optimization is the root of all evil.

Ощутив просветление, первым делом я разделил .from и .to обратно, получив таким образом один автомат оперирующий только на .from для всех правил, и по одному автомату оперирующему на .to для каждой группы правил, .from которых приводят к одному и тому же конечному состоянию первого автомата:



Это уменьшило размеры каждого NFA как минимум вдвое, а значит и существенно уменьшился размеры соответствующих DFA. Производительность поднялась на порядок, теперь уже можно было дождаться построения автомата для сотни правил.

Но это всё равно было слишком долго. Пришло понимание, что нужно менять концепцию, а где-то через неделю пришло и озарение: не нужно строить весь детерминированный автомат сразу, можно строить его лениво, по одному состоянию за шаг. Реализация этой концепции меня сильно удивила: она была в несколько раз быстрее предудущей версии на тех же входных данных, более того, она могла без труда прожёвывать входные данные куда большей размерности. Видимо большая часть состояний полного DFA не посещаются. Я даже заново распарсил датасет Enron'а, чтобы извлечь больше данных.

Я решил, что это то, что мне нужно, и принялся за оптимизацию.

Оптимизация


Я попробовал несколько разных вещей, опишу те, что дали ощутимый результат.

Мемоизация


Не замерял, но имею основания полагать, что времени экономит больше всего остального. Используется в двух местах:

  • Ленивое построение DFA запоминает однажды пройденные состояния, а не создает из заново каждый проход.
  • Запоминается конечное состояние автомата для каждого email'а, тем самым избавляя от необходимости повторно проходить по графу DFA. Так как в типичном email архиве сообщений зачастую много больше чем адресов, между которыми они пересылаются, выгода существенна. В частности, это приводит к тому, что в результате filter сообщения, имеющие одинаковые массивы действией, на самом деле ссылаются на один и тот же объект массива. Массивы действий не заполняются заново для каждого нового сообщения.

Поиск состояния DFA соответствущего множеству состояний NFA


Потратил на это больше всего времени. Суть такова: нужно эффективное отображение из множества Object'ов (состояний NFA) в другой Object (соcтояние DFA). Так как в js нету нормальных хештаблиц c нестроковыми ключами, пришлось изворачиваться.

Сделал следующее: в каждое состояние NFA поместил уникальный инт .id при создании NFA (простым инкрементом). Имея множество таких состояний, кладу их .id в Buffer, сортирую, и интерпретирую как строковый ключ с помощью .toString().

Исспользование специфики структуры NFA


NFA, получающийся из шаблонов email'ов, имеет особенности:

  • Каждая вершина-состояние имеет не более двух исходящих дуг-переходов. Изначально это было реализовано в виде массивов для произвольного числа элементов. Когда я реализовал это в виде пар свойств время выполнения уменьшилось на 20%.
  • Во время создания, состояния NFA можно нумеровать (заполнять .id) таким образом, что построенные в дальнейшем множества оных будут уже отсортированы, убирая необходимость сортировки для построения строкового ключа (описано выше)

Минимизация частоты аллокаций памяти


  • При построении DFA постоянно создаются массивы состояний NFA, которые зачастую выкидываются после того, как по ним построен строковый ключ и найдено соответствующее состояние DFA (если не найдено, то создается новое, и массив становится его частью)
  • При построении строкового ключа буфер содержащий .id NFA состояний выкидывается вообще всегда.

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

Финальная оценка корректности


К этому моменту у меня заканчивались возможности для оптимизации, а полной уверенности в корректности решения не было. Чтобы исправить это досадное упущение, я написал ещё один скрипт на питоне, который медленно, за несколько дней, прогнал маленький кусочек датасета Enron'а (около 500 сообщений, для 1000 правил) через reference implementation. И, как оказалось, не зря. Получившиеся тестовые примеры выявили баг на edge-case'е, когда в шаблоне email'a две звездочки отделены друг от друга одним символом. Его было трудно найти но легко исправить.

Комментарий к методике оценки решений


Бенчмарк организаторов запускает тестируемые модули через модуль vm Node'a, вместо простого require. Что, как выяснилось, имеет неожиданные эффекты на производительности. Организаторы решили пересмотреть результаты.

Также я был удивлен относительно малой размерностью входных данных, которые были использованы для оценки решений. Финальную версию я гонял на 500000 сообщений и 1000 правил, и ожидал ещё больших размеров в бенчмарке организаторов. На таком датасете и с запуском через require тройка официальных лидеров показывает следующие результаты:

  • Юрий Килочек ~2300мс (я)
  • Дениса Крешихин ~2850мс
  • Илья Макаров ~7500мс

Для желающих, я выложил свое решение вместе с бенчмарками. Предлагаю в будущем, во избежание подобных недоразумений, усреднять результат по разным размерностям входных данных, или организовывать соревнования в разных 'весовых категориях'.

Комментарии (10)


  1. zBit
    12.01.2016 16:05
    #8735533
    +1

    Интересный подход.
    В моём бенчмарке с исходными данными от организаторов вы заняли 4-ое место (https://github.com/zbitname/hola_nodejs_challenge). Но при запуске от раза к разу, как выяснилось позже, места немного смещались. Я помню, что ваше решение в некоторых «раундах» на моих тестах было на 2-ом и 3-ом месте, но бывало и ниже.
    Тем не менее, получилось очень достойное по производительности решение, несмотря на нестабильность времени выполнения решений ваше держится в первой 10-ке стабильно, чаще даже в первой 5-ке. Хорошо, что вы решили написать об этом статью, т.к. пытаться понять суть того как работает алгоритм по коду у подавляющего большинства участников очень сложно, надо потратить много времени.

    организовывать соревнования в разных 'весовых категориях'.
    Вы тут имеете ввиду разный объём входных данных?


    1. tymofey
      12.01.2016 16:12
      #8735547

      Вы тут имеете ввиду разный объём входных данных?

      Именно. И неплохо было бы заранее их (объёмы) объявлять, вместе с остальными правилами конкурса.


      1. zBit
        12.01.2016 17:07
        #8735665

        Согласен, иначе игра в рулетку получается. И не пришлось бы подгонять тестовые данные под объём на котором у всех скрипт отработает и не свалится. И недовольных было бы меньше. А ещё лучше автоматизировать тестирование и выводить результаты онлайн, чтобы появилось больше мотивации соревноваться, как это было сделано с конкурсом по big data от mailru. Сделал скрипт — загрузил его на их сервак, узнал проходит ли тест на корректность твоё решение, сравнил свой результат с другими участниками. Это будет предварительная оценка. А в конце конкурса перед объявлением победителей сделать тоже самое, только ещё раз и с бОльшим количеством итераций и раундов, чтобы результаты были по-объективнее.

        В общем, для организаторов теперь есть куча идей по тому как сделать в следующий раз всё удобнее.


  1. OLS
    12.01.2016 16:37
    #8735615

    В ходе прочтения обсуждений тестовых наборов мне пришла в голову следующая формула выбора тестов:
    каждый участник, направивший свое решение, имеет право направить 1 или 2 теста. Тесты анонимизируются и размещаются в общем хранилище. Затем каждый участник имеет право проголосовать против, скажем, 50% тестов или против например 10. После голосования 25% тестов, набравшие самое большое количество голосов «против», удаляются из пула, а всем остальным присваиваются равные веса. С количественными параметрам схемы конечно можно «поиграть». Например, для ускорения тестирования наоборот оставить только 10% тестов, набравших меньше всего голосов «против».


  1. Methos
    12.01.2016 21:22
    #8736097
    +2

    Вам работу то предложили или нет?


    1. tymofey
      13.01.2016 14:17
      #8737341

      Нет)


      1. Methos
        14.01.2016 17:45
        #8738985

        Это намекает о том, что это голимый пиар Hola.


  1. xytop
    13.01.2016 11:03
    #8736831

    Я пробовал делать так:

    1. оптимизировал все фильтры, убирал повторяющиеся * и?
    2. затем делал граф/дерево как-то так:

    var graph = {};
function addFilterToGraph(pattern, action) {
    var g = graph;
    for(var i = 0; i < pattern.length; i++) {
        if( !g[ pattern[i] ] ) {
            g[ pattern[i] ] = { action: [] };
        }
        g = g[ pattern[i] ];
    }
    g[ 'action' ].push( action );
}


    Код неточный, пишу по памяти. Такое добавление проходило почти мгновенно.
    В конечных точках паттернов оседали actions.

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

    Теоретически это должно было сильно сократить количество проверок и ускорить алгоритм, так как мы не проверяем начальные символы паттернов снова а движемся в направлении листьев дерева/графа. Но сожалению это по какой-то причине работало в два раза медленнее решения с самописным match, который в итоге и послал на конкурс. На моих тестах этот match минимум в 3 раза по скорости опережал скомпилированный regex, я удивляюсь как здесь у некоторых ребят из конкурса регулярки оказываются быстрее моего решения…


    1. tymofey
      13.01.2016 14:45
      #8737403

      1) Убирать повторяющиеся '?' не корректно.
      2,3) Если я правильно понимаю, ваш is_match при встрече '*' начинает перебирать все комбинации суффиксов строки и паттерна и сопоставлять их, в структуру дерева же эта звёздочка не кодируется. У меня же звездочки закодированы в структуру дерева в виде реккурентных связей (так что это уже не дерево, а граф в общем виде) NFA. После детерминизации время прохода по DFA пропорционально длине строки и не зависит от наличия звездочек.


      1. xytop
        13.01.2016 17:57
        #8737727

        1) — да, с дуру так написал, не убирал их конечно.
        А по поводу is_match, да, много рекурсивных вызовов на один паттерн, зависит от его сложности. Мне кажется, это вариант NFA.
        Интересно увидеть графическую развертку DFA для для паттерна со звездочкой/ами. Там тоже должны быть циклы/рекурсии где-то внутри по идее.