Сортировка ConcurrentSkipListMap: Может ли это быть сделано по сравнению значения?

Question

В игре я пытаюсь сохранить список пользователей и отсортировать его по количеству очков, чтобы я мог запросить список в любой момент времени и вернуть (например) десятку лучших пользователей по количеству очков. Этот список должен быть потокобезопасным. Я предполагаю использование строки userName в качестве ключа, а значением будет объект User, который реализует Comparable и имеет такие свойства, как displayName и Score. Следовательно, объект User будет иметь метод CompareTo, который будет сравнивать атрибут Score для определения его позиции.

Я смотрю на использование ConcurrentSkipListMap для этого, но, насколько я могу судить, Map (в отличие от Set) использует ключ для сортировки. Мне бы хотелось, чтобы список сортировался по свойству Score объекта User, но я все еще использую Map, потому что мне нужно иметь доступ к любому данному пользователю и изменять его атрибут Score из потока.

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

Кто-нибудь сможет подсказать, как этого добиться?

Answer 1

Нет, я не думаю, что вы можете. Для упорядочения используется тот же компаратор, что и для индексации. Вам, вероятно, придется поддерживать 2 коллекции. Один для сохранения порядка оценок пользователя для обращения к пользователям по имени.

Answer 2

Майкл прав, вы не можете иметь свой торт и есть его;)

Я думаю, что у вас есть 3 варианта:

1. Используйте карту, чтобы обновлятьпользователь быстро набирает очки, и вы платите цену при сортировке, чтобы найти самые высокие баллы.
2. Используйте SortedSet, который сортирует по баллам так, чтобы быстро находить самые высокие баллы, но вы должны заплатить цену при обновлении баллов пользователя
3. Поддерживать две структуры данных, чтобы вы могли получить лучшее из 1 и 2. Например, ваши реальные данные в наборе отсортированы по баллам, но затем также поддерживается сопоставление имени пользователя для индексации вустановить или подобное.Таким образом, у вас всегда есть отсортированные оценки, а обновление оценки пользователя - это просто поиск, а не поиск.Ценой, которую вы платите за это, является то, что теперь вы храните некоторую дублирующую информацию в двух местах, и особенно учитывая одновременный доступ, может быть сложно обеспечить, чтобы оба места всегда обновлялись синхронно.

Я бы не стал делатьпредположения о том, что быстрее между 1 и 2. Я бы опробовал их оба с вашим ожидаемым использованием и измерил, чтобы увидеть, что является худшим.

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

Answer 3

get(key) зависит от компаратора (чтобы можно было найти ключ).Вы предлагаете компаратор, который будет зависеть от get(key) (для доступа к сопоставленному значению ключа сравнение, основанное на этом).Это обязательно приводит к бесконечной рекурсии и переполнению стека (с другой стороны, вы публикуете на нужном сайте !!)