3 місце за 11 кроків у конкурсі з JavaScript від Hola

Напевно у багатьох з вас перед очима вже мелькали заголовки статей з конкурсом від 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 будуть викликатися абсолютно для всіх правил (якщо адреси в повідомленні, звичайно, підходять).

У такому разі логічно було б порівнювати не перші, а другі або треті символи з початку і кінця шаблону (за умови, що до них не було ".*"). Але як визначити, який варіант найбільш оптимальний?

Я пішов по наступному шляху:

  1. Для перших і останніх трьох позицій шаблонів порахував частоти появи тих чи інших кодів символів;
  2. Для кожної позиції обчислив середньоквадратичне відхилення цих частот;
  3. Обрав на початку і наприкінці позиції з мінімальним середньоквадратичним відхиленням (але не ті, в яких зустрічається тільки один код символу).
В принципі, все це працювало, але процес формування функції getActions сповільнилося, що позначилося на загальній швидкості роботи фільтра. До того ж, мені не давала спокою думка, що у позиції з двома варіантами кодів з однаковими частотами і у позиції з вісьмома варіантами кодів з однаковими частотами однакові середньоквадратичне відхилення, хоча логічно ясно, що другий варіант більш доречний для використання. Враховуючи невеликий провал продуктивності, намагатися все це балансувати я не став, а просто повернувся до аналізу першого і останнього символів (адже нам обіцяли реальні дані).

11. Практична магія і не тільки
  • У ході експериментів з'ясувалося, що у рядки краще спочатку читати властивість length в змінну, а подальші маніпуляції проводити з цієї змінної. Навіть якщо вона використовується один раз. Так швидше.
  • Оголошувати декілька змінних поспіль швидше з одним var через кому, ніж з кількома через крапку з комою.
  • Передача функцій порівняння через параметри функції getActions повільніше, ніж приміщення їх в global і виклик звідти.
  • Змінювати вихідний об'єкт messages ефективніше, ніж створювати новий об'єкт результатів.
  • Байдуже, чи ставити скрізь == або === .
На цьому етапі рішення і було відправлено на перевірку.

12. З несбывшегося
Для тестування продуктивності свого рішення я підготував тестові дані, в які входило 600000 повідомлень і 1000 правил. Причому серед повідомлень не було ні одного з парою повторюваних адрес. Напевно, тому мені якось і в голову не приходила думка про кешування результатів.

Додавши кешування результату getActions, з даними, що використовуються в конкурсі, на своїй машині я отримав приріст продуктивності на 15% для large-даних і на 2% для xlarge-даних (на моїх даних продуктивність деградувала на 13%). Тобто при відправці рішення у такому вигляді, ймовірно, в підсумковій таблиці мій результат становив би близько 248 і 2303 мс замість 292 і 2351 мс відповідно, а стаття називалася б «2 місце за 12 кроків». Але, на жаль і ах!

Спасибі організаторам, чекаю нових конкурсів!

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.