Наверняка у многих из вас перед глазами уже мелькали заголовки статей с конкурсом от Hola, который недавно подошел к своему логическому завершению. В окончательных результатах мне посчастливилось быть на 3 месте. По этой причине я позволил себе поделиться описанием своего решения, а также того, как я до него докатился.
1. Чем я хуже?
Самое первое решение, естественно, «в лоб». Формируем для каждого правила пару регулярных выражений, а затем запускаем цикл по сообщениям с вложенным циклом по правилам. Код до безобразия прост (и, как мы уже знаем, легко умещается в это пугающее число 666 байт), так что приводить его здесь не вижу смысла.
2. Да здравствуют динамические функции!
Следующим шагом я решил развернуть внутренний цикл. Для этого предварительно на основании правил динамически формируем функцию getActions(from, to) и вызываем её в цикле для каждого сообщения. Фильтр приобретает примерно следующий вид:
function filter(messages, rules) {
// Собираем функцию
var builder = [];
builder.push('var actions = [];');
for ( var i = 0; i < rules.length; i++ ) {
var rxFrom = createRegex(rules[i].from);
if ( rxFrom ) builder.push(escapeRegex(rxFrom), '.test(from) && ');
var rxTo = createRegex(rules[i].to);
if ( rxTo ) builder.push(escapeRegex(rxTo), '.test(to) && ');
builder.push('actions.push('', escapeString(rules[i].action), '');');
}
builder.push('return actions;');
var getActions = new Function('from, to', builder.join(''));
// Обрабатываем сообщения
var result = {};
for ( var key in messages ) {
var message = messages[key];
result[key] = getActions(message.from, message.to);
}
return result;
}
А ниже приведен пример сформированной функции getActions:
function getActions(from, to) {
var actions = [];
/.*@work.com/.test(from) && actions.push('tag work');
/.*@spam.com/.test(from) && actions.push('tag spam');
/jack@example.com/.test(from) && /jill@example.org/test(to) && actions.push('folder jack');
/jill@example.com/.test(to) && actions.push('forward to jill@elsewhere.com');
return actions;
}
Плюсом данного подхода также является то, что внутри функции мы вольны предварительно запрограммировать любые условия, необходимые для того или иного правила. Конкретно в выше приведенном примере, если в правиле не задано свойство from или to, то и нет необходимости добавлять в тело функции проверку соответствующего свойства сообщения для данного правила. А если в правиле не задано ни одно из этих свойств, то указанное в правиле действие просто запишется в результирующий массив безо всяких проверок.
При использовании же обычного вложенного цикла для достижения подобного поведения пришлось бы вставлять дополнительные проверки в тело цикла, вычисляемые на каждой итерации, что, конечно же, накладывает дополнительные расходы.
3. Сам, всё сам!
Далее я всё же сподобился уйти от регулярных выражений и написал функцию match(value, pattern), которая определяет, соответствует ли адрес заданному шаблону или нет, возвращая соответственно true или false. Изначально функция у меня оперировала символами/строками, но такой подход оказался не очень эффективным, поэтому оперировать она стала в основном ASCII-кодами, которые получаются через String.charCodeAt(index) (была также попытка использовать String.codePointAt(index), но она не оправдала себя по эффективности). Функция громоздкая и не особо интересная, поэтому приводить её здесь я не буду.
Чтобы вызывать функцию match из getActions, я передавал её дополнительным параметром после from и to.
4. Извините, Вы нам точно не подходите
В поисках способа дальнейшего увеличения производительности я решил, что собственная функция — это, конечно, здорово, но всё же следует её вызывать пореже, и опять сфокусировался на getActions. Собственно, на данном этапе задача стояла в том, чтобы на основании каких-то признаков заведомо исключить часть правил и не вызывать для них ресурсоёмкую функцию, при чём определение этих признаков само по себе тоже не должно занимать много времени.
Одним из таких признаков стал просто первый символ шаблона. Использовать его можно только в том случае, если он не был символом "?" или "*". Второй признак, длину, можно было использовать, когда в шаблоне нет символа "*" (на тот момент до меня ещё не дошла мысль, что можно проверять и минимальную длину адреса).
Чтобы при проверке каждого правила не вызывать кучу методов в свойствах from и to обрабатываемого сообщения, в начале функции getActions рассчитываем дополнительные переменные и используем их по мере необходимости:
function getActions(from, to, match) {
var actions = [];
var fb = from.charCodeAt(0), fb61 = fb == 0x61, fb74 == 0x74 /*, ... */;
var tb = to.charCodeAt(0), tb66 = tb === 0x66 /*, ... */;
var fl = from.length, fl14 = fl == 14, fl15 = fl == 15 /*, ... */;
var tl = to.length, tl16 = tl == 16 /*, ... */;
fb61 && tb66 && fl15 && tl16 && match(from, 'abc@example.com') && match(to, 'fake@example.com') && actions.push('action 1');
fb74 && fl14 && match(from, 'test@gmail.com') && match(to, '*@any.net') && actions.push('action 2');
// ...
return actions;
}
Это изменение дало заметный рост производительности. Но можно заметить, что в любом шаблоне, начинающемся с символа "*" невозможно ориентироваться ни по первому символу, ни по длине. А такие шаблоны однозначно должны были встречаться.
5. И ещё несколько вопросов
Поэтому следующим шагом я решил попробовать классифицировать шаблоны ещё и по доменам. Так как в любом месте домена также может встретиться "*", то я решил, что буду брать из него максимально возможный уровень домена вплоть до 3-го. Соответственно, в начале функции getActions необходимо из свойств сообщения from и to выделить домены 1, 2 и 3 уровня и сформировать большую пачку переменных, сигнализирующих о принадлежности адреса сообщения к тому или иному домену.
Насколько сейчас могу вспомнить, метод не то, чтобы совсем нерабочий, но при разных тестовых данных, он себя проявлял по-разному. Вычленение доменов из адресов и предварительный расчет переменных на каждой итерации съедали много времени. Тут я попробовал много разных вариантов. Например, группировал редко встречающие домены, чтобы уменьшить количество вычисляемых переменных вначале (кстати, с первыми символами и длинами я тоже проводил подобные группировки), пытался вычислять хэш доменов и сравнивать его. Но по итогу от сравнения доменов я всё-таки отказался.
6. Где-то неподалеку
Между тем, в голове все витала мысль, а не попробовать ли построить единое дерево от начала (а потом и от конца) шаблонов до первого символа "*", и засунуть в его листья списки правил, которые и надо проверять? То ли мне просто не очень нравился этот метод, и я подсознательно строил его неэффективно, то ли оно действительно так долго строится, но уже после первых экспериментов я решил, что создание этой структуры — довольно медленная штука, и я не хочу с ней возиться.
7. Зачем изобретать велосипед?
Я вернулся к предыдущему варианту, но вместо классификации по доменам я просто добавил ещё и проверку последнего символа шаблона.
Вроде всё хорошо, но не очень. Теперь получается, что при проверке каждого правила до вызова функций match могло проверяться до 6 переменных (а изначально я ведь хотел уменьшить количество проверок), да ещё и просчитывать их все надо для каждого сообщения. Мне это не нравилось. К тому же, экспериментируя с количеством проверок для каждого правила и их последовательностью, я пришёл к выводу, что при такой длинной проверке от трёх признаков пользы не намного больше, чем от двух. Отсюда следующий шаг.
8. В тесноте, да не в обиде
Я решил, что сравнение длин адресов и шаблонов — самый бесполезный признак, и исключил из исключающих правила признаков. Остались только проверки соответствия первого и последнего символов. Из условий конкурса помним, что в строках могут быть только символы с кодами в диапазоне от 0x20 до 0x7F, а значит, все первые и последние символы шаблонов можно легко уместить в одну переменную типа Integer и для каждого правила производить только одно сравнение перед вызовом match. Оставалась только проблема, что у некоторых шаблонов в начале или конце могли быть символы "?" и "*", которые участвовать в сравнении не должны. Но эта проблема легко решается, если перед сравнением значений наложить на них маску, обнуляющую лишние октеты. Получаем примерно следующее:
function getActions(from, to, match) {
var actions = [];
var hash = (from.charCodeAt(from.length-1)<<24) | (from.charCodeAt(0)<<16) | (to.charCodeAt(to.length-1)<<8) | to.charCodeAt(0);
(hash & 0xFFFFFFFF) == 0x6D616D66 && match(from, 'abc@example.com') && match(to, 'fake@example.com') && actions.push('action 1');
(hash & 0xFFFFFF00) == 0x6D747400 && match(from, 'test@gmail.com') && match(to, '*@any.net') && actions.push('action 2');
// ...
return actions;
}
Ну и конечно, наложение масок на хэш тоже логично предварительно рассчитать в переменные (их никак не может быть больше 16-ти) в начале функции, чтобы не выполнять эту операцию для каждого правила.
9. Разделяй и властвуй!
Функция match работала достаточно хорошо, но она была универсальна для всех шаблонов, и в этом был её недостаток. Для шаблонов, не содержащих символа "*" было не обязательно проходить все эти дополнительные процедуры, а достаточно только посимвольно сравнить две строки с учетом особенностей символа "?" в шаблоне. То же касалось шаблонов, содержащих только один символ "*". В этом случае логично проверять участки шаблона до "*" и после.
В итоге, вместо одной функции match их появляется пять:
- m1(value, pattern) — сравнение, если символа "*" в шаблоне нет.
- m2(value, pattern) — сравнение, если символов "*" много.
- m3(value, pattern, bl, el) — если один символ "*" в середине шаблона, то анализ bl символов в начале строки и el в конце.
- m4(value, pattern, bl) — если один символ "*" в конце шаблона, то анализ bl символов в начале.
- m5(value, pattern, el) — если один символ "*" в начале шаблона, то анализ el символов в конце.
Кроме того, в эти функции шаблон я передаю уже в виде массива с кодами символов, а не как строку (чтобы лишний раз не дёргать метод String.charCodeAt(index), на самом деле, не знаю, принесло ли это пользу).
Соответственно, в функцию getActions в процессе её формирования подставляются вызовы нужных функций (которые всё так же передаются через дополнительные параметры). В этот же момент из шаблонов удаляются подряд идущие символы "*", так как на результат это влияния не оказывает, а на выбор функции сравнения ещё как. (В конечном варианте решения реализация этого процесса находится внутри функции createPatternMatchFunc.)
10. Только тссс...
Есть в данном решении одно слабое место. В худшем случае, если вдруг все шаблоны начинаются с одного и того же символа, да ещё и заканчиваются одним и тем же символом, то у всех них хэш будет одинаковый и функции проверки шаблонов внутри getActions будут вызываться абсолютно для всех правил (если адреса в сообщении, конечно, подходят).
В таком случае логично было бы сравнивать не первые, а вторые или третьи символы с начала и конца шаблона (при условии, что до них не было "*"). Но как определить, какой вариант наиболее оптимален?
Я пошёл по следующему пути:
- Для первых и последних трёх позиций шаблонов посчитал частоты появления тех или иных кодов символов;
- Для каждой позиции вычислил среднеквадратическое отклонение этих частот;
- Выбрал в начале и конце позиции с минимальным среднеквадратическим отклонением (но не те, в которых встречается только один код символа).
В принципе, всё это работало, но процесс формирования функции getActions замедлился, что сказалось на общей скорости работы фильтра. К тому же, мне не давала покоя мысль, что у позиции с двумя вариантами кодов с равными частотами и у позиции с восемью вариантами кодов с равными частотами одинаковые среднеквадратические отклонения, хотя логически ясно, что второй вариант более уместный для использования. Учитывая небольшой провал производительности, пытаться всё это балансировать я не стал, а просто вернулся к анализу первого и последнего символов (нам ведь обещали реальные данные).
11. Практическая магия и не только
- В ходе экспериментов выяснилось, что у строки лучше сначала читать свойство length в переменную, а последующие манипуляции проводить с этой переменной. Даже если она используется один раз. Так быстрее.
- Объявлять несколько переменных подряд быстрее с одним var через запятую, чем с несколькими через точку с запятой.
- Передача функций сравнения через параметры функции getActions медленнее, чем помещение их в global и вызов оттуда.
- Менять исходный объект messages эффективней, чем создавать новый объект результатов.
- Безразлично, ставить ли везде == или === .
На этом этапе решение и было отправлено на проверку.
12. Из несбывшегося
Для тестирования производительности своего решения я подготовил тестовые данные, в которые входило 600000 сообщений и 1000 правил. Причём среди сообщений не было ни одного с парой повторяющихся адресов. Наверное, поэтому мне как-то и в голову не приходила мысль про кэширование результатов.
Добавив кэширование результата getActions, с данными, используемыми в конкурсе, на своей машине я получил прирост производительности на 15% для large-данных и на 2% для xlarge-данных (на моих данных производительность деградировала на 13%). То есть при отправке решения в таком виде, вероятно, в итоговой таблице мой результат составлял бы около 248 и 2303 мс вместо 292 и 2351 мс соответственно, а статья называлась бы «2 место за 12 шагов». Но, увы и ах!
Спасибо организаторам, жду новых конкурсов!
Автор: XMypuK
