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

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

Вставить, который добавляет новую пару ключ/значение в коллекцию,
Удалить, который удаляет пару ключ/значение из коллекции,
Percentile, в котором указывается, какой процентиль имеет значение, связанное с данным ключом, и
Tell-Percentile, который принимает номер процентиля и возвращает ключ, значение которого является самым низким значением, по крайней мере, для данного процентиля.

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

Есть ли способ сделать эти операции эффективными (скажем, сублинейное время?)

Ответ 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 работала, тоже.

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

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