Estou procurando sugestões de pseudocódigo para classificar meus arquivos mp3 de uma maneira que evite a repetição de títulos e artistas . Ouço cantores - Frank Sinatra, Tony Bennett, Ella Fitzgerald etc. cantando velhos padrões. Cada artista grava muitas das mesmas músicas - Fly Me To The Moon, The Way You Look Tonight, Stardust etc. Meu objetivo é organizar as músicas (ou solicitar a lista de reprodução) com o espaço máximo entre os artistas e os títulos das músicas. Então, se eu tenho 2000 músicas e 20 são de Ella, eu gostaria de ouvi-la apenas uma vez a cada 100 músicas. Se dez artistas cantarem Fly Me To The Moon, eu gostaria de ouvir uma vez a cada 200 músicas. É claro que quero combinar esses dois requisitos para criar meu "shuffle final".
Eu sei que essa é uma questão em aberto. Ainda não comecei a programar, então estou apenas procurando sugestões de uma boa abordagem a ser adotada. Na verdade, tenho alguns outros requisitos em relação ao espaçamento uniforme de outros atributos da música, mas não abordarei isso aqui.
Como ponto de partida, estou modificando o código que encontrei aqui para manipular arquivos mp3 e ler tags ID3.
Eu escrevi um pequeno aplicativo que satisfaz minha necessidade usando a resposta de parsifal abaixo. Também escrevi uma pergunta de acompanhamento aqui . Obrigado por todas as ótimas respostas!
fonte
while (length(songs) > 0) { x := rand(); addElem(shuffle, songs[x]); remElem(songs, x); }
mas você diz que deseja um "shuffle final". Eu não sei o que você realmente quer com isso, mesmo lendo a pergunta ...Respostas:
Deseja executar seu programa uma vez e gerar uma lista de reprodução ou escolher a próxima música ao vivo?
Neste último caso, a resposta é simples:
A escolha de uma música torna-se a seguinte sequência de etapas:
Existem alguns problemas possíveis, mas eles só devem importar se você estiver fazendo isso como lição de casa e não como um projeto real.
fonte
Eu fiz algo assim antes de usar um gerador (em C #, um loop infinito que
yield
é cada iteração de loop). Cada iteração examina seu conjunto de músicas (ou o que for) e joga fora aquelas que foram tocadas muito recentemente (ou qualquer que seja o critério negativo). Em seguida, você escolhe um da lista filtrada e atualiza seu estado. À medida que o seu estado muda (você toca músicas que não são do Sinatra), os critérios são quebrados e as músicas excluídas começam a ser incluídas novamente.Claro que existem casos de canto para lidar com:
fonte
Ignorando os discrepantes de sua pergunta que Telastyn levanta, parece que você tem uma variação no problema da mochila . Felizmente, é um algoritmo muito bem documentado.
Da Wikipedia
Existem algumas variações potencialmente relevantes listadas nesse artigo, além de uma lista adicional de problemas da mochila
Uma variação do problema da mochila é o problema da mochila multi-objetivo. O algoritmo da colônia de formigas é sugerido como um meio de resolver esse problema. A abordagem das colônias de formigas pode ser a maneira mais fácil de evitar os aspectos difíceis da PN da sua pergunta.
Também pude considerar o seu problema como uma variante extrema do problema do vendedor ambulante . Cada cidade a visitar é realmente uma música que você deseja tocar, mas não sei como você especificaria os intervalos entre os artistas. Essa sugestão também está relacionada a / pode ser resolvida pela abordagem da colônia de formigas.
fonte
Estou trabalhando com a suposição de que este é um "aqui é minha biblioteca, execute este programa e gere uma ordem para reproduzir as músicas".
Isso não foi implementado e não tenho certeza de quão bem ele irá executar seu embaralhamento. Pode ser que eu sou um pouco demasiado rigoroso no filtro, o que resultaria (creio eu) em uma ordem prescrita para o restante dado um conjunto inicial de canções.
Um tem um
ideal_gap
hash. Isso é calculado pela densidade de uma música com uma determinada propriedade (artista, álbum, título). Se alguém tiver 2000 músicas e 20 delas pertencerem a uma artista chamada Ella,ideal_gap{'artist'}{"ella"}
serão 100.Tendo essas informações, também temos o máximo dos valores ideal_gap. Vamos chamar isso
max_gap
.Considere: tenha um
ideal_gap
valor máximo no valor para impedir que uma música que apenas dois artistas cantaram impedam que a outra música seja reproduzida 1000 músicas posteriormente e também aumentando drasticamente o valor max_gap, resultando em muitas iterações de "recuar, sem músicas, voltar" desligado, sem músicas ".Examinando as últimas músicas max_gap tocadas (isso pode ser preenchido a partir de uma execução anterior, de modo que, se terminar com Frank Sinatra cantando Fly Me To the Moon, a próxima execução não começará com a mesma música por acaso), filtrará as músicas a biblioteca, resultando em um conjunto de músicas candidatas. Uma música só estaria nas músicas candidatas se todas as suas lacunas forem menores que as
ideal_gap
dessas propriedades.No conjunto de músicas candidatas, selecione uma aleatoriamente.
Considere: ponderar o conjunto para que as músicas atribuídas com um intervalo máximo maior sejam ponderadas para ter mais probabilidade. Dessa forma, não há todas as músicas maiores de gap máximo acumuladas no final da lista de reprodução.
Considere: em vez de ter todas as três propriedades maiores que a diferença ideal, apenas duas em cada três. Isso pode significar que algo pode ser reproduzido antes do ideal ideal, mas aumenta o tamanho da música candidata, o que significa que "selecionar uma aleatoriamente" tem mais opções.
Se não houver músicas que preencham os requisitos, retire o valor
max_gap
por 1 e todos os intervalos_ ideais porn/max_gap
porcentagem, onden
é o número de vezes que esse valor foi retirado. Dessa forma, se houver ummax_gap
de 100, e ele tiver sido recuado 5 vezes nesta iteração, um intervalo ideal de 100 será ajustado temporariamente para 95 e um intervalo ideal de 20 será ajustado temporariamente para 19. Repita o backup do intervalo até que haja pelo menos uma música candidata e selecione-a como acima.Considere: tenha um tamanho mínimo de piscina. Isso aumenta a variação, mas pode resultar na reprodução de uma música antes do intervalo ideal quando houver outra música que possa ser reproduzida.
fonte
Este é um trabalho de otimização e bastante complexo, se você estiver procurando a solução ideal. Felizmente, acredito que seja um daqueles casos em que o suficiente será suficiente.
A primeira coisa a fazer é estabelecer um critério matemático de qualidade, ou seja, uma fórmula que, dada uma permutação da lista, retornará um único número descrevendo quão boa ou ruim é essa permutação.
Uma sugestão simples de fórmula: cada critério que você gostaria de levar em consideração deve ter um peso, atribuir um peso alto a critérios importantes e um peso baixo a critérios em que muitas músicas compartilham a mesma propriedade, para que elas não dominem :
Quanto mais baixo for o valor desse procedimento, melhor será a permutação da lista.
Fazendo a permutação
Agora você pode usar essa fórmula em math.stackexchange e pedir que eles digam o quão incrivelmente difícil e possivelmente praticamente impossível é encontrar a solução ideal para qualquer coisa, exceto um número trivial de músicas, ou você pode simplesmente usar ciclos de relógio e obter uma boa solução.
Existem muitas maneiras de fazer isso, aqui está uma:
Esse é um algoritmo um pouco inútil, mas é fácil de implementar e pode lidar com tantos critérios quanto um desejo.
Otimizações
Cargas de diferentes ajustes e otimizações podem ser aplicadas, eis algumas:
No cálculo do valor da qualidade, não se preocupe em verificar uma música em relação a todas as outras músicas da lista; em vez disso, verifique-a nas 100 músicas mais próximas. Para valores comuns, essa otimização de velocidade praticamente não tem influência na qualidade do resultado.
Para um valor raro de uma determinada propriedade, pode ser mais eficiente rastrear as instâncias existentes desse valor do que procurá-las.
Se você achar que é importante que os valores que possuem poucas instâncias sejam espaçados perto do par, e não apenas distantes, provavelmente será necessário aumentar o peso desses valores específicos, mas não de outros valores desse critério.
Uma função pseudo-aleatória que seleciona todos os pares possíveis da lista em igual distribuição pode ter uma eficiência um pouco melhor por escolha do que uma escolha aleatória normal.
fonte
É interessante quais abordagens diferentes as pessoas adotam. Eu faria o seguinte:
Com base em todas as faixas reproduzidas até agora, dê uma pontuação a cada uma. Toque a faixa com a menor pontuação (ou, no caso de pontuações idênticas, aleatória que corresponda à menor pontuação). Repetir.
O difícil, é claro, é dar uma pontuação. Para cada faixa possível que você pode tocar a seguir, você teria que percorrer cada uma (ou um número limitado de) faixas que você já tocou. Se a faixa [possível próxima] e a faixa [reproduzida recentemente] tiverem algo em comum, você adiciona à partitura, dependendo do quanto elas têm em comum, o que elas têm em comum e há quanto tempo a faixa [reproduzida recentemente] foi reproduziu. Você provavelmente deseja que "nada em comum" seja 0, para poder começar com todas as faixas como 0.
Você provavelmente desejará experimentar algumas listas de reprodução criadas manualmente, para acertar as contas - deseja o número de palavras em comum, ou o quadrado do número de palavras em comum, ou a raiz quadrada do número de palavras em comum? Execute toda a sua lista de reprodução, veja quais flutuam para o topo como as "mais comuns" e ajuste manualmente os fatores para obter o equilíbrio certo. Talvez você queira ir por letra, para que "Duke Ellington" tenha uma pontuação alta quando comparado com "Duke Elington", mas uma pontuação ainda mais alta quando comparado com "King Elle Duton" (se eu não perdi nenhuma letra :) . Você deve considerar com muito cuidado quais campos deseja comparar e se deseja comparar entre os campos. Você pode até considerar bigrams (pares de letras; no caso de Duke Ellington, "Du", "
Observe que, se você tem um artista em particular, esse artista pode ser suspenso com prioridade - você pode ouvir uma faixa de um artista único 5 vezes, antes de ouvir todas as 10 faixas de Duke Ellington. Isso pode ou não ser o que você deseja. Você pode evitar isso configurando um dicionário de tudo o que precisa comparar e com que frequência eles ocorrem; portanto, se você tiver muitas faixas de Duke Ellington, duas faixas de Duke Ellington são "menos semelhantes" do que as de Billy Joe Shaver. .
Pode até valer a pena pré-cacular uma mesa com cada combinação de dois pares de músicas. Além disso, ao considerar qual música tocar em seguida, você só precisa se lembrar da melhor música até agora; se a próxima a considerar tiver uma pontuação pior que a melhor música até agora, você pode pular para a próxima.
fonte