Самый быстрый способ вычислить процентиль элементов в коллекции

Question

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

Answer 1

Если вам нужна структура данных в памяти, вам нужно дерево статистики заказов , которое является расширенной версией двоичного дерева поиска.Это поддерживает поиск значения Nth в отсортированном порядке, вставку и удаление всего за O (log (n)).

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