Tomsk Sysadmins Forum

Unix => Программирование => Topic started by: One on January 25, 2006, 15:12:26

Title: Алгоритм случайного выбора песен.
Post by: One on January 25, 2006, 15:12:26
Если не сочтёте за "не в тему"...

Знает кто, как алгоритм случайной выборки файлов осуществляется в проигрывателях, например, XMMS? Т.е. есть список файлов, нужно проиграть их (я это делаю Mplayer) в случайном порядке, не повторяясь. Вот, какой алгоритм, пооптимальней, Вы предложете/знаете?

Спасибо.
Title: Алгоритм случайного выбора песен.
Post by: Krueger on January 25, 2006, 20:02:08
Quote
Если не сочтёте за "не в тему"...

Знает кто, как алгоритм случайной выборки файлов осуществляется в проигрывателях, например, XMMS? Т.е. есть список файлов, нужно проиграть их (я это делаю Mplayer) в случайном порядке, не повторяясь. Вот, какой алгоритм, пооптимальней, Вы предложете/знаете?

Спасибо.
[snapback]7058[/snapback]
Самое первое, что приходит на ум. Брать случайную песню из списка, проигрывать её, брать следующую, а предыдущую удалять из списка.
А вообще то-ли в мплеере, толи в хммс1 есть финкция перемешать плейлист случайным образом.
Title: Алгоритм случайного выбора песен.
Post by: One on January 28, 2006, 12:56:58
Удаление обуславливает пустые иттерации... Поэтому, не "the best". :)
Title: Алгоритм случайного выбора песен.
Post by: Krueger on January 28, 2006, 21:07:12
Quote
Удаление обуславливает пустые иттерации... Поэтому, не "the best". :)
[snapback]7138[/snapback]
пустые чего??
все последующие смещаются на место предыдущих..
можно, конечно, завести БД, куда будут складываться уже проигранные песни, но это, имхо, не лучший вариант.. потому, как повторов таким способом не избежать, и не факт, что хть раз выпадет одна из последних песен в течение короткого промежутка времени.
Хотя проще всего перемешать список сразу, а потом уже слушать его последовательно.
Title: Алгоритм случайного выбора песен.
Post by: One on January 30, 2006, 11:23:27
Навряд ли XMMSы решают это с помощью БД! :) Да даже если бы и так, я бы БД сюда не "прикручивал". :) Вариант про перемешать сразу - я тоже думал, но каков алгоритм в этом случае? С другой стороны, не хотелось бы никого напрягать... я и сам додумаю, просто могло оказаться, что "рядом" был человек, кто уже знает готовое решение...
Title: Алгоритм случайного выбора песен.
Post by: -ud- on January 30, 2006, 22:38:56
http://www.google.ru/search?hl=ru&q=shuffle+programming (http://www.google.ru/search?hl=ru&q=shuffle+programming)
вот хотя-бы: http://www.cs.sunysb.edu/~skiena/214/lectu...ect8/lect8.html (http://www.cs.sunysb.edu/~skiena/214/lectures/lect8/lect8.html)

не гуглите ни хера...  :angry:

+ у xmms есть исходники...
Title: Алгоритм случайного выбора песен.
Post by: One on January 31, 2006, 13:53:44
Quote
http://www.google.ru/search?hl=ru&q=shuffle+programming (http://www.google.ru/search?hl=ru&q=shuffle+programming)
вот хотя-бы: http://www.cs.sunysb.edu/~skiena/214/lectu...ect8/lect8.html (http://www.cs.sunysb.edu/~skiena/214/lectures/lect8/lect8.html)
не гуглите ни хера...  :angry:
А я наино полагал, что этот форум - место для общения... :)
Не гневитесь, жизнь - замечательна, даже елси люди "не гуглите ни хера..."
Кстати, "ни хера..." - не приличное слово, и употреблять на публике по-крайней мере неэтично.

Quote
+ у xmms есть исходники...
[snapback]7177[/snapback]
Да что Вы, правда? Какой он! - А я думал только операционная ОС Линукс такое прелоставляет... :)

В общем, будьте здоровы! :) Как говорил один мой американский друг: "Улыбайтесь!"
Title: Алгоритм случайного выбора песен.
Post by: stranger on January 31, 2006, 15:29:50
Как вариант возможен такой алгоритм.
При загрузки плэйлиста у каждой песни есть свой номер.
Разыгрываем простым генератором число и играем соответствующую мелодию. Перед генерированием следующей мелодии записываем ее номер в хешь, например, и разыгрываем заново. Проверяем есть ли новый полученный номер в хэше, если нет играем, если да разыгрываем новый ну и так далее пока количество элементов в хеше не совпадет с количеством песен в плэйлисте.

Алгоритм конечно не оптимальный, но храниться история проиграных песен и если человек нажмет на проигрышь предыдущей песни, то нужно сделать механизм, что бы ее номер читался из хэша и проигрывался, а последний скорее всего удалялся из хеша.
Как я понимаю после окончания проигрывания всех песен, если юзверь нажмет плей, то все в хэше нужно занулить и опять начать заново...
Title: Алгоритм случайного выбора песен.
Post by: -ud- on February 01, 2006, 00:51:54
Это я все к тому, что в деле изобретения велосипедов с квадратными колесами немаловажно быть в курсе аналогов  :rolleyes:
Title: Алгоритм случайного выбора песен.
Post by: One on February 01, 2006, 11:15:20
К stranger: Спасибо, хэш, используемый так - тоже какой-то вариант! Я тоже думал о хэше - если всё запихить в него и потом запросто удалать из него, но не придумал как их "перемешать"... Однако, хотелось бы от пустых итерраций уйти. А "походы" взад-вперёд по списку в задачи пока не ставились.

К -ud-: Да в курсе мы аналогов этих. Лично мне легче изобрести велосипед по-новой, нежели разбираться в чьём-то коде... Но, если сам не придумаю, буду разбирваться с чужим кодом. С другой стороны спросить кого-то мне труда не составляет. А общаться даже самым нелюдимым - полезно - IMO.
Title: Алгоритм случайного выбора песен.
Post by: stranger on February 01, 2006, 21:05:44
Quote
К stranger: Спасибо, хэш, используемый так - тоже какой-то вариант! Я тоже думал о хэше - если всё запихить в него и потом запросто удалать из него, но не придумал как их "перемешать"... Однако, хотелось бы от пустых итерраций уйти. А "походы" взад-вперёд по списку в задачи пока не ставились.
[snapback]7205[/snapback]
От пустых итераций уйти... Хм... Достаточно сложно, хотя для перемешивания списка. В приципе можно сделать например, следующее.
Список номеров хранить в контейнере со случайным доступом.
1. Разыгрываем случайное число, например, N (диаппазон его значений лучше сделать зависимым от количества мелодий в листе где-то 90-120% от n, где n количество мелодий в списке).  Это число будет определять количество перестановок в списке.
2. Потом N раз разыгрываем по два случайных числа в диаппазоне от 1 до n и переставляем между собой элементы стоящие на этих позициях.
В приципе после этой операции мы получим более или менее перемешенные намера мелодий. Качество перемешивания будет зависить от того с каким процентом от n мы будем разыгрывать число перестановок (его можно в принципе задать жестко простой формулой)

Ну а потом просто выбираем по одному последовательно номера мелодий и играем их...

Да еще нужно как-то задать начальное значение счетчика, что бы при запуске одного и того же списка на воспроизведение при новом запуске программы эта последовательность не повторялась.
Title: Алгоритм случайного выбора песен.
Post by: One on February 02, 2006, 11:23:59
Вы, молодец, stranger, такие "ракеты тут в космос" запускаете! :) -
Проблема не в том, чтобы придумать алгоритм - я, конечно, тоже смогу что-нить намудрить, потом, мысль осенит и что-то упростить, но вопрос мой в другом: *технологии* языка при реализации оного. Здесь, конечно, всплывает язык реализации алгоритма. И, буду я это делать если не bash, то по-крайней мере на Perl. Мысль моя проста: используя технологии языка, как, например: хэш - здоровская вещь, или, ссылки - тоже классно, - решить эту задачу просто. И, мне кажется, я уже что-то в этом направлении "нарыл", пока не было возможности попробовать. Но, если вариант окажется дееспособным, и тут ничего мы "не родим" - я его здесь приведу.

PS Спасибо, stranger, за Ваше внимание, кое Вы проявляете к моему вопросу. :)
Title: Алгоритм случайного выбора песен.
Post by: stranger on February 02, 2006, 12:58:51
Начнем с того, что изначально в постах спрашивалось про алгоритм.
А алгоритм - это штука, которая не зависит от языка.
Я привел дае реализации - обе они могут использовться в проигрывателях - причем первая более вероятно.
Если бы вы хотели знать о том как написать алгоритм на каком-нибудь языке, то указали бы его, так как в зависимости на чем я буду писать, на Perl || C++, реализация может быть разная. А точнее она будет совершенно разная для различных языков, даже если алгоритм один и тот же.

Что качается Perl, то оба алгоритма на нам то же можно решить по разному.
Или, если нужно просто выбрать случайным образом файлы из папки, то можно, например, воспользоваться File::Random

З.Ы. Каков был вопрос - таков был и ответ
Title: Алгоритм случайного выбора песен.
Post by: One on February 02, 2006, 15:55:02
Quote
З.Ы. Каков был вопрос - таков был и ответ
[snapback]7238[/snapback]
OK! Принимается! :)

Теперь мыслим в перловом направлении. :)

File::Random - мы уже с Вами об этом говорили в самом начале. Смысла от него мало здесь.
Title: Алгоритм случайного выбора песен.
Post by: demiurg on February 02, 2006, 22:52:47
Quote
OK! Принимается! :)

Теперь мыслим в перловом направлении. :)

File::Random - мы уже с Вами об этом говорили в самом начале. Смысла от него мало здесь.
[snapback]7241[/snapback]
Если уж речь зашла о перле :) Влезу и я со своим советом....
Code: [Select]
...
use List::Util qw(shuffle);
@array = shuffle(@array);Перемешает элементы массива.
Perl Cookbook (2nd ed). Рецепт 4.18. Там же сказано, что сделать плохой алгоритм случайной перестановки просто, а хороший сложнее...  :)
Причины там же объясняются.
Title: Алгоритм случайного выбора песен.
Post by: stranger on February 02, 2006, 23:17:35
Quote
Если уж речь зашла о перле :) Влезу и я со своим советом....
Code: [Select]
...
use List::Util qw(shuffle);
@array = shuffle(@array);Перемешает элементы массива.
Perl Cookbook (2nd ed). Рецепт 4.18. Там же сказано, что сделать плохой алгоритм случайной перестановки просто, а хороший сложнее...  :)
Причины там же объясняются.
[snapback]7254[/snapback]
Э... Точно. У меня же есть эта книга - из головы совсем вылетоло это описание  :(
Title: Алгоритм случайного выбора песен.
Post by: One on February 06, 2006, 16:01:55
Спасибо большое! Решили проблему! Тема закрыта.