← Журнал
Jiva Studio

День, когда повторения свалились в кучу

Классические интервальные повторения называют идеальный день для каждого стиха. Следуйте им буквально — и во вторник получите шестьдесят карточек, а в среду четыре. Вот небольшая хитрая правка: она разносит нагрузку и не ломает математику.

Учи ШлокиSpaced RepetitionAlgorithmsEngineering

В прошлой статье мы собрали планировщик Учи Шлоки на основе кривой забывания. Это урезанный SM-2: для каждого известного стиха он считает последний дешёвый день, когда его ещё стоит повторить, пока стих не забылся. Алгоритм честный, математика чистая. Но если следовать ему буквально, рано или поздно он испортит кому-нибудь вторник.

Это история про тот вторник и про двадцать строк, которые его починили.

Откуда берётся завал

SM-2 работает с одной карточкой. Он смотрит на стих, на лёгкость, на последний интервал — и называет один идеальный день. О соседнем стихе он ничего не знает. Для одной карточки это нормально, а для целой колоды тихо губительно: настоящая практика идёт комками.

Представьте вдохновлённое утро. За один присест вы выпускаете пять новых шлок. Каждая порождает пару карточек на воспроизведение (стих по номеру, перевод, разные направления, в которых вас будут проверять), и SM-2, безупречно делая своё дело, назначает каждую на очевидный первый интервал — на завтра. Десять карточек падают на один день. Повторите так неделю — и комки нарастают: несколько десятков карточек, выпущенных вместе, теперь движутся во времени одной колонной и всегда подходят к сроку в одни и те же дни. Ученик открывает приложение во вторник — шестьдесят повторений, в среду — четыре. На каждой отдельной карточке алгоритм прав. А по ощущениям всё выходит комковато и уныло.

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

Зацепка: день шире точки

Разгадка проста: «идеальный день» SM-2 — вовсе не точка. У вершины кривая забывания пологая. При интервале около 24 дней повторение на 23-й или 25-й день меняет вероятность припоминания на ошибку округления. «Нужный день» — это на самом деле небольшая окрестность почти равноценных дней. А внутри окрестности выбор за вами — так берите наименее загруженный день.

Планирование превращается в задачу размещения. Для каждой карточки берём окно дней вокруг цели SM-2, смотрим, сколько карточек уже подходит к сроку в каждый из них, и кладём карточку в самый пустой. Толпа выравнивается сама, и ни одна карточка не уходит больше чем на день-два от того места, куда её звала математика.

Окно намеренно перекошено

Вот первое неочевидное решение. Окно несимметрично. В прошлое оно тянется дальше, чем в будущее:

// reviewDueAt(): the search window around the SM-2 target day
const kBack = Math.max(2, Math.round(intervalDays * 0.075)) // ~7.5% of the interval
const kForward = 3                                          // capped, always small

В асимметрии зашит факт о кривой, который симметричное окно упустило бы: рано — дёшево, поздно — опасно. Повторить стих за день до идеального момента почти ничего не стоит: вспоминаете чуть легче, интервал почти не укорачивается. Повторить на день позже — значит, стих, возможно, уже перешёл в забытые, а провал — самое дорогое, что бывает с карточкой: он сбрасывает интервал и сильнее всего срезает лёгкость. Поэтому окно клонится назад. Карточку с интервалом 24 дня оно сдвинет вперёд на round(24 × 0.075) ≈ 2 дня, если там свободнее, но назад отодвинет самое большее на три дня — и не более. Дешёвыми днями мы платим за дорогие.

graph LR
    B2["−2"] --- B1["−1"] --- T["целевой день"] --- F1["+1"] --- F2["+2"] --- F3["+3"]
    T -.->|"kBack: до ~7.5% интервала"| B2
    T -.->|"kForward: ограничено тремя"| F3

Ничьи и кости, которые мы держим предсказуемыми

Внутри окна правило простое: берём день с наименьшей нагрузкой. Но на минимуме часто оказывается сразу несколько дней, а в начале свежей колоды таких — большинство. Если бы мы всегда разрешали ничью одинаково (скажем, «побеждает самый ранний»), то две родственные карточки, выпущенные подряд, сделали бы один и тот же выбор и снова сбились бы в кучу в тот самый день, от которого мы их растаскивали. Поэтому ничью решает случай — но с двумя хитростями.

// chooseDueDay(): least-loaded day in the window, random among ties
let chosen = windowStart, seen = 0
const considerDay = (day) => {
  if ((dayLoadCounts.get(day) ?? 0) !== minLoad) return
  seen += 1
  if (seen === 1 || rng() < 1 / seen) chosen = day   // reservoir sampling
}
if (targetInWindow) considerDay(target)               // target gets seat #1
for (const day of window) if (day !== target) considerDay(day)

Во-первых, это резервуарная выборка: один проход по ничейным дням, каждый заменяет текущий выбор с вероятностью 1/seen. В итоге все дни равновероятны, а знать заранее их число не нужно. Во-вторых, целевой день SM-2 предлагается первым — он занимает «место №1». Сместить выбор может только строго меньшая нагрузка, поэтому простая ничья не собьёт карточку с идеального дня. Балансировка нагрузки работает только как способ разбить ничью и никогда не спорит с математикой. Отклонение от учебникового SM-2 по устройству минимально.

rng передаётся снаружи, а не берётся из глобального. В продакшене это Math.random, в тестах — генератор с фиксированным зерном. Так поведение, случайное по замыслу, остаётся в точности воспроизводимым, когда по нему нужно писать проверки. Случайность там, где выигрывает пользователь; предсказуемость там, где её требует тест.

Пакетный баг, спрятанный в «уже подходит к сроку»

Всё держится на карте дневной нагрузки — «сколько карточек подходит к сроку в каждый день». Слой приложения запрашивает её один раз, одним индексированным GROUP BY по таблице воспроизведения. Дёшево и правильно — но с одной ловушкой.

Когда вы выпускаете пять стихов разом, их карточки размещаются в цикле внутри одной транзакции, которая ещё не зафиксирована. Спросите нагрузку у базы — и каждая карточка в пакете увидит один и тот же снимок, сделанный до пакета: ноль в каждый день. И все они «сбалансируются» на один и тот же пустой вторник. Мы бы заново построили завал внутри той самой процедуры, что должна его предотвращать.

Решение — считать карту нарастающим счётчиком, а не готовым фактом:

const load = await fetchRecallDayLoadCounts(...)   // one GROUP BY, the snapshot
for (const card of graduating) {
  const due = placeOnLeastLoadedDay(card, load)
  load.set(due, (load.get(due) ?? 0) + 1)          // book the seat in memory
}

Каждое размещение увеличивает карту в памяти до того, как посмотрит следующая карточка. Поэтому внутри пакета карточки видят брони друг друга, хотя базы данных ещё ничто не коснулось. Задним умом это очевидно. Но такой баг вылезает только под той самой нагрузкой, ради которой всё и писалось.

Переключатель — для тех, кому нужна голая математика

Всё это скрыто за одним переключателем — evenOutDailyLoad, включён по умолчанию, в разделе Settings → Progress. Выключите его — и каждая карточка ляжет ровно на свой день по SM-2: предсказуемо и с той самой кучностью, с которой мы начинали. Кто-то так и хочет: любит редкое честное расписание и не боится тяжёлого дня. Большинство переключатель не трогает — и вторника с шестьюдесятью карточками не видит.

Чему это учит

Интересна тут вовсе не математика SM-2: она устоялась, ей сорок лет, и она хорошо описана. Интересен стык между правильным поэлементным алгоритмом и человечной работой со всей колодой. Этим стыком оказалась горстка чистых функций: перекошенное окно, которое знает, что рано дешевле, чем поздно; разбиение ничьей, которое добавляет случайности, но сохраняет воспроизводимость; и нарастающий счётчик, переживающий целый пакет. Пара десятков строк между учебником и человеком следят за тем, чтобы правильный ответ ещё и ощущался правильным.

Часть проекта

Учи Шлоки

Открыть проект