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

Question

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

Например

1 - й Валет 100

2 - е Иоанна 50

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

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

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

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

Answer 1

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

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

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

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

Answer 2

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

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