Резюме

Привет!

Во-первых, я поздравляю команду Авито с супер-заданием. Вам удалось найти объем работ и сформулировать требования к нему так, что про конкретного разработчика становится видно все. На ум приходит байка про Петра I - "...чтобы дурь каждого видна была".

Во-вторых, вы наверное знаете, что ваша задача является публичной, вот статья на Хабре, поэтому замечательный файл "pg" весом более 300 Mb выступил главным объектом тестирования.

В-третьих, мои результаты плачевные, несмотря на то, что я "упоролся" с вашей задачей. А именно:

1. мое однопоточное решение близко не дотягивает до секунды на обработку файла "pg";
2. я не могу предложить многопоточное решение, которое было бы более эффективным, чем однопоточное;
3. поскольку я нашел себя в таком затруднительном положении, я обратился к старшим товарищам, а именно к Илье Шишкову, который очень любезно выделил время посмотреть на мои идеи. Илья предложил еще одну ветку по подсчету, которая работает быстрее однопоточного решения.

Детали

Сборка-Запуск

1. С++20;
2. Можно запустить сразу тесты, в этот репо вложен один тестовый файл, выполняющий end to end тестирование, где в качестве входного файла используется "pg" - см следующий пункт;
3. Замечательный файл "pg" не заливается на гитхаб ввиду своего веса, его нужно руками положить в test_data/inputs каталог проекта чтобы запускать код через тесты. Коллега, который опубликовал вышеупомянутую статью, также выложил ссылку на этот файл, по которой его можно скачать;
4. Нужно выбрать define-ы в файле code_branch_selector.h, без явного указания опции код работать не будет, по умолчанию выбрано однопоточное решение (ST):
   • ST //однопоточное решение, бор на массиве;
   • MT_CONCURRENT_MAP //многопоточное решение на concurrent map;
   • MT_TRIE //многопоточное решение на боре, если выбрана эта опция, то обязательно указать одну из двух последующих;
     • TRIE_ON_VECTOR //шардированный многопоточный бор на массивах;
     • TRIE_ON_ARENA //шардированный многопоточный бор, аллоцируемый на арене;
   • MT_SHISHKOV //многопоточная сортировка подсчетом, вариант решения, предложенный Ильей Шишковым.

Комментарии по идеям реализации

• Однопоточное решение - бор на массиве (app/data_structures/trie.hpp). Своя имплементации хеш-таблицы с открытой адресацией (app/data_structures/hash_table.hpp) проиграла замер;
• Многопоточное решение на конкурентной мапе - тривиально, app/multi_threading/ts_map.hpp;
• Многопоточное решение с использованием шардированного бора - идея состоит в том, чтобы шардировать бор по первому уровню переходов из корня. Каждый шард получает свой обработчик из пары очередь-выделенный поток, чтобы исключить гонку. Шардируем простой хеш-таблицей с идеальной хеш-функцией (app/data_structures/sharded_trie.hpp). Многопоточная очередь, обертка задачи в очередь - немного доработанный публичный код К.Владимирова. Это решение имеет две опции для шарда - вектор (app/data_structures/trie_vec.hpp) и арена (app/data_structures/trie_mem.hpp). Не могу не повториться - вся эта красота у меня не полетела, как говорят умные люди: "Усложнять - просто, попробуй упрости". Работает за >300 секунд на "pg";
• Многопоточное решение с сортировкой подсчетом (идея И.Шишкова) - для каждого блока буфера сразу посчитаем частотность слов после приведения к алфавиту из условия. Слить полученные результаты.