Обновление относительного списка лидеров в реальном времени для каждого пользователя среди друзей

Question

Я работал над функцией моего приложения для реализации списка лидеров - в основном, составление рейтинга пользователей в соответствии с их оценкой. Я в настоящее время отслеживаю счет на индивидуальной основе. Я думаю, что эта таблица лидеров должна быть относительной, а не абсолютной, то есть вместо того, чтобы иметь 10 лучших пользователей с наибольшим количеством баллов по всему сайту, это 10 лучших среди друзей в сети пользователя. Это кажется лучше, потому что у всех есть шанс быть # 1 в их сети, и есть форма дружеского соревнования для тех, кто интересуется такими вещами. Я уже храню счет для каждого пользователя, поэтому задача состоит в том, как эффективно вычислить рейтинг этого счета в режиме реального времени. Я использую Google App Engine, поэтому есть некоторые преимущества и ограничения (например, IN [массив]), запросы выполняют подзапрос для каждого элемента массива, а также ограничены 30 элементами на оператор

Например

1-й Джек 100

2-й Иоанн, 50

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

1. Потяните список всех пользователей сайта, упорядоченных по счету. Для каждого пользователя выберите своих друзей из этого списка и создайте новый рейтинг. Сохраните звание и порядок списков. Обновлять ежедневно. Минусы - если я получу много пользователей, это займет вечность

2a. Для каждого пользователя выберите своих друзей и для каждого друга выберите балл. Сортировать этот список. Сохраните звание и порядок списков. Обновлять ежедневно. Запишите последнюю позицию каждого пользователя, чтобы существующий список можно было использовать для повторного заказа на следующее обновление, чтобы сделать его более эффективным (может сэкономить время сортировки)

2b. То же, что и выше, за исключением того, что вычисляются только ранги и порядок списков для людей, чьи профили были просмотрены в последний день Минусы - рейтинг актуален только для 2-го лица, просматривающего профиль

Answer 1

Если записи очень редки по сравнению с чтениями (предположение ключа в большинстве хранилищ значений ключа, а не только в них ;-), тогда вы можете предпочесть удар по времени, когда вам нужно обновить оценки (запись) вместо того, чтобы получить относительные списки лидеров (чтение). В частности, когда счет пользователя меняется, поставьте в очередь задачи для каждого из своих друзей, чтобы обновить свои «относительные списки лидеров» и сохранить эти списки лидеров в качестве атрибутов списка (которые поддерживают порядок! -) надлежащим образом отсортированными (да, последний - денормализация - это часто необходимо денормализовать, т. е. дублировать информацию соответствующим образом, чтобы наилучшим образом использовать хранилища ключей и значений! -).

Конечно, вы также будете обновлять относительные списки лидеров, когда дружба (соединение между пользователями) исчезнет или появится, но они должны (я думаю) быть даже реже, чем обновления очков; -).

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

Например, большие изменения в баллах (более редкие) могут вызвать повторные вычисления относительных списков лидеров, в то время как более мелкие (более частые) скрываются и применяются только время от времени "когда вы дойдете до этого". Трудно быть более конкретным без приблизительных цифр о частоте обновлений различной величины, типичных размерах кластеров дружбы сети и т. Д., И т. Д. Я знаю, что, как и всем остальным, вам нужен идеальный подход, который применим независимо от того, насколько разные размеры и частоты под вопросом ... но вы его просто не найдете! -)

Answer 2

Существует библиотека Python для хранения рейтинга:

http://code.google.com/p/google-app-engine-ranklist/