Мы здесь в Spotify серьёзно относимся к фидбеку от пользователей. Какое-то время назад мы заметили, что пользователи жалуются на то, что при включенном режиме случайного перемешивания плейлиста порядок песен на самом деле не случаен — например, несколько песен одного и того же исполнителя могут быть воспроизведены одна за другой, при том, что в плейлисте множество песен разных исполнителей. Пользователи спрашивали неужели мы не способны сделать такую простую вещь, как случайный порядок воспроизведения треков? Мы отвечали «Он правда-правда случаен! Мы проверяли!»
Так кто же был прав — мы или пользователи? Как оказалось — и мы, и они. Ну и вообще дело обстояло значительно серьёзнее, чем казалось на первый взгляд.
Ещё в самом первом релизе нашего плеера в нём была функция случайного перемешивания плейлиста. Мы использовали для этого алгоритм Фишера-Йетса — и он давал идеально случайное перемешивание. Но что такое «идеально случайное»? Это значит, например, что мы можем получить один из двух нижеуказанных порядков песен с одинаковой вероятностью (разные цвета означают треки разных исполнителей):
Кстати, личное мнение: алгоритм Фишера-Йетса является одним из наиболее элегантных из известных мне алгоритмов. Это просто поразительно, как столь непростая задача может быть решена в 3 строчки кода, дать при этом верный результат и выполнить минимально необходимое количество операций.
Сначала мы не понимали, что именно нам пытались сказать пользователи своими жалобами на «не случайность». Но после вдумчивого чтения комментариев мы поняли, что людям не нравится ситуация, когда подряд играют несколько песен одного и того же исполнителя. И даже не просто «подряд», а когда, например, на 5 воспроизведённых песен 3 принадлежат одному автору (даже если между ними играли другие песни). Люди считали это явным нарушением случайности.
Общеизвестно, что люди иногда серьёзно ошибаются в интуитивном восприятии вероятностей. Представьте, что каждый день на работе вы подбрасываете монетку, чтобы решить, что будете сегодня есть на обед — тайскую еду или индийскую. В первый 4 дня монетка выбрала тайскую. И вот в пятницу вы думаете «так, 4 дня монетка выбирала одно и тоже, ну, сегодня точно будет индийская еда!». И снова выпадает тайская. Дело в том, что у монетки нет памяти, она «не знает», что она выбирала вчера и совершенно не учитывает это при сегодняшнем своём «решении». Миллионный бросок имеет такие же шансы на выпадения орла или решки, как и первый — 50%.
Или вот другой пример: люди думают, что если сыграли несколько раз в лотерею и не выиграли, то в следующий раз у них больший шанс что-то выиграть. Этот феномен называется заблуждением игрока, и он применим и для лотереи, и для вышеописанного случая с монеткой и выбором еды.
Давайте вернёмся к нашим пользователям, которые тоже люди, а значит не менее остальных подвержены заблуждению игрока. Если вы только что прослушали песню какого-то исполнителя, а в вашем плейлисте есть и другие его песни, то у этих песен при случайном перемешивании плейлиста есть полное право попасть на следующую позицию в плейлисте. Они ничем не хуже других песен.
Но, как говорится — «клиент всегда прав». И мы решили подумать о том, как изменить наш алгоритм перемешивания таким образом, чтобы его «случайность» была достаточно хорошей не с математической, а с психологической точки зрения. Поскольку идеальная математическая случайность не выглядит для людей достаточно случайной.
Задача выглядела как нечто, что уже должно было быть решено кем-то раньше. И действительно, мы нашли статью "Искусство перемешивания музыки", которую написал Martin Fiedler и где решается примерно та же проблема. Однако, описанный в ней алгоритм был переусложнён и иногда работал слишком медленно, так что мы модифицировали его в соответствии с нашими задачами:
Главная идея похожа на «встряхивание». Представьте, что у нас есть картинка, нарисованная в оттенках серого цвета (их несколько сотен):
Мы хотим упростить картинку, преобразовав её к черно-белому спектру (использовать только чисто чёрные и чисто белые пиксели). Это можно сделать так: если в сером пикселе более 80% чёрного — он получает шанс в 80% стать чисто чёрным и 20% стать чисто белым. Мы обрабатываем пиксели по одному и для каждого определяем новый цвет по вышеописанному правилу. Результат, конечно, будет чем-то напоминать оригинал, но всё же нельзя сказать, что получилось хорошо:
Как вы можете заметить, чёрные пиксели сбились в кластеры, плюс образовались большие белые промежутки между ними. Было бы лучше, если бы группы чёрных и белых пикселей были меньше и распределены более равномерно. Для этого можно использовать другой алгоритм, например, Флойда-Штейнберга:
Кластеры, хорошо заметные на предыдущей картинке, пропали. Мы можем использовать идеи данного алгоритма и в нашей задаче по перемешиванию песен. Это позволит нам избежать сбивания песен одного исполнителя в кластеры — мы постараемся распределить их по всему плейлисту. Давайте представим, что у нас есть плейлист, состоящий из песен таких исполнителей, как The White Stripes (красный цвет на рисунке), The xx (чёрный), Bonobo (зелёный), Britney Spears(розовый) и Jaga Jazzist (оранжевый). Мы возьмём песни каждого из исполнителей и постараемся «размазать» их по плейлисту. Картинка лучше тысячи слов:
Как вы можете заметить, песни каждого исполнителя распределены достаточно далеко друг от друга и человеческому глазу такой порядок плейлиста выглядит идеально случайным (хотя таковым и не является). Давайте посмотрим детальнее на то, как работает алгоритм.
Пусть у нас есть 4 песни исполнителя The White Stripes (как на картинке выше). Это означает, что каждая из песен должна попасть примерно в каждые 25% общей продолжительности плейлиста. Мы распределяем 4 песни на расстоянии от 20% до 30% друг от друга (так выглядит «случайнее»). Видите, расстояния между красными кружками на линии не одинаковы. В начале мы добавляем случайный отступ, иначе первые песни каждого исполнителя попадут в точку 0 на линии. Вы можете заметить, что у Britney Spears и Jaga Jazzist есть всего по одной песне, но случайное стартовое смещение помещает их в случайное место плейлиста. Мы также перетасовываем песни одного исполнителя друг относительно друга (здесь сойдёт и старый алгоритм Фишера-Йетса, хотя можно и рекурсивно применить наш новый алгоритм если мы, например, захотим распределить песни из разных альбомов так же равномерно, как мы распределяем песни разных исполнителей).
Сейчас алгоритм уже используется нашими плеерами на всех платформах. Спасибо всем пользователям, которые хорошо описали свои проблемы, касающиеся случайности плейлистов.
Так кто же был прав — мы или пользователи? Как оказалось — и мы, и они. Ну и вообще дело обстояло значительно серьёзнее, чем казалось на первый взгляд.
Наш точка зрения
Ещё в самом первом релизе нашего плеера в нём была функция случайного перемешивания плейлиста. Мы использовали для этого алгоритм Фишера-Йетса — и он давал идеально случайное перемешивание. Но что такое «идеально случайное»? Это значит, например, что мы можем получить один из двух нижеуказанных порядков песен с одинаковой вероятностью (разные цвета означают треки разных исполнителей):
Кстати, личное мнение: алгоритм Фишера-Йетса является одним из наиболее элегантных из известных мне алгоритмов. Это просто поразительно, как столь непростая задача может быть решена в 3 строчки кода, дать при этом верный результат и выполнить минимально необходимое количество операций.
Заблуждение игрока
Сначала мы не понимали, что именно нам пытались сказать пользователи своими жалобами на «не случайность». Но после вдумчивого чтения комментариев мы поняли, что людям не нравится ситуация, когда подряд играют несколько песен одного и того же исполнителя. И даже не просто «подряд», а когда, например, на 5 воспроизведённых песен 3 принадлежат одному автору (даже если между ними играли другие песни). Люди считали это явным нарушением случайности.
Общеизвестно, что люди иногда серьёзно ошибаются в интуитивном восприятии вероятностей. Представьте, что каждый день на работе вы подбрасываете монетку, чтобы решить, что будете сегодня есть на обед — тайскую еду или индийскую. В первый 4 дня монетка выбрала тайскую. И вот в пятницу вы думаете «так, 4 дня монетка выбирала одно и тоже, ну, сегодня точно будет индийская еда!». И снова выпадает тайская. Дело в том, что у монетки нет памяти, она «не знает», что она выбирала вчера и совершенно не учитывает это при сегодняшнем своём «решении». Миллионный бросок имеет такие же шансы на выпадения орла или решки, как и первый — 50%.
Или вот другой пример: люди думают, что если сыграли несколько раз в лотерею и не выиграли, то в следующий раз у них больший шанс что-то выиграть. Этот феномен называется заблуждением игрока, и он применим и для лотереи, и для вышеописанного случая с монеткой и выбором еды.
Давайте вернёмся к нашим пользователям, которые тоже люди, а значит не менее остальных подвержены заблуждению игрока. Если вы только что прослушали песню какого-то исполнителя, а в вашем плейлисте есть и другие его песни, то у этих песен при случайном перемешивании плейлиста есть полное право попасть на следующую позицию в плейлисте. Они ничем не хуже других песен.
Но, как говорится — «клиент всегда прав». И мы решили подумать о том, как изменить наш алгоритм перемешивания таким образом, чтобы его «случайность» была достаточно хорошей не с математической, а с психологической точки зрения. Поскольку идеальная математическая случайность не выглядит для людей достаточно случайной.
Алгоритм
Задача выглядела как нечто, что уже должно было быть решено кем-то раньше. И действительно, мы нашли статью "Искусство перемешивания музыки", которую написал Martin Fiedler и где решается примерно та же проблема. Однако, описанный в ней алгоритм был переусложнён и иногда работал слишком медленно, так что мы модифицировали его в соответствии с нашими задачами:
Главная идея похожа на «встряхивание». Представьте, что у нас есть картинка, нарисованная в оттенках серого цвета (их несколько сотен):
Мы хотим упростить картинку, преобразовав её к черно-белому спектру (использовать только чисто чёрные и чисто белые пиксели). Это можно сделать так: если в сером пикселе более 80% чёрного — он получает шанс в 80% стать чисто чёрным и 20% стать чисто белым. Мы обрабатываем пиксели по одному и для каждого определяем новый цвет по вышеописанному правилу. Результат, конечно, будет чем-то напоминать оригинал, но всё же нельзя сказать, что получилось хорошо:
Как вы можете заметить, чёрные пиксели сбились в кластеры, плюс образовались большие белые промежутки между ними. Было бы лучше, если бы группы чёрных и белых пикселей были меньше и распределены более равномерно. Для этого можно использовать другой алгоритм, например, Флойда-Штейнберга:
Кластеры, хорошо заметные на предыдущей картинке, пропали. Мы можем использовать идеи данного алгоритма и в нашей задаче по перемешиванию песен. Это позволит нам избежать сбивания песен одного исполнителя в кластеры — мы постараемся распределить их по всему плейлисту. Давайте представим, что у нас есть плейлист, состоящий из песен таких исполнителей, как The White Stripes (красный цвет на рисунке), The xx (чёрный), Bonobo (зелёный), Britney Spears(розовый) и Jaga Jazzist (оранжевый). Мы возьмём песни каждого из исполнителей и постараемся «размазать» их по плейлисту. Картинка лучше тысячи слов:
Как вы можете заметить, песни каждого исполнителя распределены достаточно далеко друг от друга и человеческому глазу такой порядок плейлиста выглядит идеально случайным (хотя таковым и не является). Давайте посмотрим детальнее на то, как работает алгоритм.
Пусть у нас есть 4 песни исполнителя The White Stripes (как на картинке выше). Это означает, что каждая из песен должна попасть примерно в каждые 25% общей продолжительности плейлиста. Мы распределяем 4 песни на расстоянии от 20% до 30% друг от друга (так выглядит «случайнее»). Видите, расстояния между красными кружками на линии не одинаковы. В начале мы добавляем случайный отступ, иначе первые песни каждого исполнителя попадут в точку 0 на линии. Вы можете заметить, что у Britney Spears и Jaga Jazzist есть всего по одной песне, но случайное стартовое смещение помещает их в случайное место плейлиста. Мы также перетасовываем песни одного исполнителя друг относительно друга (здесь сойдёт и старый алгоритм Фишера-Йетса, хотя можно и рекурсивно применить наш новый алгоритм если мы, например, захотим распределить песни из разных альбомов так же равномерно, как мы распределяем песни разных исполнителей).
Заключение
Сейчас алгоритм уже используется нашими плеерами на всех платформах. Спасибо всем пользователям, которые хорошо описали свои проблемы, касающиеся случайности плейлистов.
