Обновить отсортированный список

Я думаю, что есть общее название для алгоритма, который я ищу.

У меня есть большой список игроков, отсортированных по их счету. например 1 миллион или миллиард игроков. Каждую секунду один игрок меняет свой счет, и я хочу обновить отсортированный список, чтобы он был отсортирован, и я хочу знать позицию нового игрока.

Я могу обновить счет и пересортировать список лунок. (неэффективно) или я могу пересортировать из [oldpos, newpos] (лучше) или я могу переместить игрока и сместить других игроков. (Лучший)

Есть ли название для такого алгоритма?

Верно ли, что обычные базы данных не справятся с этой задачей эффективно, и мне нужно разработать сервис на Java, C #, Go и т. Д., Который будет хранить отсортированный список в ОЗУ и вносить изменения?


microservices database sorting algorithm sortedlist
person Artem    schedule 02.04.2017    source источник
comment
обычные базы данных SQL должны эффективно справляться с такого рода задачами, поскольку индекс БД — это именно та структура данных, которая вам нужна. К сожалению, их нет :(   -  person Matt Timmermans    schedule 02.04.2017

Ответы (1)


arrow_upward
3
arrow_downward

Вы можете хранить дерево AVL, операции вставки и удаления занимают O(logn) времени на таких структура данных. каждый раз, когда вам нужно обновить игрока: удалить из дерева, изменить счет, вставить в дерево.

Это именно тот компромисс, который вы ищете, все операции занимают O (logn), и, поскольку вам нужны все операции (поиск и обновление - удаление\вставка), это лучшее совпадение для вас. Потребление памяти составляет O(n) между прочим.

person Anton.P    schedule 02.04.2017
comment
Благодарю вас. Меня беспокоит следующее. Если бы у меня было 1 миллион игроков, то дерево было бы примерно на 20-30 шагов вглубь. Это будет 2-3 миллиона распределений узлов. Распределение памяти и фрагментация памяти могут изменить эти ожидания? по сравнению с int32[1000000] составляет всего 4 МБ и одно выделение. (Я могу хранить все остальные данные в обычной базе данных или в другом месте.) Я думаю, что сдвиг идентификаторов игроков в массиве может быть быстрее и более предсказуем. В любом случае, я бы предпочел не изобретать новый алгоритм. - person Artem; 03.04.2017