Отсортировать дерево?

[tengiz]

Я там выше даввл решение, размер структуры в районе 10М, поиск константный.

Да, я имел в виду похожую идею, хотя и разложенную на более заковыристую структуру данных. При этом Ваше решение можно улучшить в смысле времени выполнения как при построении, так и при использовании.

[Berlaga]

Я там выше даввл решение, размер структуры в районе 10М, поиск константный.

Да, я имел в виду похожую идею, хотя и разложенную на более заковыристую структуру данных. При этом Ваше решение можно улучшить в смысле времени выполнения как при построении, так и при использовании.

Тенгиз, пожалуйства, приведете свое решение. Это же так интересно!
Спасибо заранее.

[tengiz]

Вот пара толстых намеков:
1. Top-n список для префиксов длины k можно посчитать из top-n списков для "покрываемых" префиксов длины k+1.
2. Списки для префиксов всех длин можно строить одновременно за один последовательный проход по сортированному списку слово/вес за линейное по длине исходного списка время.

[tengiz]

А вообще нужно заранее дерево построить, где у каждого нода хранится топ-10 окончаний и имеется 0..26 деток. О(1)

Можно не хранить окончания, вместо этого для каждого из под-деревьев хранить максимальную частоту слов в под-дереве, что позволит делать прицельные обходы для динамического построения окончаний.

[OtherSide]

А вообще нужно заранее дерево построить, где у каждого нода хранится топ-10 окончаний и имеется 0..26 деток. О(1)

Можно не хранить окончания, вместо этого для каждого из под-деревьев хранить максимальную частоту слов в под-дереве, что позволит делать прицельные обходы для динамического построения окончаний.

А что это даст. Нам же надо максимальное значение, а 10 максимальных. Ну вот в одной ветке максмиальное 10000, а в другой 99990. И что делать? Может в первой ветке лежат еще 9991...10000. А может, нет

[tengiz]

А что это даст. Нам же надо максимальное значение, а 10 максимальных. Ну вот в одной ветке максмиальное 10000, а в другой 99990. И что делать? Может в первой ветке лежат еще 9991...10000. А может, нет

Это значит, что нужно начинать обход с ветки с максимальным значением частоты и не выходить из нее пока наберется нужное количество слов или не попадется слово с частотой меньшей, чем максимальная частота другой ветки и после этого продолжить обход в другой. И так на каждом уровне рекурсии.

[OtherSide]

А что это даст. Нам же надо максимальное значение, а 10 максимальных. Ну вот в одной ветке максмиальное 10000, а в другой 99990. И что делать? Может в первой ветке лежат еще 9991...10000. А может, нет

Это значит, что нужно начинать обход с ветки с максимальным значением частоты и не выходить из нее пока наберется нужное количество слов или не попадется слово с частотой меньшей, чем максимальная частота другой ветки и после этого продолжить обход в другой. И так на каждом уровне рекурсии.

Это может ускорить в определенных случаях, но в общем случе - х.з. Тем более у них там на тестовом примере были не настоящие слова языка, а комбинации a,b,c из десятков символов.
Даст ли прирост производительности наличие максимального числа в ветке третичного дерева, если нужно выбрать первые 10? Не уверен

[tengiz]

Это может ускорить в определенных случаях, но в общем случе - х.з. Тем более у них там на тестовом примере были не настоящие слова языка, а комбинации a,b,c из десятков символов.
Даст ли прирост производительности наличие максимального числа в ветке третичного дерева, если нужно выбрать первые 10? Не уверен

Придумать случай распределения данных где это не поможет, конечно возможно. Например, когда у всех слов одинаковая частота, при этом просто проход дерева в естественном порядке уже дает правильный ответ. Также я отвечал на сообщение АццкоМото где он предложил дерево с 26 ответвлениями, предполагая ситуацию реального словаря, а не искусственный набор данных. Поэтому наличие максимальной частоты у каждой ветви позволит вместо перебора сразу двигаться в нужную ветку при первом проходе. Алгоритм для top-n, конечно, немного сложнее, когда на одном и том же уровне нужно продолжать после выхода из ветки, но так как это происходит на каждом уровне и уровней больше, чем 10, то и в разумных случаях, я полагаю, выигрыш будет заметный. В любом случае можно иметь гибридную структуру, которая может кешировать результат для узла, если поиск top-10 перебором таким алгоритмом будет "дорогим", скажем, когда для нахождения top-10 нужно будет пройти через количество конечных узлов много большее, чем 10.

[АццкоМото]

А вообще нужно заранее дерево построить, где у каждого нода хранится топ-10 окончаний и имеется 0..26 деток. О(1)

Можно не хранить окончания, вместо этого для каждого из под-деревьев хранить максимальную частоту слов в под-дереве, что позволит делать прицельные обходы для динамического построения окончаний.

Нет ничего глупее
Максимум слева, вторая величина - справа. Упс. "Прицельный обход" превратился в тыкву

[tengiz]

Максимум слева, вторая величина - справа. Упс. "Прицельный обход" превратился в тыкву

...нужно начинать обход с ветки с максимальным значением частоты и не выходить из нее пока наберется нужное количество слов или не попадется слово с частотой меньшей, чем максимальная частота другой ветки и после этого продолжить обход в другой. И так на каждом уровне рекурсии.

[АццкоМото]

Максимум слева, вторая величина - справа. Упс. "Прицельный обход" превратился в тыкву

...нужно начинать обход с ветки с максимальным значением частоты и не выходить из нее пока наберется нужное количество слов или не попадется слово с частотой меньшей, чем максимальная частота другой ветки и после этого продолжить обход в другой. И так на каждом уровне рекурсии.

если так, то это минимальная оптимизация. ничем не отличается от оригинального решения

[tengiz]

если так, то это минимальная оптимизация. ничем не отличается от оригинального решения

Ну вот, видите, Вы зря сердились. Это просто вариант уменьшить размер или оптимизировать баланс межу размером-локальностью данных дерева при коротких префиксах, когда окончания еще могу быть длинными, да еще и если в уникодах.

[OtherSide]

если так, то это минимальная оптимизация. ничем не отличается от оригинального решения

Ну вот, видите, Вы зря сердились. Это просто вариант уменьшить размер или оптимизировать баланс межу размером-локальностью данных дерева при коротких префиксах, когда окончания еще могу быть длинными, да еще и если в уникодах.

сложно алгоритма та же - o(n)

[tengiz]

..Это просто вариант уменьшить размер или оптимизировать баланс межу размером-локальностью данных дерева при коротких префиксах, когда окончания еще могу быть длинными, да еще и если в уникодах.

сложно алгоритма та же - o(n)

Не уточните что здесь (n)? И о каких алго идет точно речь?

[tengiz]

Возможно, коллеги давно не имели дело с алгоритмом quick selection, или давно не имели возможности в реальной практике делать multi-way merge для получения top-k. Поэтому некоторые пояснения на пальцах:

Нужно выбрать top-k на несортированных данных длины n.

1. Если это не массив, а stream, тогда алгоритм с хипом будет адекватным вариантом, при этом нужно будет просмотреть поток от начала до конца. Сложность пропорциональна n * log k.
2. Если это массив (т.е. допускается произвольный доступ, да еще и можно менять на месте), то есть вариант получше - quick selection, который в среднем и лучшем случае пропорционален n и не зависит от k. В худшем случае пропорционален квадрату n. Но мы все пользуемся quick sort в большинстве неспециальных случаев, несмотря на то, что у него такие же точно характеристики для худшего случая как и у quick selection.
3. Есть "как бы" промежуточный вариант, когда исходные данные нельзя модифицировать на месте, однако они уже кем-то распартированы и для каждой партиции известно максимальное значение атрибута, по которому делается top. Если партиций p много больше, чем k, то при "разумно случайном" (не нужно только меня пытать на тему точного определения) распределении данных может оказаться так, что нужно будет пройтись по подмножеству данных, а не по всем данным. А именно, вместо сканирования всех p партиций нужно будет только просканировать порядка O(k) партиций.
4. Как организовать партиции в виде дерева, я думаю, понятно.

[tengiz]

Пока ехал домой придумал как доказать, что top-k по частоте на дереве с максимумом частоты поддерева записанном в узле в худшем случае стоит операций/памяти O((height - prefix) * k), где prefix - это длина префикса, height - это высота дерева.

Т.е. я утверждаю, что для дерева, отсортированного по значению строки, top-k по ранку, который независим от значения строки, можно сделать за время, как если бы дерево было отсортировано по ранку. Единственный caveat - k должно быть "небольшим".