Вопрос 1: насколько я пониманию, сплей-деревья должны крайне эффективно работать с такими моделями запросов, которые имеют крайне горбатое нормальное распределение по запрашиваемым данным ?
Вопрос 2: И вот ещё, если дерево поиска (avl, r/b и т.д.), в отличие от обычного отсортированного массива, используется, когда помимо операции find(x), присутствуют операции модификации - insert(x), remove(x) и т.д., и нет никакого смысла использовать дерево поиска, если операции модификации отсутствуют(конструктор с данными для начальной инициализации не учитывается), но в случае сплей-дерева, как я понимаю, даже если не подразумевается модификация, всё равно выгоднее использовать его в противовес статичному отсортированному массиву, если конечно имеется нормальное распределение на find'ы с большим пиком ?
Если твоя память делится по стоимости доступа на несоклько зон (оперативная и дисковая) то
используют LRU(HashMap) для того чтобы горячие ключи всегда были подняты наверх.
Есть модификации LRU (ARC, 2Q).
Где используется Splay дерево - я не знаю. Никогда не слышал о том чтобы эта
структура была практически где-то применима.
mayton2019, имелось в виду, что на find'ы будут приходить range запросы, а не запросы на равенство (поэтому хеш таблица не подойдёт)
например, autocomplete
Идея пока выглядит достаточно аватнюрно. Нигде не указано как Splay должен реагировать на диапазонные
поиски. Для точечных - алгоритм пере-балансировки определен.
Но нет никаких оснований думать что после такой балансировки диапазонные запросы вдруг
станут эффективнее.
mayton2019, ну вот в вик ,например, написано, что это дерево поиска, значит на нём порядок есть
ну и все эти зиги а заги это же повороты, значит порядок элементов сохраняется, не понимаю почему это должно не работать
на всякий случай уточню: range запрос имелось в виду запрос на неравеснство (>, <, >=, <=)
Wataru, ну типа есть хеш-таблица, где можно делать запросы только на равенство, есть дерево поиска, где можно делать запросы по неравенству(самих целевых значений узлов дерева), а в дерево отрезков, где можно делать запросы по непрерывному диапазону узлов (отрезку), и вычислять какую-то функцию для этого подмножества, но в дереве отрезков запрос именно можно сказать по 2-му параметру узлов - порядковому номеру, которые вместе образуют диапазон, а не целевому значению узла, как в обычном дереве отрезков, так что это немного не то, про что я говорил
но в дереве отрезков запрос именно можно сказать по 2-му параметру узлов - порядковому номеру,
Если в качестве диапазоно взять ключи, то у вас будет запрос по ключам. Но вообще, надо конкретно вашу задачу узнать. Вы там говорили, что данные не меняются, так что возможно какой-нибудь сортированный массив с одним бинпоиском может быть даже быстрее любой другой структуры данных.
Если в качестве диапазоно взять ключи, то у вас будет запрос по ключам.
не уверен, что это получится, если вставить новый элемент, то в отличие от обычного дерева отрезков, где нейтральный элемент заменится на новый и пересчитаются предки, то тут как минимум придётся делать дерево но узлах, а не массиве и кажется, что оно сильно поехать может если не в конец вставить, а в середину
Вы там говорили, что данные не меняются, так что возможно какой-нибудь сортированный массив с одним бинпоиском может быть даже быстрее любой другой структуры данных.
вот как раз не уверен, например, если там лежит 1кк элементов, при этом 99% запросов это какие-то 1000 элементов, то для них будет в сплей дереве глубина в 2 раза меньше, чем до остальных (должна быть), а в отсортированном массиве для всех элементов будет примерно logn скачков в рандомное место памяти, ну то есть, например, в сплей дереве будет для 1кк в среднем 11 скачков на запрос, а в отсортированном массиве 20 скачков
Wataru, вот, кстати, что в самом верху топика про сплей деревья в вики написано:
For random access patterns drawn from a non-uniform random distribution, their amortized time can be faster than logarithmic, proportional to the entropy of the access pattern. For many patterns of non-random operations, also, splay trees can take better than logarithmic time, without requiring advance knowledge of the pattern.
floppa322, В зависимости от того, что вам на самом деле надо делать со структурой данных, она может быть строго O(1), а не чуть лучше логарифма в среднем на некоторых данных.
Wataru, ну я как раз и спросил, что мб как раз с сильно неравномерными распределениями сплей дерево как раз лучшее, что есть, мб даже лучше статического массива при отсутствии модификации
1) Нет, сплей дерево всегда работает за log n амортизировано. Его лучше использовать как временную структуру данных. То есть на серверах для поиска пользователей оно иногда будет долго работать (а это недопустимо), но в сумме быстро. Здесь написано, что такое амортизированный алгоритм https://ru.m.wikipedia.org/wiki/%D0%90%D0%BC%D0%BE...
2) Нет, отсортированный массив занимает меньше места и бинарный поиск происходит быстрее.
