Szukam sugestii pseudokodu do sortowania plików mp3 w sposób, który pozwoli uniknąć powtarzania tytułów i wykonawców . Słucham śpiewaków - Franka Sinatry, Tony'ego Bennetta, Elli Fitzgerald itp. Śpiewających stare standardy. Każdy artysta nagrywa wiele takich samych piosenek - Fly Me To The Moon, The Way You Look Tonight, Stardust itp. Moim celem jest uporządkowanie utworów (lub uporządkowanie listy odtwarzania) z maksymalną przestrzenią między artystami i tytułami utworów. Więc jeśli mam 2000 piosenek, a 20 pochodzi od Elli, chciałbym ją usłyszeć tylko raz na 100 piosenek. Jeśli 10 artystów śpiewa Fly Me To The Moon, chciałbym to usłyszeć raz na 200 piosenek. Oczywiście chcę połączyć te dwa wymagania, aby stworzyć mój „ostateczny los”.
Wiem, że to dość szeroko otwarte pytanie. Jeszcze nie zacząłem go programować, więc szukam tylko sugestii dobrego podejścia. Mam inne wymagania dotyczące równomiernego rozmieszczania innych atrybutów utworów, ale nie będę się tutaj zajmował.
Na początek modyfikuję kod, który tu znalazłem, aby manipulować plikami mp3 i czytać tagi ID3.
Napisałem małą aplikację, która zaspokaja moją potrzebę, korzystając z odpowiedzi parsifal poniżej. Tutaj też napisałem pytanie uzupełniające . Dzięki za wszystkie świetne odpowiedzi!
źródło
while (length(songs) > 0) { x := rand(); addElem(shuffle, songs[x]); remElem(songs, x); }
ale mówisz, że chcesz „ostatecznego losowania”. Nie wiem, czego tak naprawdę chcesz, nawet czytając pytanie ...Odpowiedzi:
Czy chcesz raz uruchomić program i wygenerować listę odtwarzania, czy wybrać następny utwór na żywo?
Jeśli to drugie, to odpowiedź jest prosta:
Wybór utworu staje się następującą sekwencją kroków:
Istnieje kilka możliwych problemów, ale powinny one mieć znaczenie tylko wtedy, gdy robisz to jako zadanie domowe, a nie prawdziwy projekt.
źródło
Zrobiłem coś takiego przed użyciem generatora (w C #, nieskończonej pętli, która
yield
jest iteracją każdej pętli). Każda iteracja analizuje pulę utworów (lub cokolwiek innego) i odrzuca te, które były odtwarzane zbyt niedawno (lub jakiekolwiek negatywne kryteria). Następnie wybierz jedną z przefiltrowanej listy i zaktualizuj swój stan. Gdy stan się zmienia (grasz utwory inne niż Sinatra), kryteria załamują się, a wykluczone utwory zaczynają być ponownie uwzględniane.Oczywiście istnieją narożne sprawy do rozwiązania:
źródło
Ignorując wartości odstające od twojego pytania, które wysuwa Telastyn, brzmi to tak, jakbyś miał różne rozwiązanie problemu plecaka . Na szczęście jest to dość dobrze udokumentowany algorytm.
Z Wikipedii
W tym artykule wymieniono kilka potencjalnie istotnych odmian wraz z dodatkową listą problemów z plecakiem
Jedną z odmian problemu plecakowego jest problem plecakowy z wieloma celami. Kolonia mrówek algorytm jest sugerowane jako sposób na rozwiązanie tego problemu. Podejście do kolonii mrówek może być najłatwiejszym sposobem na uniknięcie trudnych aspektów NP pytania.
Widziałem także twój problem jako skrajny wariant problemu podróżującego sprzedawcy . Każde miasto do odwiedzenia to naprawdę piosenka, którą chcesz zagrać, ale nie jestem pewien, jak określisz odstępy między artystami. Ta sugestia jest również związana z / może być rozwiązana poprzez podejście do kolonii mrówek.
źródło
Pracuję przy założeniu, że jest to „oto moja biblioteka, uruchom ten program i wygeneruj rozkaz do odtworzenia utworów”.
Nie zostało to zaimplementowane i nie jestem pewien, jak dobrze wykona tasowanie. Może być tak, że jestem nieco zbyt rygorystyczny w filtrze, co spowodowałoby (wierzę) ustaloną kolejność dla reszty, biorąc pod uwagę początkowy zestaw piosenek.
Jeden ma
ideal_gap
skrót. Jest to obliczane na podstawie gęstości utworu o danej właściwości (wykonawca, album, tytuł). Jeśli ktoś ma 2000 piosenek, a 20 z nich to artysta o imieniu Ella,ideal_gap{'artist'}{"ella"}
to będzie 100.Mając te informacje, można również uzyskać maksimum wartości ideal_gap. Nazwijmy to
max_gap
.Zastanów się: ustaw maksymalną
ideal_gap
wartość, aby uniemożliwić utwór, który śpiewali tylko dwaj artyści, uniemożliwiający odtworzenie 1000 utworów później, a także drastycznie zwiększyć wartość max_gap, co skutkuje wieloma powtórzeniami „wycofaj się, żadnych utworów, cofnij się” wyłączone, brak piosenek ”.Analizując ostatnie odtwarzane utwory max_gap (można to wypełnić z poprzedniego uruchomienia, aby jeśli zakończyło się śpiewaniem Franka Sinatry Fly Me To the Moon, następny utwór nie rozpocznie się przypadkowo od tej samej piosenki), jeden odfiltrowuje utwory z biblioteka, w wyniku której powstaje zestaw piosenek kandydujących. Piosenka byłaby w piosenkach kandydujących tylko wtedy, gdy wszystkie jej luki są mniejsze niż
ideal_gap
dla tych właściwości.Z zestawu kandydatów wybierz jedną losowo.
Zastanów się: ważenie zestawu w taki sposób, aby utwory, które mają większą maksymalną przerwę, były ważone, aby były bardziej prawdopodobne. W ten sposób na końcu listy odtwarzania nie gromadzą się wszystkie większe piosenki o maksymalnej przerwie.
Zastanów się: zamiast mieć wszystkie trzy właściwości większe niż idealna przerwa, tylko dwie z trzech. Może to oznaczać, że coś można odtworzyć wcześniej niż idealny ideał, ale zwiększa rozmiar zestawu utworów kandydujących, co oznacza, że „wybierz jeden losowo” ma więcej opcji.
Jeśli nie ma utworów spełniających wymagania, cofnij wartość
max_gap
o 1, a wszystkie wartości ideal_gap wedługn/max_gap
procentu oznaczająn
liczbę przypadków, w których zostało to cofnięte. W ten sposób, jeśli jestmax_gap
100, i zostało cofnięte 5 razy w tej iteracji, idealna przerwa 100 będzie tymczasowo ustawiona na 95, a idealna przerwa 20 będzie tymczasowo ustawiona na 19. Powtórz wycofanie przerwy, aż będzie co najmniej jedna piosenka kandydująca, a następnie wybierz ją jak wyżej.Zastanów się: mieć minimalny rozmiar puli. Zwiększa to wariancję, ale może spowodować, że utwór zostanie odtworzony wcześniej niż idealna przerwa, gdy istnieje inny utwór, który można odtworzyć.
źródło
Jest to zadanie optymalizacji i dość skomplikowana, jeśli szukasz do rozwiązania optymalnego. Na szczęście uważam, że jest to jeden z tych przypadków, w których wystarczy wystarczająco dużo.
Pierwszą rzeczą do zrobienia jest ustalenie matematycznego kryterium jakości, czyli formuły, która przy permutacji listy zwróci pojedynczą liczbę opisującą, jak dobra lub zła jest ta permutacja.
Prosta sugestia formuły, każdemu kryterium, które chciałbyś wziąć pod uwagę, należy przypisać wagę, przypisać dużą wagę ważnym kryteriom, a niską wagę kryteriom, w których wiele utworów ma tę samą właściwość, aby nie dominowały :
Im niższa jest wartość tej procedury, tym lepsza jest permutacja listy.
Dokonanie permutacji
Teraz możesz wziąć tę formułę do matematyki. Wymiana plików i poprosić, aby powiedzieli ci, jak szalenie trudne i być może praktycznie niemożliwe jest znalezienie optymalnego rozwiązania dla niczego poza trywialną liczbą piosenek, lub możesz po prostu rzucić na nią cykle zegara i uzyskać dobre rozwiązanie.
Jest na to wiele sposobów, oto jeden:
Jest to dość marnotrawny algorytm, ale jest łatwy do wdrożenia i może spełnić tyle kryteriów, ile jedno życzenie.
Optymalizacje
Można zastosować wiele różnych poprawek i optymalizacji, oto kilka:
Przy obliczaniu wartości jakości nie zawracaj sobie głowy sprawdzaniem utworu w porównaniu do każdego innego utworu na liście, zamiast tego sprawdź go w stosunku do 100 lub więcej najbliższych utworów. W przypadku wspólnych wartości ta optymalizacja prędkości praktycznie nie ma wpływu na jakość wyniku.
W przypadku rzadkiej wartości danej właściwości bardziej efektywne może być śledzenie istniejących wystąpień tej wartości niż ich wyszukiwanie.
Jeśli uważasz, że ważne jest, aby wartości, które mają niewiele instancji, były rozmieszczone w pobliżu wartości parzystej, a nie tylko daleko od siebie, prawdopodobnie konieczne jest zwiększenie wagi dla tych konkretnych wartości, ale nie dla innych wartości tego kryterium.
Pseudolosowa funkcja, która wybiera wszystkie możliwe pary z listy w równym rozkładzie, może mieć nieco lepszą wydajność na typ niż typowa losowa selekcja.
źródło
Ciekawe, jakie są różne podejścia ludzi. Zrobiłbym następujące:
Na podstawie wszystkich odtwarzanych do tej pory utworów, daj każdemu wynik. Zagraj na ścieżce z najniższym wynikiem (lub, w przypadku identycznych wyników, losowym pasującym do najniższego wyniku). Powtarzać.
Trudne jest oczywiście przyznanie punktacji. Dla każdej możliwej ścieżki, którą możesz odtworzyć w następnej kolejności, musisz przejść przez każdą (lub ograniczoną liczbę) ścieżek, które już odtworzyłeś. Jeśli utwór [możliwy następny] i utwór [ostatnio odtwarzany] mają coś wspólnego, dodajesz do partytury, w zależności od tego, jak wiele mają one wspólnego, co mają ze sobą wspólnego i jak dawno temu utwór [ostatnio odtwarzany] był grał. Prawdopodobnie chciałbyś, aby „nic wspólnego” nie było równe 0, więc możesz zacząć od wszystkich ścieżek jako 0.
Prawdopodobnie będziesz chciał poeksperymentować z ręcznie tworzonymi listami odtwarzania, aby poprawnie wyliczyć matematykę - czy chcesz liczbę wspólnych słów, czy kwadrat liczby wspólnych słów, czy pierwiastek kwadratowy z liczby słów wspólnych? Przejrzyj całą listę odtwarzania, zobacz, które z nich unoszą się na szczyt jako „najbardziej wspólne”, i ręcznie dostosuj czynniki, aby uzyskać równowagę. Może chcesz wybrać literę, więc „Duke Ellington” ma wysoki wynik w porównaniu z „Duke Elington”, ale jeszcze wyższy wynik w porównaniu z „King Elle Duton” (jeśli nie straciłem żadnych liter :) . Powinieneś bardzo dokładnie rozważyć, które pola chcesz porównać, a jeśli chcesz porównać między nimi. Możesz nawet rozważyć bigramy (pary liter; w przypadku księcia Ellington „Du”, „
Pamiętaj, że jeśli masz wielu konkretnych wykonawców, może zostać uprzywilejowany - może usłyszeć utwór unikalnego artysty 5 razy, zanim usłyszysz wszystkie 10 utworów Duke Ellington. To może, ale nie musi być to, czego chcesz. Można tego uniknąć, ustawiając słownik wszystkiego, co trzeba porównać i częstotliwość ich występowania, więc jeśli masz dużo utworów Duke Ellington, dwa utwory autorstwa Duke Ellington są „mniej podobne” niż dwa utwory Billy Joe Shaver .
Warto nawet wstępnie obstawiać przy każdej kombinacji dwóch par piosenek. Ponadto, zastanawiając się, który utwór zagrać jako następny, musisz tylko zapamiętać najlepszą do tej pory piosenkę; jeśli następny do rozważenia ma gorszy wynik niż jak dotąd najlepsza piosenka, możesz przejść do następnego.
źródło