Comments 19
Не могли бы вы привести пример вывода кода с trie? Интересно посмотреть как там время распределено между вводом, построением tire, рекурсивным обходом и сортировкой, а компилятора под рукой сейчас нет.
Тоже под руками нет. Насколько я помню на ввод 0.1 на сортировку порядка 0.01 и на вывод такого же порядка цифры
time (open files) = 1.66e-05
input size = 336183276 bytes
time (read input) = 0.114
time (make input lowercase) = 0.0347
trie size = 501266
time (count words) = 1.26
word count = 213637, length = 1883055
time (recover words from trie) = 0.0401
time (sort words) = 0.00766
time (write output) = 0.00605
time (total) = 1.46
А что насчет префиксного дерева с узлом не из одного символа а из нескольких? Количество случайных доступов к памяти должно уменьшиться пропорционально, процент cache miss'ов наверное вырастет, но думаю не на столько, насколько уменьшиться количество самих обращений, т.ч. в общем должен быть выигрыш.
Я пробовал это в каком-то виде. Называется path compression. Добавил массив, который "добивал" размер узла до целого количества кэш-линий. Ускорения не было. Для средней длины слова 4.25 это даже интуитивно кажется мне логичным.
Код с path compression.
Если исправить, то число узлов будет почти в два раза меньше, но выигрыша по времени относительно реализации без path compression все равное не получается — усложняется логика ветвления и видимо это все съедает.
Ради интереса попробовал на языке с GC (C#).
Код
using System.Collections.Concurrent;
using System.Diagnostics;
using System.Text;
var file = @"E:\Desktop\Media\pg.txt";
var sw = new Stopwatch();
sw.Start();
var word = new StringBuilder();
var freqDict = new ConcurrentDictionary<string, int>(1, 1500000);
char[] block = new char[1024 * 1024 * 1024];
int count;
char sym;
using (var stream = new FileStream(file, FileMode.Open, FileAccess.Read, FileShare.None, 1024 * 1024 * 64))
{
using (TextReader reader = new StreamReader(stream))
{
while ((count = reader.ReadBlock(block, 0, block.Length)) > 0)
{
for (int i = 0; i < count; i++)
{
sym = char.ToLowerInvariant(block[i]);
if (sym >= 'a' && sym <= 'z')
{
word.Append((char)sym);
}
else if (word.Length > 0)
{
freqDict.AddOrUpdate(word.ToString(), 1, (_, o) => o + 1);
word.Clear();
}
}
}
}
}
sw.Stop();
Console.WriteLine($"{freqDict.Count} words. {sw.ElapsedMilliseconds} ms");
var max = freqDict.OrderByDescending(x => x.Value).Take(25);
Console.WriteLine($"Max\r\n{string.Join("\r\n", max.Select(m => $"{m.Key} = {m.Value}"))}");Результат работы
Результат
213637 words. 5510 ms
Max
the = 3343241
and = 1852717
of = 1715705
to = 1560152
a = 1324244
in = 956926
i = 933954
he = 781286
that = 713514
was = 690876
it = 665710
you = 608451
his = 580460
with = 498427
for = 442288
had = 433687
as = 426356
her = 415101
she = 371545
is = 370831
at = 362783
s = 358148
not = 346718
but = 338402
on = 338295То есть наивное решение на .net 6 и C++ по скорости практически идентичны.
Мне кажется, это не совсем корректное сравнение, проблема кроется в .Take(25)
Из документации MSDN про OrderByDescending: "This method is implemented by using deferred execution. The immediate return value is an object that stores all the information that is required to perform the action. The query represented by this method is not executed until the object is enumerated either by calling its GetEnumerator method directly or by using foreach in Visual C# or For Each in Visual Basic."
В случае применения .Take(25) достаточно будет найти 25 максимальных элементов, что совершенно неэквивалентно полной сортировке в оригинальном решении на с++
Пара вопросов.
Мне не очень понятно почему бакет фиксированной длинны лучше, чем Open Addressing на массиве большего размера? Условно, если у нас 2^b корзин по 8 элементов в каждом, то почему бы не выделить 8 * 2 ^ b корзин по одному элементу, а при коллизии использовать, например, quadratic probing (он вроде как дружелюбен к кешам при маленьком заполнении)? Это из-за возможности использования векторных инструкций?
Если сделать не одну хеш-таблицу, а 26 и определять в какую из них идти по первой букве, то мы вроде бы сильно уменьшим проблему коллизиями. Эдакий одноуровневый trie. Есть подозрение, что по скорости не выиграем т.к. памяти скорее всего больше понадобится и, соответственно, больше cache miss. А если настроить размер хеш таблиц для каждой буквы отдельно? Или так не получится из-за жесткой привязки b = 17?
Любой open addressing требует сравнение элементов: решение автоматически с 0.9 до 1.7 секунды замедляется, т.к. ещё в две "случайные" локации бегаем - в
wordsи вoutput(можно сократить до одной доп. локации, если в корзине хранить индексы: можно даже всё в 64 байта уместить при желанииstruct { uint16_t hashesHigh[8]; uint24 counters[8]; uint24 words[8]; }). Если кажется, что не требует, то тогда зачем probing? Допущение хэш-коллизий автоматически влечёт за собой требование искать и сравнивать элементы вообще всегда. В исходнике есть настройка kEnableOpenAddressing - можно посмотреть, что она включает. Кроме избыточных походов по случайным адресам ещё добавляется цикл.Больше cash miss, т.к. по 1.63 элемента на корзину (=кэш-линию) уже не получим. b + битовая длина хранимого суффикса хэша должны быть равны 32 (хотя может быть можно и для 31 или 30 бит seed для perfect hash найти), чтобы сравнение суффикса хэша избавляло нас от необходимости сравнивать содержимое элементов. Действительно perfect hash требует b >= 17. Если префикс хэша будет меньше 17, то придётся хранить уже суффиксы хэша в
uint32_t, что на Ivy Bridge повлечёт необходимость усложнить код в части сравненияhashesHigh. Это опять же замедление. Параметры найденного решения действительно ограничены сверху и снизу.
Не пробовали сделать trie с выделением памяти под узлы из фиксированного пула, а не при помощи системного malloc? boost::object_pool или вообще вручную, создав большой массив узлов и используя индекс в нём вместо указателей.
Пробовал. trie.reserve даёт пару десятков миллисекунд. В коде его не оставил, чтобы поменьше магических констант было. Индексы по сравнению с итераторами или указателями для std::vector также не дают никакого выигрыша. Вся реализация std::vector-а у компилятора "перед глазами", так что для меня очевидно, что разницы быть не должно. RIP-relative addressing тоже не даёт какого-то замедления по сравнению с абсолютными адресами в случае глобального static массива в 32-bit режиме.
Подсчёт слов