Один із найпопулярніших способів відтворення музики – випадковий вибір чергового треку. Здавалося б, у цьому немає жодної проблеми – уже давно написані такі генератори випадкових чисел, які максимально можливі без використання спеціальних апаратних генераторів рандому. Але відомий музичний стримінговий сервіс Spotify стикнувся зі скаргами користувачів. Користувачі хотіли рандом, але не справжній рандом, а більш приємний рандом.
Користувачі Spotify запитували: «Чому ваше тасування не є випадковим?». У сервісі дивувалися, адже треки в плейлистах відтворювалися у випадковому порядку.
Так хто був правий? Як виявилося, і Spotify, і користувачі мали рацію, але все трохи складніше.
Яким було випадкове відтворення треків у Spotify
З моменту запуску служби Spotify використовувалося перемішування Фішера-Єйтса, щоб створити ідеально випадкове перетасування списку відтворення.
Однак абсолютно випадковий означає, що наступні події жодним чином не пов’язані з попередніми.
При справді випадковому відтворенні цілком можливо, що користувачу доведеться прослухати треки альбому послідовно один за одним. Звісно, ймовірність цього надзвичайно низька. Зате буденною справою є відтворення двох чи трьох пісень одного автора.
Помилка гравця
Спочатку у Spotify не розуміли, що користувачі намагалися сказати, кажучи, що випадкове відтворення треків не є випадковим. Але потім інженери сервісу уважніше прочитали коментарі та помітили, що деякі люди не хочуть, щоб один і той самий артист грав два або три рази протягом короткого періоду часу.
Відомо, що ми, люди, іноді погано оцінюємо ймовірності. Припустімо, що ви щодня на роботі підкидаєте монету, щоб вирішити, де обідати. Перші чотири дні тижня монета вирішила, що вам варто їсти тайську їжу, а ви віддаєте перевагу індійській. Ви можете подумати: «Цього тижня монета чотири рази вирішувалась на користь тайської, сьогодні вона має бути індійською».
Якщо ви думаєте, що монета має більшу ймовірність прийняти рішення за індіанців у п’ятницю, ви помиляєтеся. Кинути монету в мільйонний раз – все одно, що кинути її впершеЗвичайна монета не має пам’яті, не знає, хто її кинув і т.д. Отже, і орел, і решка мають однакову ймовірність випасти у п’ятницю – 50% [примітка перекладача: нещодавнє дослідження з підкидуванням монетки понад 300 тис. разів показало, що монетка не падає абсолютно випадково. Вона частіше опиняється на тому боці, з якого її кидали].
Інший приклад: люди часто думають, що якщо вони не виграли нічого в лотерею зі скретч-картками кілька разів поспіль, у них має бути більше шансів виграти зараз. Це явище називається помилкою гравця, і це та сама помилка, яка призвела до помилки щодо тайської/індійської кухні.
Користувачі Spotify також стали жертвами помилки гравця. Якщо ви щойно почули пісню від певного виконавця, це не означає, що наступна пісня, швидше за все, буде від іншого виконавця в абсолютно випадковому порядку.
Користувач завжди правий і Spotify редагує випадковість
Однак стара приказка говорить, що користувач завжди правий, тому у Spotify вирішили знайти способи змінити наш алгоритм випадкового тасування треків, щоб користувачі були щасливішими. У Spotify дізналися, що юзери не люблять абсолютної випадковості.
Здавалося, що це проблема, яку мав вирішити хтось інший раніше. Дійсно, знайшлася публікація в блозі « Мистецтво тасування музики» Мартіна Фідлера, яка вирішує ту саму проблему.
Однак його алгоритм складний і може бути дуже повільним у деяких випадках, тому програмісти Spotify змінили його, щоб краще відповідати потребам сервісу.
Основна ідея дуже схожа на методи, що використовуються в дизерінгу. Припустимо, у нас є чорно-біле зображення, яке використовує кілька сотень відтінків сірого.
Ми хотіли б ще більше спростити зображення, використовуючи лише пікселі двох кольорів, чорний і білий. Ми могли б використати випадкову вибірку: скажімо, піксель має 80% відтінку сірого, тоді він матиме 80% шансів стати чорним і 20% шансів стати білим. Ми обробляємо пікселі один за одним і для кожного випадковим чином визначаємо новий колір на основі вихідного відтінку сірого. Однак результат дуже далекий від задовільного.
Як бачите, чорні пікселі утворюють кластери, а також є великі білі плями. Було б краще, якби чорні та білі плями були розподілені рівномірніше. Інші алгоритми, такі як дизерінг Флойда-Штейнберга, уникають кластерів і дають набагато кращі результати. Майже повністю зникли кластери, які ми бачили на попередньому знімку.
Ми можемо черпати натхнення з алгоритмів згладжування, щоб вирішити нашу проблему з кластерами пісень одного виконавця, спробувавши розповсюдити їх по всьому плейлисту.
Припустімо, у нас є список відтворення, що містить кілька пісень The White Stripes, The xx, Bonobo, Britney Spears (Toxic!) і Jaga Jazzist. Для кожного артиста ми беремо його пісні і намагаємося максимально рівномірно розтягнути їх по всьому плейлисту. Потім ми збираємо всі пісні та впорядковуємо їх за позицією.
Як бачите, пісні від виконавця добре розподілені, і це виглядає досить випадковим для людського ока.
Розглянемо докладніше, як працює алгоритм.
- Припустимо, у нас є 4 пісні від The White Stripes , як на малюнку вище. Це означає, що вони мають з’являтися приблизно через кожні 25% довжини списку відтворення. Ми розкладаємо 4 пісні вздовж рядка, але їх відстань змінюватиметься випадковим чином від приблизно 20% до 30%, щоб остаточний порядок виглядав більш випадковим. Ви повинні бачити, що відстань між червоними колами на лінії неоднакова.
- Ми вводимо випадковий зсув на початку; інакше всі перші пісні опинилися б на позиції 0. Ви бачите, що і Брітні Спірс, і Джага Джазіст мають лише одну пісню, але випадкове зміщення призводить до того, що вони з’являються у випадковому місці списку відтворення.
- Пісні одного виконавця Ми також перемішуємо між собою . Тут ми можемо використати перемішування Фішера-Йетса або застосувати той самий алгоритм рекурсивно, наприклад, ми можемо запобігти відтворенню пісень з одного альбому надто близько одна до одної.
Загалом, алгоритм дуже простий і його можна реалізувати всього за пару рядків програмного коду. Він також дуже швидкий і дає гідні результати.
За матеріалами: Spotify
