Хм, а первая задача разве за линейное время не решается? В каждом слове ищем первую слева букву (начиная при этом со второй буквы, т.к. префикс не должен быть пустым), большую первой буквы в следующем слове и обрезаем слово по найденной букве (не включая ее), от последнего слова оставляем только первую букву. На всех приведенных примерах это вроде работает…
Спасибо большое за ссылки, обязательно поизучаю на досуге! С libdatrie, кстати, я сравнение не делал… Относительно терминологии, мне больше нравится Radix Tree и русский вариант — дерево цифрового поиска.
Это я к тому, что суммарный объем необходимой памяти, в принципе, один и тот же, поэтому, чем меньше куски, тем больше их нужно, тем больше операций с памятью…
Была мысль вместо односвязного списка хранить двоичное дерево (то же АВЛ), но что-то страшно стало :) А вот с алфавитом все немного интереснее выглядит, надо будет подумать…
Доля правды в ваших словах есть. Вот распределение длин ключей во внутренних узлах дерева для двух тестовых наборов:
Однако, хранить в одном узле один символ (при двух указателях) — это, по-моему, перебор. Хотя, с другой стороны, такой вариант (несжатое префиксное дерево) у меня реализован, но статистику я с него еще не снимал…
1) С этим замечанием согласен, на графике время отнормировано на размер (в символах) используемого набора строк, иначе разброс для одного графика оказывался очень большим. Сейчас попробую пересчитать чистое время… На третьем графике шкала обозначена в подписи :) — по оси Y отложено количество байт на один символ (символ у меня занимает один байт)…
2,3) Про продакшн никто и не говорит :)
1) На первых двух графиках сравниваются между собой два времени, какая разница, какая там шкала? На третьем шкала обозначена… На серьезную статобработку данных времени и сил пока нет :)
2) Стек выдержал :) Кстати, да, надо было бы глубину дерева измерить. А в принципе, можно и итеративную реализацию сделать…
3) А какая длина массива должна быть (это в случае, когда дерево мутируется)? На самом деле я уже думал над таким вариантом — держать в узле вектор указателей на всех дочерей узла…
ЗЫ: Не совсем функционально, зато рекурсивно и в одну строчку :)
Однако, хранить в одном узле один символ (при двух указателях) — это, по-моему, перебор. Хотя, с другой стороны, такой вариант (несжатое префиксное дерево) у меня реализован, но статистику я с него еще не снимал…
Ссылку попозже посмотрю, спасибо!
2,3) Про продакшн никто и не говорит :)
2) Стек выдержал :) Кстати, да, надо было бы глубину дерева измерить. А в принципе, можно и итеративную реализацию сделать…
3) А какая длина массива должна быть (это в случае, когда дерево мутируется)? На самом деле я уже думал над таким вариантом — держать в узле вектор указателей на всех дочерей узла…