Предложение по структуре данных для ранжирования пользователей на основе баллов

Question

Я хочу использовать создание и сохранение рангов в памяти.

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

• Сортировка рангов по возрастанию или убыванию баллов.Вставка или удаление за время O (log n).
• Учитывая идентификатор пользователя, ищите ранг / оценку пользователя вместе с n предшествующими и последующими рангами за время O (log n).Например, получить ранги пользователя 8347 с 5 предыдущими и последующими рангами.
• Извлечь n рангов из любого смещения x.Например, получить 100 рангов, начиная с 800

Учитывая эти требования, есть ли какие-либо предложения относительно того, какая структура данных соответствует этим требованиям лучше всего?

Answer 1

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

Статистическое дерево заказов - это расширенное двоичное дерево поиска, которое в дополнение к хранению элементов в отсортированном порядке позволяет искать элементы по их индексу в дереве. Таким образом, структура поддерживает O (lg n) вставку, удаление и поиск значений по их ключу, а также O (lg n) поиск элемента по его индексу. Если вы сохраняете баллы в этой структуре, вы можете легко вставлять или обновлять новые баллы, а также отслеживать ранг каждого элемента в дереве.

Чтобы связать пользователей с их оценками, вы могли бы объединить эту структуру со вспомогательной хэш-таблицей, отображающей идентификаторы пользователей на узлы в дереве статистики заказов, в котором хранятся оценки для этого пользователя. Это даст вам O (1) доступ к счету игрока в дополнение к O (lg n) поиску рейтинга.

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

Answer 2

двоичное дерево поиска, одна реализация - http://en.wikipedia.org/wiki/AA_tree

Space   O(n)            O(n)
Search  O(log n)    O(log n)
Insert  O(log n)    O(log n)
Delete  O(log n)    O(log n)

Answer 3

Как насчет очереди приоритетов?

Каждый человек получит счет, бросит его в очередь приоритетов, и он будет выполнять сортировку по возрастанию / убыванию приоритета / значению / рангу /и т.д.

Answer 4

Использование базы данных SQLite в памяти.