В моем последнем посте я представил свой недавний побочный проект: переосмысление оригинального flagvsflag.com Томаса Крома.

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

Как работает текущая стратегия

Сейчас я использую адаптацию QuickSort со следующим алгоритмом:

function flagSort(db : *sql.DB, scheduler *scheduler) {
    function refreshAll(iLeft : int, iPivot : int, iRight : int) : (ID, ID, ID) {
        returns the flag ID's corresponding to the given indices
    }
function swapPositions(a : flags.ID, b : flags.ID) {
        swap the positions in the overall ranking for the two flags
    }
    function queueUpComparisons(iLeft : int, iRight : int) {
        l = iLeft
        iPivot = (iLeft + iRight) / 2
        _, oldPivot, oldRight = refreshAll(iLeft, iPivot, iRight)
        for l < iRight:
            if l == iPivot:
                l++
                continue
            left, pivot, right = refreshAll(l, iPivot, iRight)
            // detect if elements at iPivot & iRight have changed
            if right != oldRight || pivot != oldPivot:
                l = iLeft
            oldPivot = pivot
            oldRight = right
            continue
            scheduler.RequestComparison((left, pivot), PMarginal)
            wait for the request to be filled
            l++
    }
    function quickSort(iLeft : int, iRight : int, readyToStart: chan bool, done : chan bool) {
        defer { done <- true }
        constant iCenter = (iLeft + iRight) / 2
        // eagerly start requesting comparisons for the left and right sub routines
        go queueUpComparisons(iLeft, iCenter)
        go queueUpComparisons(iCenter + 1, iRight)
        
        <-readyToStart // wait for the start signal
        
        startedLeft, startedRight = false
        isDoneLeft, isDoneRight = make 2 boolean channels
        readyForLeft, readyForRight = make 2 boolean channels
        go quickSort(iLeft, iCenter, readyForLeft, isDoneLeft)
        go quickSort(iCenter + 1, iRight, readyForRight, isDoneRight)
        l = iLeft
        r = iRight
        for l < r:
            left, pivot, right = refreshAll(l, iCenter, r)
            if l == iCenter:
                l++
                continue
            var cmp : int
            // want to keep requesting comparison until it's nonzero
            for abs(cmp = flags.GetComparison(db, left, pivot)) < 1:
                scheduler.RequestComparison((left, pivot), PHigh)
                wait for the request to be filled
            if cmp > 0:
                swapPositions(left, right)
                r--
                left, pivot, right = refreshAll(l, iCenter, r)
            else:
                l++
                left, pivot, pivot = refreshAll(l, iCenter, r)
            if l > iCenter && !startedLeft:
                startedLeft = true
                readyForLeft <- true
            if r < iCenter && !startedRight:
                startedRight = true
                readyForRight <- true
        if !startedLeft:
            readyForLeft <- true
        if !startedRight:
            readyForRight <- true
        increment the global count of sort iterations completed
        // wait on the children to finish running
        <-isDoneLeft
        <-isDoneRight
        return
    left, pivot, right = select the first, center, and last flags by current state of the leaderboard
    done, readyToStart = make two boolean channels
    go quickSort(left, right, readyToStart, done)
    readyToStart<-true // signal that we're ready to start sorting
    <-done // wait to be done with quickSort
    // recurse. we shouldn't run out of stack space because this
    // should happen super rarely
    flagSort(db, scheduler)
}

Тот факт, что для тщательного описания этого алгоритма требуется так много псевдокода, является достаточной причиной для его изменения. Однако у него есть еще несколько проблем, которые появились в производстве:

  1. Постановка запросов на сравнение в очередь была очень сложной в реализации и на самом деле не решала проблему повторяемости вообще. Вместо того, чтобы сравнивать один опорный элемент с каждым другим элементом 200 раз подряд, вы просто чередуете сравнение нескольких элементов с каждым другим элементом, что не является большим улучшением.
  2. Отдельный плохой агент все еще может иметь огромное влияние на рейтинг, поскольку одно голосование может определить, попадет ли флаг в верхний или нижний квартиль. Это можно исправить, увеличив степень допустимых сравнений, но это также увеличило бы повторение до недопустимого уровня.
  3. Добавление нового флага в список (как вы помните, это проблема, к которой я недавно начал приближаться) не будет учитываться до тех пор, пока не будет завершена вся flagSort итерация, что означает, что перед новым флагом будет выполнено как минимум nlog(n) сравнений. даже появляется. В n>200 это 1500 сравнений. Неприемлемо!
  4. Это было бы чрезвычайно сложно масштабировать до нескольких экземпляров.

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

Претенденты

Еще в моем первом посте о REFlagVsFlag я упомянул MergeSort и простую систему ранжирования в качестве возможных стратегий. Здесь я примерно опишу, как каждый из них будет реализован.

Сортировка слиянием

MergeSort имеет многие из тех же преимуществ, что и QuickSort, а также некоторые другие:

  1. Эффективный, требующий идеального количества сравнений.
  2. Элементы могут быстро перемещаться по рейтингу.
  3. Важно: MergeSort будет менее повторяющимся, чем QuickSort. Ближе к концу сортировки, когда объединяются большие списки, мы можем увидеть несколько более длинных циклов повторяющихся сравнений, но они не должны быть такими плохими, как повторяющиеся последовательности, наблюдаемые в QuickSort.

Одна из причин, по которой я сомневаюсь в использовании MergeSort, связана с проблемой реализации: таблица лидеров представлена ​​путем связывания индекса в списке с каждым элементом, в дополнение к уникальному идентификатору элемента. Первоначально это было сделано для того, чтобы сделать мой выбор алгоритмов более гибким, поскольку я мог адаптировать алгоритмы на основе массивов и очень быстро получать доступ к положению изображения в таблице лидеров. Однако проблема в том, что моя таблица имеет только одно индексное поле, а большинство реализаций MergeSort требуют создания временных подсписков, а встроенная версия алгоритма оказывается на удивление нетривиальной. Однако мне бы очень хотелось попробовать эту нетривиальную реализацию хотя бы для того, чтобы вырасти как разработчик.

Общие проблемы с алгоритмами сортировки списка

По нескольким причинам я пришел к выводу, что обычные алгоритмы сортировки списка могут быть совершенно неподходящими для этой задачи, хотя после этого я обязательно буду реализовывать MergeSort на месте.

  1. Большинство общих алгоритмов сортировки списка полагаются на то, что список не увеличивается во время сортировки, и, поскольку я хотел бы, чтобы REFlagVsFlag поддерживал флаги, отправленные пользователем, это действительно убийца сделки.
  2. Сложность: в своей реализации QuickSort я обнаружил, что это совсем не так, как кажется, просто впихнуть обычный алгоритм сортировки в сложное приложение, удовлетворяя при этом второстепенные требования.

Рейтинговая система Эло

Рейтинговые системы Elo популярны в соревновательных играх, подобных турнирам, таких как шахматы, League of Legends и DotA, поэтому кажется, что они идеально подходят для REFLagVsFlag. Я хотел бы использовать эту стратегию, потому что:

  1. Я никогда раньше не внедрял систему Эло.
  2. Проблемы, присущие обычным алгоритмам сортировки списка, упоминались выше.

Выполнение

Во-первых, мне нужно добавить столбец в мою таблицу флагов для хранения очков Эло:

ALTER TABLE images ADD COLUMN elo REAL NOT NULL DEFAULT(1000.0)

Значение по умолчанию не должно иметь большого значения, потому что оно должно быть приведено в нормальный диапазон довольно быстро.

Большинство интересных изменений коснется алгоритма планирования, которому теперь нужно будет все делать самому, поскольку он не может полагаться на запросы от подпрограммы сортировки.

В настоящее время, когда вызывается обработчик конечной точки /judge, он вызывает scheduler.NextRequest(user's remote IP address) для получения следующей пары флагов. Я изменю тело NextRequest, чтобы вращаться вокруг этих команд SQL:

  1. Выберите изображение с наименьшим «нагревом» для текущего пользователя (обозначено $1), где «нагрев» представляет собой общее количество сопоставлений, в которых изображение было оценено пользователем:
    SELECT id, COALESCE(views.heat, 0) + COALESCE(images.heat, 0) as s_heat FROM views, images WHERE “user” = $1 GROUP BY (id, s_heat) ORDER BY s_heat ASC LIMIT 1;
  2. Случайным образом выберите один из десяти элементов с ближайшим значением Эло, где $1 – это показатель Эло для выбранного выше элемента:
    SELECT id FROM (SELECT * FROM images ORDER BY ABS(elo-$1) ASC LIMIT 10) tbl ORDER BY RANDOM() LIMIT 1;
  3. Добавьте запрос в таблицу расписания в базе данных:
    INSERT INTO schedule (fst, snd, user) VALUES ($1, $2, $3) с очевидными $1, $2 и $3.
  4. После того, как пользователь проголосовал и доставил пару идентификаторов (winner, loser) (планировщик видит это как вызываемый метод scheduler.FillRequest(winner, loser)), мы сначала проверяем, действительно ли планировщик запросил этот запрос (чтобы предотвратить группирование), затем мы обновляем соответствующий Эло использует формулу из этой записи в блоге:
    Сначала вычислите преобразованные рейтинги для двух элементов (в Go):
    r1 := math.Pow1o(elo1 / 400)
    r2 := math.Pow10(elo2 / 400)
    Затем вычислите ожидаемый счет для каждого флага:
    e1 := r1 / (r1 + r2)
    e2 := r2 / (r1 + r2)
    Далее мы просто устанавливаем счет:
    s1 := 0 если флаг 1 проигран, 1 если он выигран
    s2 := 1 — s1
    Наконец, мы обновим фактические Эло в таблице (код SQL):
    Пусть $1 будет s1, $2 будет e1, а $3 будет идентификатором первого флага в UPDATE images SET elo = elo + 32 * ($1 — $2) WHERE id = $3
    Пусть $1 будет s2, $2 будет e2, а $3 будет идентификатором второго флага в том же запросе.

Конечно, я не хотел тратить ~2000 голосов, которые уже были отданы, поэтому я использовал функцию PL/SQL, чтобы воспроизвести их по всей базе данных с новой системой Elo:

CREATE FUNCTION playAllVotes() RETURNS VOID AS $$
DECLARE
  r1 REAL := 0.0;
  r2 REAL := 0.0;
  s1 REAL := 0.0;
  s2 REAL := 0.0;
  e1 REAL := 0.0;
  e2 REAL := 0.0;
  elo1 REAL := 0.0;
  elo2 REAL := 0.0; winner INT; loser INT;
BEGIN
  FOR winner, loser IN SELECT votes.winner, votes.loser FROM votes LOOP
    elo1 := (SELECT elo FROM images WHERE id = winner);
    elo2 := (SELECT elo FROM images WHERE id = loser);
    r1 := 10.0 ^ (elo1 / 400);
    r2 := 10.0 ^ (elo2 / 400);
    e1 := r1 / (r1 + r2);
    e2 := r2 / (r1 + r2);
    s1 := 1.0;
    s2 := 0.0;
    elo1 := elo1 + 32.0 * (s1 - e1);
    elo2 := elo2 + 32.0 * (s2 - e2);
    UPDATE images SET elo = elo1, heat = heat + 1 WHERE id = winner;
    UPDATE images SET elo = elo2, heat = heat + 1 WHERE id = loser; RAISE NOTICE 'Ran vote on % and %', winner, loser;
  END LOOP;
  RETURN;
END
$$ LANGUAGE plpgsql VOLATILE;

Результаты

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