Laravel по-русски
Laravel по-русски
Русское сообщество разработки на PHP-фреймворке Laravel.
Ты не вошёл. Вход тут.
Доброго времени суток!
Каждому из участников соответствует оценка, причем у разных участников могут быть одинаковые оценки.
Имеется ли на примете алгоритм вычисления места участника в рейтинге?
Желательно обойтись без промежуточного хранения данных.
Изменено Androbim (12.07.2017 12:52:02)
Не в сети
Что мешает попросту отсортировать элементы по рейтингу и по ФИО, например?
Не в сети
Что мешает попросту отсортировать элементы по рейтингу и по ФИО, например?
А как место вычислить?
Не в сети
Мастер 
А как место вычислить?
Переменной.
Решение для MySQL:
SET @position = 0;
SELECT a.* FROM (
SELECT id, @position := @position + 1
FROM MyUserTable
ORDER BY id desc
) as a WHERE a.id = 103;вместо MyUserTable и ORDER BY id desc (и id 103) - твои значения
P.S. Не знаю как будет работать с persistent соединениями с базой.
Изменено covobo (12.07.2017 14:29:45)
Не в сети
Решение для MySQL
А если оценки одинаковые? Место-то, при этом одно...
Не в сети
Мастер ну, первое что пришло в голову 
Смещаем место только если изменился рейтинг.
Если рейтинг может быть отрицательным - то чуть хитрее надо.
SET @position = 1;
SET @prev_rating = 0;
SELECT a.position FROM (
SELECT id, if(@prev_rating != rating, @position := @position + 1, @position) as position, @prev_rating := rating
FROM MyUserTable
ORDER BY id desc
) as a WHERE a.id = 103;(если у тебя оценка хранится физически, а не является результатом подсчета во время запроса, то можно сделать иначе, более понятно, через джоины, но работать будешь дольше.)
Изменено covobo (12.07.2017 14:54:08)
Не в сети
Мастер 
sqlSELECT id, @position := @position + 1
Действительно оригинально. Однако можно попробовать устранить первый запрос (и соответственно зависимость от контекста выполнения), перенеся
sqlSET @pos внутри SELECT (как JOIN).
sql... SELECT id, @position := @position + 1 FROM @position := 0, MyUserTable ...
- А если оценки одинаковые? Место-то, при этом одно…
@pos будет работать в любом случае, ведь сортировка детерминированная.
А у меня такой вариант: использовать GROUP_CONCAT (нестандартная, но крайне полезная функция MySQL).
Допустим, в таблице 2 поля: id и score. Первое уникальное, второе нет.
| id | score |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 1 |
| 4 | 3 |
| 5 | 1 |
| 6 | 0 |
| 7 | 10 |
| 8 | -1 |
| 9 | 2 |
| 10 | 0 |
Тогда запрос (где 0000000003 — id пользователя):
sqlSELECT INSTR(GROUP_CONCAT('[', LPAD(id, 10, 0), ']' ORDER BY score DESC SEPARATOR ''), '[0000000003]') FROM t WHERE score >= 20;
13 25 1 ... 12 ... 24 ... 36 [0000000001][0000000002][0000000003] ^^^^^^^^^^^^ 1+10+1=12 (25 - 1) / 12 = 3
То есть все id (должно быть некое уникальное значение) объединяются в одну строку (добиваясь до 10 знаков нулями — достаточно для UNSIGNED INT), отсортированную по score, дальше в этой же строке ищется id самого пользователя и по положению в ней определяется его место в рейтинге.
В отличии от @pos этот вариант не требует прохода по всем строкам и атомарный (работает в один запрос).
Недостаток: чем больше таблица, тем длиннее строка, создаваемая GROUP_CONCAT. Соответственно, растёт расход памяти и время поиска подстроки. Иными словами, чем ближе пользователь к началу рейтинга, тем быстрее будет работать функция (WHERE как раз добавлен для того, чтобы уменьшить длину строки, т.к. нас не интересуют пользователи, которые имеют меньший рейтинг).
Документация по GROUP_CONCAT.
Не в сети
Смещаем место только если изменился рейтинг.
В настоящее время рейтинг в структуре не хранится. Предполагалось вычислять его "по-ходу".
Впрочем, мне кажется, что даже если изменить структуру под Ваше решение... Не оптимально.
P.S. Сорри, подразобрался, прикину. Спасибо :-)
Изменено Androbim (12.07.2017 15:12:04)
Не в сети
Мастер SELECT INSTR(GROUP_CONCAT('[', LPAD(id, 10, 0), ']' ORDER BY score DESC SEPARATOR ''), '[0000000003]')
FROM t
WHERE score <= 20;
Идею понял, понравилась гибкость мышления, но не решается проблема, что два пользователя с одинаковым рейтингом должны занимать одно место.
Изменено covobo (12.07.2017 15:20:20)
Не в сети
Большое всем спасибо! Направление примерно понятно, пока заверстаю, подумаю :-)
Не в сети
Мастер
- что здесь не так? результат — 25
Смотря, что ты хотел получить в итоге.
В твоём случае получается такая строка с рейтингом:
[0000000003][0000000002][0000000001]
Понятно, т.к. top1 (id 3) идёт первым из-за рейтинга 50, дальше идут два top2, которые сортируются произвольно из-за одинакового рейтинга.
Соответственно, INSTR() возвращает правильный результат — ты ищешь id = 1, он третий по счёту, т.е. (25 — 1) / 12 = место №3.
- Делить по модулю на длину строки (’[0000000001]’)?
Без модуля, результат всегда целочисленный, т.к. все id имеют длину 12 символов (LPAD до 10 + две скобки).
- + не решается проблема, что два пользователя с одинаковым рейтингом должны занимать одно место.
Проблемы нет, как её и в твоём варианте нет. Если не хочется полагаться на поведение ORDER BY при одинаковых значениях, то просто добавляется второе поле, которое всегда уникально — тот же id. Например:
sqlORDER BY score DESC, descr, id.
Не в сети
Мастер Спасибо за ответ) Я не сразу увидел
(25 - 1) / 12 = 3
Проблемы нет, как её и в твоём варианте нет. Если не хочется полагаться на поведение ORDER BY при одинаковых значениях, то просто добавляется второе поле, например
Речь идет о другом, в group_concat будет строка '[0001][0002][0003]', дальше мы ищем нужную позицию для id = 3, подстрока начинается с 12ой позиции, а значит место - 3.
Автор хочет, чтобы люди с одинаковым рейтингом занимали одинаковую позицию.
Т.е. в случае если у id=2 и у id=3 - рейтинг 100, то они оба занимают второе место (допустим второе, если есть кто-то выше, главное, что все люди с одинаковым рейтингом занимают одну и ту же позицию).
Изменено covobo (12.07.2017 15:34:33)
Не в сети
Из вашего разговора сделал вывод, что дело еще и ресурсозатратное.
Может быть, структуру стоит изменить?
Может быть, оптимальным было бы запускать задачу по пересчету рейтинга?
Изменено Androbim (12.07.2017 15:43:36)
Не в сети
Мастер Из вашего разговора сделал вывод, что дело еще и ресурсозатратное. Может быть, структуру стоит изменить? Может быть, оптимальным было бы запускать задачу по пересчету рейтинга?
О проблемах ты знаешь, о своем приложении ты знаешь. Это решать только тебе.
Могу лишь сказать, что, да, чаще всего люди заморачиваются и фиксируют рейтинг за пользователем (пересчитывают), сводят к минимуму количество пересчетов, используют кэши и т.п., т.е. редко можно встретить, что позиция пользователя постоянно берется realtime из бд. Особенно если речь идет о большом объеме данных.
Изменено covobo (12.07.2017 15:57:56)
Не в сети
CREATE VIEW tmp AS
SELECT avg(mark) AS rating,
user_id
FROM users
JOIN marks ON users.id = marks.user_id
GROUP BY user_id
ORDER BY rating DESC;
SELECT * FROM tmp;
SET @position:= 0;
SELECT POSITION,
tmp.user_id,
rates.rating
FROM
(SELECT @position:=@position + 1 AS POSITION, rating
FROM tmp
GROUP BY rating) AS rates
JOIN tmp ON tmp.rating = rates.rating
ORDER BY POSITION ASC;
DROP VIEW tmp;Можно так
Не в сети
Мастер
- Автор хочет, чтобы люди с одинаковым рейтингом занимали одинаковую позицию.
В этом случае идея та же, только вместо [000id] используется [000score], а id не используется. То есть это не рейтинг пользователей (= уникальные id), а рейтинг рейтингов (= уникальные, гм, рейтинги).
sqlSELECT INSTR(GROUP_CONCAT(DISTINCT '[', LPAD(score, 10, 0), ']' ORDER BY score DESC SEPARATOR ''), '[0000000010]') FROM t WHERE score >= 10;
Общая мысль такая: любой рейтинг (leaderboard) это последовательность чисел; последовательность может быть как строковой, так и более сложной (рядами), но т.к. в MySQL нет функций для работы с рядами (rows), то составляется строковая последовательность через GROUP_CONCAT. А дальше, когда последовательность есть, в ней уже можно искать любой элемент, который представлен, к примеру, числом-рейтингом или числом-id.
Используя строковые функции можно одним запросом покрыть весьма сложные случаи. К примеру, запрос выше не возвращает списка id (в отличии от изначальной версии); это можно исправить, генерируя не [000score], а [000score-000id] и делая поиск по [000score-, и дальше возвращая не просто число, а всю подстроку. В итоге клиенту (PHP) остаётся только извлечь id между - и ].
sqlSELECT SUBSTR(j, 1, INSTR(j, '[0000000010-') - 1) FROM ( SELECT GROUP_CONCAT(DISTINCT '[', LPAD(score, 10, 0), '-', LPAD(id, 10, 0), ']' ORDER BY score DESC SEPARATOR '') FROM t WHERE score >= 10 ) sub
Однако в том случае можно натолкнуться на ограничение максимальной длины строки, возвращаемой GROUP_CONCAT (если не ошибаюсь, по умолчанию это 10 Кб). Его можно поднять настройкой в my.cnf.
- Может быть, оптимальным было бы запускать задачу по пересчету рейтинга?
Обычно оптимально не пересчитывать всё подряд по таймеру, а пересчитывать в момент изменения, т.к. изменяется только малый % строк (и тем меньше, чем их больше).
Если нагрузка по пересчёту большая (то есть не достаточно просто добавить/вычесть число из нужного столбца), то в очередь ставится задача по пересчёту конкретно данной строки.
Но что касается построения рейтинга, то это в любом случае весьма тяжёлая задача (если используется MySQL) и её нужно кэшировать, вне зависимости, каким образом составляется leaderboard. Благо, на весь сайт обычно один глобальный рейтинг, его можно даже в фоне считать, а не по запросу.
Не в сети
Большое всем спасибо еще раз!
Решил при помощи GROUP_CONCAT, предварительно создав такую вьюху, для "уникальности" участников:
CREATE VIEW rating_scores AS SELECT
AVG(score) AS avscore, competitor_id, nomination_id
FROM scores
WHERE is_actual = 1
GROUP BY competitor_id, nomination_id'А затем, к ней:
$ratingScores = DB::table('rating_scores')
->select(DB::raw('avscore, GROUP_CONCAT(competitor_id)'))
->where('nomination_id', $id) //параметр
->groupBy('avscore')
->orderBy('avscore', 'desc')
->get();
return $ratingScores;Результат (в первом элементе, как раз, одинаковые оценки):
Collection {#781 ▼
#items: array:3 [▼
0 => {#782 ▼
+"avscore": 6.1
+"GROUP_CONCAT(competitor_id)": "487,484"
}
1 => {#784 ▼
+"avscore": 1.5
+"GROUP_CONCAT(competitor_id)": "485"
}
2 => {#785 ▼
+"avscore": 1.4
+"GROUP_CONCAT(competitor_id)": "486"
}
]
}Не в сети
Однако, опыты продолжаются, и вот на чем остановился.
TRUNCATE TABLE rating_scores;
INSERT INTO rating_scores (competitor_id, nomination_id, avscore)
SELECT competitor_id, nomination_id, avg(score) as avscore
FROM scores
WHERE is_actual = 1
GROUP BY competitor_id, nomination_id
ORDER BY avscore descSET @position = 0;
SET @prev_avscore = 0;
SELECT competitor_id, avscore, if(@prev_avscore != avscore, @position := @position + 1, @position) as position, @prev_avscore := avscore
FROM rating_scores
WHERE nomination_id = 1
ORDER BY position В результате участники с одинаковыми оценками имеют одинаковые позиции.
'484', '6.10', '1', '6.10'
'487', '6.10', '1', '6.10'
'485', '1.50', '2', '1.50'
'486', '1.40', '3', '1.40'Не в сети
Мастер Не в сети
Мастер В результате участники с одинаковыми оценками имеют одинаковые позиции.
Так ты же это и просил, вот, здесь:
А если оценки одинаковые? Место-то, при этом одно...
По крайней мере я так понял.
Тогда вот:
Переменной.Решение для MySQL:
SET @position = 0;
SELECT a.* FROM (
SELECT id, @position := @position + 1
FROM MyUserTable
ORDER BY id desc
) as a WHERE a.id = 103;
Первый комментарий в этой ветке
Не в сети
Ну так я весьма вами благодарен :-)
Вот так получаем позицию участника.
SET @position = 0;
SET @prev_avscore = 0;
SELECT a.* FROM (
SELECT competitor_id, avscore, if(@prev_avscore != avscore, @position := @position + 1, @position) as position, @prev_avscore := avscore
FROM rating_scores
WHERE nomination_id = 1
ORDER BY position) as a
WHERE a.competitor_id = 484;Не в сети
В итоге вышло вот что.
public function rating()
{
// Полная очистка рейтинга
DB::table('rating_scores')->truncate();
//Подготовка данных для выстраивания рейтинга
$rows = DB::table('scores')
->select(DB::raw('competitor_id, nomination_id, avg(score) as avscore'))
->where('is_actual', '=', 1)
->groupBy('competitor_id')
->groupBy('nomination_id')
->orderBy('avscore', 'desc')
->get();
//Вставка
foreach ($rows as $row) {
DB::table('rating_scores')->insert(['competitor_id' => $row->competitor_id, 'nomination_id' => $row->nomination_id, 'avscore'
=> $row->avscore]);
}
//Построение рейтинга
//Получаем открытые номинации (чтобы не тратить ресурсы на закрытые)
$nominations = Nomination::where('is_actual', 1)->get();
// По каждой номинации считается рейтинг, используется алгоритм, предоставленный covobo
foreach ($nominations as $nomination) {
$ratings = RatingScore::where('nomination_id', $nomination->id)
->orderBy('avscore', 'desc')->get();
$position = 0;
$prev_score = 0;
foreach ($ratings as $rating) {
$rating_current = RatingScore::find($rating->id);
if ($prev_score != $rating_current->avscore) {
$position = $position + 1;
}
$rating_current->position = $position;
$prev_score = $rating_current->avscore;
$rating_current->save();
}
}
}
Изменено Androbim (21.07.2017 11:39:34)
Не в сети
Мастер 
что только люди не придумают, лишь бы редис не использовать
Androbim, попробуй так, для общего развития, представить сколько запросов будет генерировать твой метод и сколько памяти потреблять если нужно будет отранжировать, ну, хотя бы миллион записей…
Не в сети
есть момент:
юзер1 - 100очков
юзер2 - 80очков
юзер3 - 80очков
юзер4 - 80очков
юзер5 - 50очков
вы отображаете как
1 место - юзер1
2 место - юзер2,юзер3,юзер4
3 место - юзер5
собственно сам момент:
почему у юзер5 не 5-е место , а 3-е?
Не в сети
что только люди не придумают, лишь бы редис не использовать Androbim, попробуй так, для общего развития, представить сколько запросов будет генерировать твой метод и сколько памяти потреблять если нужно будет отранжировать, ну, хотя бы миллион записей…
Не думаю, что там когда-либо будет миллион строк, но дело не в этом, просто я про Redis не в курсе пока еще, впрочем, спасибо, обязательно посмотрю.
собственно сам момент:почему у юзер5 не 5-е место , а 3-е?
Потому что у предыдущих одинаковые оценки, тут в соответствии с постановкой, все верно. Логическая несостыковка? Хм... Как посмотреть, ведь у предыдущих - 2-е место.
Изменено Androbim (21.07.2017 16:06:34)
Не в сети
Универсальная вики-разметка
Работает на FluxBB (перевод Laravel.ru)