J; хотів би написати алгоритм "остаточного перемішування" для сортування моєї колекції mp3

Я шукаю псевдокоди для сортуйте мої mp3-файли, щоб уникнути повторення назв та виконавців . Я слухаю кронів - Френка Сінатру, Тоні Беннета, Елу Фіцджеральд тощо, які співають старі стандарти. Кожен виконавець записує кілька однакових пісень - Fly Me To The Moon, What You Watch Tonight, Stardust тощо. Моя мета - організувати пісні (або замовити список відтворення) з максимальним проміжком між виконавцями та назвами пісень. Отже, якщо у мене 2000 пісень, а 20 - від Елли, я хотів би почути це лише один раз із 100 пісень. Якщо 10 виконавців співають Fly Me To The Moon, я хотів би почути це раз у 200 піснях. Звичайно, я хочу поєднати ці дві вимоги, щоб створити свою "остаточну суміш".

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

Для початку я модифікую код, який я знайшов тут, для маніпулювання файлами mp3 та читання тегів ID3.

Я написав невеликий додаток, який відповідає моїм потребам, використовуючи відповідь parsifal нижче. Я також написав тут наступне запитання. Дякую за всі правильні відповіді!

Ви хочете запустити програму один раз і створити список відтворення або вибрати наступну пісню в прямому ефірі?

У останньому випадку відповідь проста:

Створіть таблицю, що містить усі ваші пісні, з виконавцем та назвою.
Створіть список (краще пов'язаний список), щоб містити нещодавно відтворені назви пісень. На початку цей список порожній, і кожного разу, коли ви відтворюєте пісню, ви додаєте її до списку. Коли у списку відображається бажаний розмір "не повторювати пісню", видаліть найстаріший (перший) запис.
Так само для списку виконавців.

Вибір пісні стає наступною послідовністю кроків:

Випадково виберіть пісню з таблиці "всі пісні". Це просто випадкове число від 0 до розміру масиву.
Перевірте, чи ця пісня вже є у списку відтворених пісень. Якщо так, поверніться до кроку 1.
Перевірте, чи виконавець вже є у списку відтворених виконавців. Якщо так, поверніться до кроку 1.
Додайте виконавця пісні/заголовок до відповідних списків, видаляючи старі записи, якщо це необхідно.
Відтвори пісню.

Є декілька можливих проблем, але вони мають значення, лише якщо ви робите це як доручення, а не як реальний проект.

Як зазначив @Dukeling у коментарі, якщо ваша колекція різко розбалансується на користь одного виконавця чи назви пісні, ви можете загубитися у циклі, де ви постійно відкидаєте пісні. На практиці це не буде проблемою. Рішення полягає в зменшенні розміру списків "вже побаченого". А додавання лічильників на кроках 2 і 3 може сказати вам, чи це проблема (якщо ви бачите 10 помилок поспіль, викликайте попередження та/або зменште розмір списку).
Якщо ви намагаєтеся створити список відтворення, в якому всі ваші пісні відтворюються один раз, вам потрібно видалити пісні з вихідної матриці. Це також змінить спосіб вашого спілкування із занадто великою кількістю "нещодавно зіграних" шахів (оскільки ви могли б отримати лише одного виконавця у вашій вихідній дошці).
Якщо ваші теги ID3 схожі на мої, вони містять багато орфографічних помилок. Чи повинен "Герцог Елінгтон" відрізнятися від "Герцога Елінгтена"? Якщо так, розгляньте можливість використання збігу Левенштейна під час перегляду списків "нещодавно відтворених".

Я вже робив щось подібне, перш ніж використовувати генератор (у C #, нескінченний цикл, який збігається, дає кожну ітерацію циклу). Кожна ітерація перевіряє свій пул пісень (або що завгодно) і відкидає ті, що звучали занадто недавно (або незалежно від негативних критеріїв). Потім ви вибираєте один із відфільтрованого списку та оновлюєте свій статус. У міру того, як ваш стан змінюється (ви граєте пісні, що не належать до Синатри), критерії руйнуються, а виключені пісні починають повторно включатися.

Звичайно, є випадки, з якими потрібно боротися:

Що станеться, якщо викинути всі пісні? (зазвичай вибирають навмання, в надії на дестабілізацію стану)
Чи є якісь критерії, яким слід віддати перевагу? (Зазвичай ви можете не захотіти грати Fly Me to the Moon спиною до спини і вважати за краще не грати в Синатру, але якщо це все, що у вас є.)
Що станеться, якщо ваша колекція пісень буде оновлена під час бійки? (як правило, простий в управлінні, але паралельність може бути проблемою залежно від використання)

Ігноруючи викиди у вашому питанні, піднятому Теластином, схоже, у вас є варіація проблеми з рюкзаком. На щастя, це досить добре задокументований алгоритм.

Для набору предметів, кожен із вагою та вартістю, визначте кількість предметів, які слід включити до колекції, щоб загальна вага була меншою або дорівнювала заданому межі, а загальна вартість була якомога більшою.

Деякі потенційно відповідні варіанти перелічені в цій статті, а також додатковий список проблем із рюкзаками.

Різновидом проблеми рюкзака є проблема багатоцільового рюкзака. Як спосіб вирішення цієї проблеми пропонується алгоритм колонії мурашок. Підхід "колонії мурах" може бути найпростішим способом уникнути складних аспектів вашого питання.

Я також міг розглянути, розглядаючи вашу проблему як крайній варіант проблеми продавця, що подорожує. Кожне місто для відвідування - це справді пісня, яку ви хочете зіграти, але я не знаю, як би ви визначили інтервали між артистами. Ця пропозиція також пов'язана з/може бути вирішена підходом колонії мурах.

Я припускаю, що це "ось моя бібліотека, запустіть цю програму та створіть замовлення на відтворення пісень".

Він не реалізований, і я не знаю, наскільки він буде успішно його ремонтувати. Я можу бути занадто суворим у фільтрі, що призведе (я вважаю) до встановленого порядку для решти, з початкового набору пісень.

У нас є хеш ideal_gap. Це обчислюється за щільністю пісні із заданою властивістю (виконавець, альбом, назва). Якщо у нас 2000 пісень, і 20 з них написані художником на ім’я Елла, ideal_gap - це 100.

Отримуючи цю інформацію, ми також маємо максимум значень ideal_gap. Назвемо це max_gap .

Подумайте: наявність максимального значення ideal_gap для запобігання одній пісні, яку співали лише два виконавці, заважає відтворювати іншу пісню пізніше 1000 пісень і значно збільшує значення max_gap, що призводить до багатьох ітерацій "return, no song, return off, пісень немає ".

Перегляньте останні відтворені пісні max_gap (це можна заповнити з попереднього виступу. Тож якщо це закінчиться співом Френка Синатри Fly Me To the Moon, наступний виступ не почнеться з тієї самої пісні випадково.), Ми фільтруємо пісні в бібліотеці в результаті набір пісень-кандидатів. Пісня буде в піснях-кандидатах лише тоді, коли всі її прогалини менше ніж ideal_gap від цих властивостей.

З усіх пісень-кандидатів виберіть одну навмання.

Подумайте: обтяжте ансамбль так, щоб пісні, які призначають більший максимальний розповсюдження, були більш імовірними. Таким чином, усі найбільші доріжки з максимальним розривом не складаються в кінці списку відтворення.

Подумайте: замість того, щоб три властивості були більшими за ідеальний простір, з трьох є лише дві. Це може означати, що щось можна було б відтворити раніше ідеального ідеалу, але збільшує розмір набору пісень-кандидатів, що означає, що "вибір навмання" має більше можливостей.

Якщо немає пісень, які відповідають вимогам, max_gap скасуйте її на 1, а всі ideal_gaps - на n/max_gap%, де n - кількість разів, коли це було скасовано. Таким чином, якщо існує число max_gap 100 і воно було зменшено в 5 разів за цю ітерацію, ідеальний проміжок 100 буде тимчасово відрегульований до 95, а ідеальний проміжок 20 тимчасово буде 19. Повторювати пробіл, поки не буде принаймні одну пісню-кандидата, а потім виберіть її, як зазначено вище.

Подумайте: наявність мінімального розміру басейну. Це додає дисперсії, але може призвести до того, що пісня відтворюється раніше ідеального місця, коли можна відтворити іншу пісню.

Це робота з оптимізації і досить складна, якщо ви шукаєте оптимальне рішення. На щастя, я вважаю, що це один із тих випадків, коли вдається досить добре.

Перше, що потрібно зробити, це встановити математичний критерій якості, тобто формулу, яка, враховуючи перестановку списку, поверне унікальне число, що описує, хороша чи погана ця перестановка.

Проста пропозиція формули, призначте вагу кожному критерію, який ви хочете врахувати, надайте велику вагу важливим критеріям і низьку критеріям, коли багато пісень мають однакові властивості, щоб вони не домінували:

Чим нижче значення цієї процедури, тим краща перестановка списку.

Зробіть перестановку

Тепер ви можете використовувати цю формулу в math.stackexchange і попросити її розповісти вам, як неймовірно складно і практично неможливо знайти оптимальне рішення правильним рішенням.

Є кілька способів зробити це, ось один:

Це недорогий алгоритм, але його легко реалізувати та обробити стільки критеріїв, скільки потрібно.

Оптимізація

Можна навантажити різні налаштування та оптимізації, ось деякі з них:

Підраховуючи якість, не намагайтесь порівнювати одну пісню з усіма іншими піснями у списку, просто порівняйте її зі 100 найближчими піснями. Для загальних значень така оптимізація швидкості практично не впливає на якість результату.

Для рідкісного значення даної властивості може бути ефективніше відстежувати існуючі екземпляри цього значення, ніж знаходити їх.

Якщо ви відчуваєте, що важливо, щоб значення, які мають кілька екземплярів, були близькими одне до одного, а не дуже близькими, можливо, потрібно збільшити вагу цих конкретних значень, але не інших значень цього критерію.

Псевдовипадкова функція, яка вибирає всі можливі пари з рівномірно розподіленого списку, може мати дещо вищу ефективність на вибір у порівнянні зі звичайним випадковим вибором.

Цікаво спостерігати за різними підходами людей. Я б зробив наступне:

Виходячи з усіх відтворених досі композицій, поставте кожному оцінку. Відтворіть доріжку з найнижчим балом (або, у випадку однакових оцінок, випадкову доріжку, що відповідає найнижчій оцінці). Повторити.

Складність, звичайно, полягає в тому, щоб дати оцінку. Для кожної можливої доріжки, яку ви могли б відтворити наступною, вам доведеться пройти кожну з доріжок (або обмежену кількість) доріжок, які ви вже відтворили. Якщо [наступна можлива] доріжка та [нещодавно відтворена] доріжка мають щось спільне, ви додаєте до рахунку, залежно від того, скільки у них спільного, що у них спільного та дати попередньої. нещодавно відтворена] доріжка. грати. Ви, мабуть, хотіли б, щоб "взагалі нічого спільного" не було 0, тому ви можете починати з усіх треків як 0.

Можливо, для початку вам захочеться поекспериментувати з ручно створеними списками відтворення, щоб отримати точні підрахунки - чи потрібно кількість спільних слів, квадрат загальної кількості слів або квадратний корінь з числа слова. спільного? Перегляньте весь ваш список відтворення, визначте, які з них видаються «найпоширенішими», і відкоригуйте фактори, щоб отримати правильний баланс. Можливо, ви хочете піти письмово, тоді "Дюк Еллінгтон" має високий бал у порівнянні з "Дюком Елінгтоном", але ще вищий бал порівняно з "Кінг Елле Датон" (якщо я не втратив жодного листа:). Вам слід дуже уважно поглянути на поля, які ви хочете порівняти, і вказати, чи хочете ви порівнювати поля. Ви навіть можете розглянути біграми (пари літер; у випадку з Дюком Еллінгтоном, "Du", "

Зверніть увагу, що, якщо у вас багато виконавців, зокрема, цей виконавець може бути пріоритетним - ви можете прослухати пісню одного виконавця 5 разів, перш ніж прослухати всі 10 пісень на вашому Дюк Еллінгтон. Це може бути, а може і не те, що ти хочеш. Цього можна уникнути, створивши словник усього, що потрібно для порівняння, і того, як часто вони з’являються. Якщо у вас багато пісень Дюка Еллінгтона, дві пісні Дюка Еллінгтона "менш схожі", ніж дві пісні Біллі Джо Шейвера. .

Можливо, варто навіть заздалегідь розрахувати таблицю з кожною комбінацією двох пар пісень. Крім того, щоб визначити, яку пісню відтворювати далі, потрібно лише запам’ятати найкращу пісню на сьогоднішній день. якщо наступна, що підраховується, має нижчий бал, ніж найкраща пісня на даний момент, ви можете перейти до наступної.