Структура данных для эффективного поиска процентилей?

Ответ 1

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

Дерево статистики заказов - это тип сбалансированного двоичного дерева поиска, который в дополнение к обычным операциям двоичного дерева поиска поддерживает еще две операции:

• Ранг (ключ), который возвращает количество элементов в дереве, меньшем, чем данный элемент, и
• Выберите (k), который возвращает наименьший элемент k в дереве.

Деревья статистики заказов можно построить, добавив нормальное сбалансированное двоичное дерево поиска (например, красное/черное дерево или Дерево AVL) с дополнительной информацией, которая сохраняется при поворотах. Таким образом, все обычные операции BST в дереве статистики заказов могут быть выполнены для выполнения в O (log n) времени, а дополнительные операции также выполняются в O (log n) времени.

Теперь предположим, что вы просто хранили значения, а не показатели key/percentile. В этом случае было бы очень просто реализовать поиск процентилей следующим образом. Сохраните все значения в дереве статистики заказа. Чтобы определить показатель процентиля для заданного значения, используйте операцию rank в дереве статистики заказов, чтобы посмотреть, какой индекс указывает значение. Это дает число в диапазоне от 0 до n - 1 (где n - количество элементов в дереве), обозначая положение этой оценки в дереве статистики заказа. Затем вы можете умножить это число на 99/(n - 1), чтобы получить оценку процентиля для значения, которое выполняется в диапазоне от 0 до 99, если требуется.

Чтобы определить наименьшее значение, большее некоторого процентиля, вы можете использовать операцию select следующим образом. Учитывая процентиль между 0 и 99, умножите процентиль на 99/(n - 1), чтобы получить реальное число между 0 и n - 1 включительно. Взятие потолка этого числа дает натуральное число в диапазоне от 0 до n - 1 включительно. Используя операцию select в дереве статистики заказов, можно использовать для поиска первого значения в диапазоне, который находится выше или ниже указанного процентиля.

Однако эти операции предполагают, что мы имеем чисто значения в структуре данных, а не пары ключ/значение. Чтобы эта операция работала для пар ключ/значение, мы будем дополнять нашу структуру данных следующим образом:

• Вместо сохранения значений мы будем хранить пары ключ/значение в каждом node. Дерево статистики заказов сортирует пары ключ/значение исключительно по их значению, причем ключ переносится как спутниковые данные.
• Мы будем хранить вторичную хеш-таблицу, которая отображает ключи в соответствующие значения.

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

Если предположить, что в хеш-таблице используется цепное хеширование, тогда время, требуемое для каждой операции, приведено ниже:

• Вставить: время O (log n) для вставки пары значение/ключ в дерево статистики заказа, плюс O (1) амортизированное время для вставки пары ключ/значение в хэш-таблицу. Общее время O (log n) амортизировано.
• Удалить: время O (log n) для удаления пары значение/ключ из дерева статистики заказа, плюс (1) амортизированное время для удаления пары ключ/значение из хеш-таблицы. Общее время O (log n) амортизировано.
• Percentile: O (1) ожидаемое время для поиска значения, связанного с ключом, времени O (log n) для выполнения операции rank и O ( 1) дополнительное время, чтобы отобразить ранг в процентиль. Общее время ожидания O (log n).
• Найти-Percentile: O (1) время, необходимое для сопоставления процентиля с рангом и O (log n) времени, необходимого для выполнения операции select. Общее время O (log n) наихудший.

Надеюсь, это поможет!

Ответ 2

Существует простая и высокоэффективная возможность:

Если вы можете жить с поиском процентиля только в структуре, заполненной окончательно заполненной, то:

Используйте ArrayList для динамического наращивания, когда вы не знаете количество элементов.
Если вы их знаете, начните с массива напрямую, иначе создайте массив из динамического массива. (например, ArrayList в java).

вставить: не требуется, заменяется добавлением в конце и сортировкой один раз.
удалить: не обязательно, если вы можете жить с этим.
tell-percentile: еще проще: что-то очень близко к: element [length * percentile]: O (1)

На практике подход массива будет намного быстрее, чем сбалансированный древовидный подход, по крайней мере, в java, когда ваше приложение может создавать массив один раз (например, ежедневная оценка ученика, ежедневно его наращивать)

Я реализовал алгоритм (мой) выше, используя самозаписываемую ArrayListInt, которая делает то же самое, что и ArrayList, но использует примитивные типы (double, int) вместо типов объектов. Я отсортировал его один раз, когда все данные были прочитаны.

Далее вам нужно значение ключа:
Я бы просто добавил карту дерева (сбалансированное дерево). Теперь немного сомневаюсь в том, что имеет значение TreeMap и добавочный массив процентилей. Это зависит от того, как часто вам приходится искать, и использования памяти в сравнении с временем поиска.

Update:

Результаты: treeet vs sorted array (динамическое наращивание массива, затем, наконец, сортировка:

num elements: 1000 treeSet: 4.55989 array=0.564159
num elements: 10000 treeSet: 2.662496 array=1.157591
num elements: 100000 treeSet: 31.642027 array=12.224639
num elements: 1000000 treeSet: 1319.283703 array=140.293312
num elements: 10000000 treeSet: 21212.307545 array=3222.844045

Это количество элементов (1e7) теперь близко к пределу (1 куб кучи), в следующем шаге память закончится (уже началось с 1e7, но с очисткой памяти после treeet, работа для измерения 1e7 работала, тоже.

Не хватает времени поиска, но отсортированный массив с бинсовым поиском доступен только хеш-таблице

Наконец: Если вы можете создать набор учеников один раз, например, ежедневно, то использование подхода массива дает гораздо более простой поиск процентилей.