Chciałbym napisać algorytm „ostatecznego losowania”, aby posortować moją kolekcję mp3

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!

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:

• Utwórz tablicę zawierającą wszystkie Twoje utwory, z nazwiskiem wykonawcy i tytułem
• Utwórz listę (najlepiej listę połączoną), aby przechowywać ostatnio odtwarzane tytuły utworów. Ta lista zaczyna się pusta i za każdym razem, gdy odtwarzasz utwór, dodajesz go do listy. Gdy lista osiągnie pożądany rozmiar „bez powtarzania utworu”, usuń najstarszy (pierwszy) wpis.
• To samo dotyczy listy artystów.

Wybór utworu staje się następującą sekwencją kroków:

1. Losowo wybierz utwór z tablicy „wszystkie utwory”. To tylko losowa liczba między 0 a rozmiarem tablicy.
2. Sprawdź, czy ten utwór jest już na liście odtwarzanych utworów. Jeśli tak, wróć do kroku 1.
3. Sprawdź, czy artysta jest już na liście wykonawców. Jeśli tak, wróć do kroku 1.
4. Dodaj wykonawcę / tytuł utworu do odpowiednich list, w razie potrzeby usuwając stare wpisy.
5. Odtwórz piosenkę.

Istnieje kilka możliwych problemów, ale powinny one mieć znaczenie tylko wtedy, gdy robisz to jako zadanie domowe, a nie prawdziwy projekt.

• Jak powiedział w komentarzu @Dukeling, jeśli Twoja kolekcja jest dramatycznie niezrównoważona na korzyść jednego wykonawcy lub tytułu utworu, możesz znaleźć się w pętli, w której ciągle odrzucasz utwory. W praktyce nie będzie to stanowić problemu. Rozwiązanie polega na tym, że musisz zmniejszyć rozmiar „już widzianych” list. Dodanie liczników w krokach 2 i 3 może powiedzieć, czy jest to problem (jeśli zobaczysz 10 awarii z rzędu, podnieś ostrzeżenie i / lub zmniejsz rozmiar listy).
• Jeśli próbujesz utworzyć listę odtwarzania, która zawiera wszystkie twoje utwory odtwarzane tylko raz, musisz usunąć utwory z tablicy źródłowej. Spowoduje to również zmianę sposobu radzenia sobie ze zbyt wieloma „ostatnio odtwarzanymi” awariami (ponieważ ostatecznie możesz skończyć z tylko jednym wykonawcą w tablicy źródłowej).
• Jeśli tagi ID3 są podobne do moich, zawierają wiele błędów ortograficznych. Czy „Duke Ellington” musi różnić się od „Duke Elingten”? Jeśli tak, skorzystaj z mechanizmu dopasowywania Levensteina podczas skanowania list „ostatnio granych”.

Zrobiłem coś takiego przed użyciem generatora (w C #, nieskończonej pętli, która yieldjest 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:

• Co się stanie, jeśli wyrzucisz wszystkie piosenki? (zwykle wystarczy wybrać jeden losowo, mając nadzieję na destabilizację stanu)
• Czy niektóre kryteria powinny być preferowane? (zwykle tak jest, może nie chcesz grać Fly Me to the Moon jeden po drugim i wolisz nie grać Sinatra jeden po drugim, ale jeśli to wszystko, co masz ...)
• Co się stanie, jeśli twoja kolekcja piosenek zostanie zaktualizowana w trakcie walki? (zwykle łatwe do rozwiązania, ale współbieżność może mieć problemy w zależności od użytkowania)

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

Biorąc pod uwagę zestaw przedmiotów, każdy o wadze i wartości, określ liczbę każdego elementu do uwzględnienia w kolekcji, aby całkowita waga była mniejsza lub równa danemu limitowi, a całkowita wartość była tak duża, jak to możliwe.

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.

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_gapskró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_gapwartość, 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_gapdla 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_gapo 1, a wszystkie wartości ideal_gap według n/max_gapprocentu oznaczają nliczbę przypadków, w których zostało to cofnięte. W ten sposób, jeśli jest max_gap100, 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ć.

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 :

For each song on the list
    For each other song on the list
        For each criteria
            If the two songs share that criteria
                Add to the quality value: square root( [criteria weight]/[distance between the two songs] )

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:

Start with a random permutation of the list.
Several million times do the following:
    Select two entries at random
    For each of those two entries calculate their contribution to the quality value
    Swap the positions of the two entries
    Calculate the contribution to the quality value of the two entries at their new position
    If the sum of the calculations in the new positions is greater than the sum in the old positions
        Swap back

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.

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.