Алгоритм случайного выбора песен.

[One]

Если не сочтёте за "не в тему"...

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

Спасибо.

[Krueger]

Если не сочтёте за "не в тему"...

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

Спасибо.

[snapback]7058[/snapback]

Самое первое, что приходит на ум. Брать случайную песню из списка, проигрывать её, брать следующую, а предыдущую удалять из списка.
А вообще то-ли в мплеере, толи в хммс1 есть финкция перемешать плейлист случайным образом.

[One]

Удаление обуславливает пустые иттерации... Поэтому, не "the best".

[Krueger]

Удаление обуславливает пустые иттерации... Поэтому, не "the best".

[snapback]7138[/snapback]

пустые чего??
все последующие смещаются на место предыдущих..
можно, конечно, завести БД, куда будут складываться уже проигранные песни, но это, имхо, не лучший вариант.. потому, как повторов таким способом не избежать, и не факт, что хть раз выпадет одна из последних песен в течение короткого промежутка времени.
Хотя проще всего перемешать список сразу, а потом уже слушать его последовательно.

[One]

Навряд ли XMMSы решают это с помощью БД! Да даже если бы и так, я бы БД сюда не "прикручивал". Вариант про перемешать сразу - я тоже думал, но каков алгоритм в этом случае? С другой стороны, не хотелось бы никого напрягать... я и сам додумаю, просто могло оказаться, что "рядом" был человек, кто уже знает готовое решение...

[-ud-]

http://www.google.ru/search?hl=ru&q=shuffle+programming
вот хотя-бы: http://www.cs.sunysb.edu/~skiena/214/lectu...ect8/lect8.html

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

+ у xmms есть исходники...

[One]

http://www.google.ru/search?hl=ru&q=shuffle+programming
вот хотя-бы: http://www.cs.sunysb.edu/~skiena/214/lectu...ect8/lect8.html
не гуглите ни хера...  :angry:

А я наино полагал, что этот форум - место для общения...
Не гневитесь, жизнь - замечательна, даже елси люди "не гуглите ни хера..."
Кстати, "ни хера..." - не приличное слово, и употреблять на публике по-крайней мере неэтично.

+ у xmms есть исходники...

[snapback]7177[/snapback]

Да что Вы, правда? Какой он! - А я думал только операционная ОС Линукс такое прелоставляет...

В общем, будьте здоровы! Как говорил один мой американский друг: "Улыбайтесь!"

[stranger]

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

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

[-ud-]

Это я все к тому, что в деле изобретения велосипедов с квадратными колесами немаловажно быть в курсе аналогов  :rolleyes:

[One]

К stranger: Спасибо, хэш, используемый так - тоже какой-то вариант! Я тоже думал о хэше - если всё запихить в него и потом запросто удалать из него, но не придумал как их "перемешать"... Однако, хотелось бы от пустых итерраций уйти. А "походы" взад-вперёд по списку в задачи пока не ставились.

К -ud-: Да в курсе мы аналогов этих. Лично мне легче изобрести велосипед по-новой, нежели разбираться в чьём-то коде... Но, если сам не придумаю, буду разбирваться с чужим кодом. С другой стороны спросить кого-то мне труда не составляет. А общаться даже самым нелюдимым - полезно - IMO.

[stranger]

К stranger: Спасибо, хэш, используемый так - тоже какой-то вариант! Я тоже думал о хэше - если всё запихить в него и потом запросто удалать из него, но не придумал как их "перемешать"... Однако, хотелось бы от пустых итерраций уйти. А "походы" взад-вперёд по списку в задачи пока не ставились.

[snapback]7205[/snapback]

От пустых итераций уйти... Хм... Достаточно сложно, хотя для перемешивания списка. В приципе можно сделать например, следующее.
Список номеров хранить в контейнере со случайным доступом.
1. Разыгрываем случайное число, например, N (диаппазон его значений лучше сделать зависимым от количества мелодий в листе где-то 90-120% от n, где n количество мелодий в списке).  Это число будет определять количество перестановок в списке.
2. Потом N раз разыгрываем по два случайных числа в диаппазоне от 1 до n и переставляем между собой элементы стоящие на этих позициях.
В приципе после этой операции мы получим более или менее перемешенные намера мелодий. Качество перемешивания будет зависить от того с каким процентом от n мы будем разыгрывать число перестановок (его можно в принципе задать жестко простой формулой)

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

Да еще нужно как-то задать начальное значение счетчика, что бы при запуске одного и того же списка на воспроизведение при новом запуске программы эта последовательность не повторялась.

[One]

Вы, молодец, stranger, такие "ракеты тут в космос" запускаете! -
Проблема не в том, чтобы придумать алгоритм - я, конечно, тоже смогу что-нить намудрить, потом, мысль осенит и что-то упростить, но вопрос мой в другом: *технологии* языка при реализации оного. Здесь, конечно, всплывает язык реализации алгоритма. И, буду я это делать если не bash, то по-крайней мере на Perl. Мысль моя проста: используя технологии языка, как, например: хэш - здоровская вещь, или, ссылки - тоже классно, - решить эту задачу просто. И, мне кажется, я уже что-то в этом направлении "нарыл", пока не было возможности попробовать. Но, если вариант окажется дееспособным, и тут ничего мы "не родим" - я его здесь приведу.

PS Спасибо, stranger, за Ваше внимание, кое Вы проявляете к моему вопросу.

[stranger]

Начнем с того, что изначально в постах спрашивалось про алгоритм.
А алгоритм - это штука, которая не зависит от языка.
Я привел дае реализации - обе они могут использовться в проигрывателях - причем первая более вероятно.
Если бы вы хотели знать о том как написать алгоритм на каком-нибудь языке, то указали бы его, так как в зависимости на чем я буду писать, на Perl || C++, реализация может быть разная. А точнее она будет совершенно разная для различных языков, даже если алгоритм один и тот же.

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

З.Ы. Каков был вопрос - таков был и ответ

[One]

З.Ы. Каков был вопрос - таков был и ответ

[snapback]7238[/snapback]

OK! Принимается!

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

File::Random - мы уже с Вами об этом говорили в самом начале. Смысла от него мало здесь.

[demiurg]

OK! Принимается!

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

File::Random - мы уже с Вами об этом говорили в самом начале. Смысла от него мало здесь.

[snapback]7241[/snapback]

Если уж речь зашла о перле Влезу и я со своим советом....

Code: [Select]

...
use List::Util qw(shuffle);
@array = shuffle(@array);Перемешает элементы массива.
Perl Cookbook (2nd ed). Рецепт 4.18. Там же сказано, что сделать плохой алгоритм случайной перестановки просто, а хороший сложнее...  
Причины там же объясняются.

[stranger]

Если уж речь зашла о перле Влезу и я со своим советом....

Code: [Select]

...
use List::Util qw(shuffle);
@array = shuffle(@array);Перемешает элементы массива.
Perl Cookbook (2nd ed). Рецепт 4.18. Там же сказано, что сделать плохой алгоритм случайной перестановки просто, а хороший сложнее... 
Причины там же объясняются.

[snapback]7254[/snapback]

Э... Точно. У меня же есть эта книга - из головы совсем вылетоло это описание  

[One]

Спасибо большое! Решили проблему! Тема закрыта.