Estoy buscando sugerencias de pseudocódigo para ordenar mis archivos mp3 de una manera que evite la repetición de títulos y artistas . Escucho cantantes: Frank Sinatra, Tony Bennett, Ella Fitzgerald, etc., cantando viejos estándares. Cada artista graba muchas de las mismas canciones: Fly Me To The Moon, The Way You Look Tonight, Stardust, etc. Mi objetivo es organizar las canciones (u ordenar la lista de reproducción) con el máximo espacio entre artistas y títulos de canciones. Entonces, si tengo 2000 canciones y 20 son de Ella, me gustaría escucharla solo una vez de cada 100 canciones. Si 10 artistas cantan Fly Me To The Moon, me gustaría escucharlo una vez cada 200 canciones. Por supuesto, quiero combinar estos dos requisitos para crear mi "baraja definitiva".
Sé que esta es una pregunta bastante abierta. Todavía no he comenzado a programarlo, así que solo estoy buscando sugerencias de un buen enfoque. De hecho, tengo algunos otros requisitos con respecto al espaciado uniforme de otros atributos de la canción, pero no voy a entrar en eso aquí.
Como punto de partida, estoy modificando el código que encontré aquí para manipular archivos mp3 y leer etiquetas ID3.
Escribí una pequeña aplicación que satisface mi necesidad usando la respuesta de parsifal a continuación. También escribí una pregunta de seguimiento aquí . ¡Gracias por todas las buenas respuestas!
fuente
while (length(songs) > 0) { x := rand(); addElem(shuffle, songs[x]); remElem(songs, x); }
pero usted dice que quiere un "shuffle definitivo". No sé lo que realmente quieres con eso, incluso leyendo la pregunta ...Respuestas:
¿Desea ejecutar su programa una vez y generar una lista de reproducción, o elegir la próxima canción en vivo?
Si es lo último, entonces la respuesta es simple:
Elegir una canción se convierte en la siguiente secuencia de pasos:
Hay un par de posibles problemas, pero solo deberían importar si lo haces como tarea y no como un proyecto real.
fuente
He hecho algo como esto antes de usar un generador (en C #, un bucle infinito que
yield
es cada iteración del bucle). Cada iteración analiza su grupo de canciones (o lo que sea) y arroja las que se han reproducido demasiado recientemente (o cualquier criterio negativo). Luego elige uno de la lista filtrada y actualiza su estado. A medida que su estado cambia (toca canciones que no son de Sinatra), el criterio se desmorona y sus canciones excluidas comienzan a volver a incluirse.Por supuesto, hay casos de esquina para tratar:
fuente
Ignorando los valores atípicos de su pregunta que plantea Telastyn, parece que tiene una variación en el problema de la mochila . Afortunadamente, es un algoritmo bastante bien documentado.
De Wikipedia
Hay algunas variaciones potencialmente relevantes enumeradas en ese artículo junto con una lista adicional de problemas de mochila
Una variación del problema de la mochila es el problema de la mochila de objetivos múltiples. El algoritmo de la colonia de hormigas se sugiere como un medio para resolver ese problema. El enfoque de la colonia de hormigas podría ser la forma más fácil de evitar los aspectos difíciles de NP de su pregunta.
También pude ver considerando su problema como una variante extrema del problema del vendedor ambulante . Cada ciudad para visitar es realmente una canción que quieres tocar, pero no estoy seguro de cómo especificarías los intervalos entre artistas. Esta sugerencia también está relacionada con / puede resolverse mediante el enfoque de colonias de hormigas.
fuente
Estoy trabajando bajo el supuesto de que este es un "aquí está mi biblioteca, ejecute este programa y genere un orden para reproducir las canciones".
Esto no se ha implementado y no estoy seguro de qué tan bien preformará su barajado. Puede ser que soy demasiado estricto en el filtro, lo que resultaría (creo) en un orden prescrito para el resto dado un conjunto inicial de canciones.
Uno tiene un
ideal_gap
hash. Esto se calcula por la densidad de una canción con una propiedad dada (artista, álbum, título). Si una tiene 2000 canciones y 20 de ellas son de una artista llamada Ella,ideal_gap{'artist'}{"ella"}
serían 100.Tener esta información también tiene el máximo de los valores ideal_gap. Vamos a llamar a esto
max_gap
.Considere: tenga un
ideal_gap
valor máximo para evitar que una canción que solo dos artistas han cantado impida que la otra canción se reproduzca 1000 canciones más tarde, y también aumente drásticamente el valor max_gap, lo que resulta en muchas iteraciones de "retroceder, sin canciones, volver apagado, no hay canciones ".Examinando las últimas canciones de max_gap reproducidas (esto se puede completar a partir de una ejecución anterior, de modo que si terminó con Frank Sinatra cantando Fly Me To the Moon, la próxima ejecución no comenzará con la misma canción por casualidad), se filtran canciones de la biblioteca resulta en un conjunto de canciones candidatas. Una canción solo estaría en las canciones candidatas si todos sus espacios son menores que los
ideal_gap
de esas propiedades.Del conjunto de canciones candidatas, seleccione una al azar.
Considere: ponderar el conjunto para que las canciones que se atribuyen con una brecha máxima más alta sean ponderadas para ser más probables. De esta manera, uno no tiene todas las canciones de brecha máxima más grandes que se acumulan al final de la lista de reproducción.
Considere: en lugar de que las tres propiedades sean mayores que la brecha ideal, solo dos de cada tres. Esto puede significar que algo podría reproducirse antes del ideal ideal, pero aumenta el tamaño del conjunto de canciones candidato, lo que significa que "seleccionar uno al azar" tiene más opciones.
Si no hay canciones que cumplan los requisitos, retroceda en
max_gap
1 y todos los ideal_gaps enn/max_gap
porcentaje, donden
es el número de veces que se ha retrocedido. De esta manera, si hay unmax_gap
100 y se ha retrocedido 5 veces en esta iteración, un ideal_gap de 100 se ajustará temporalmente a 95, y un ideal_gap de 20 se ajustará temporalmente a 19. Repetir el retroceso del separe hasta que haya al menos una canción candidata, y luego selecciónela como se indica arriba.Considere: tener un tamaño mínimo de piscina. Esto se suma a la variación, pero puede dar como resultado que se reproduzca una canción antes del intervalo ideal cuando hay otra canción que podría reproducirse.
fuente
Este es un trabajo de optimización y bastante complejo si está buscando la solución óptima. Afortunadamente, creo que es uno de esos casos donde lo suficientemente bueno será suficiente.
Lo primero que debe hacer es establecer un criterio matemático de calidad, es decir, una fórmula que, dada una permutación de la lista, devolverá un solo número que describe cuán buena o mala es esa permutación.
Una sugerencia de fórmula simple, cada criterio que le gustaría tener en cuenta debe tener un peso, dar un alto peso a los criterios importantes y un bajo peso a los criterios en los que muchas canciones comparten la misma propiedad, para que esas no dominen :
Cuanto menor sea el valor que produce este procedimiento, mejor será la permutación de la lista.
Haciendo la permutación
Ahora podría llevar esta fórmula a math.stackexchange y hacer que le digan cuán increíblemente difícil y posiblemente prácticamente imposible es encontrar la solución óptima para cualquier cosa que no sea un número trivial de canciones, o simplemente puede lanzarle ciclos de reloj y obtener un buena solución.
Hay muchas formas de hacerlo, aquí hay una:
Este es un algoritmo algo derrochador, pero es fácil de implementar y puede manejar tantos criterios como uno desee.
Optimizaciones
Se pueden aplicar cargas de diferentes ajustes y optimizaciones, aquí hay algunos:
En el cálculo del valor de calidad, no se moleste en comparar una canción con cada una de las otras canciones de la lista, en su lugar, simplemente verifíquela con las 100 canciones más cercanas. Para valores comunes, esta optimización de velocidad prácticamente no tiene influencia en la calidad del resultado.
Para un valor raro de una propiedad dada, puede ser más eficiente rastrear las instancias existentes de ese valor que buscarlas.
Si considera que es importante que los valores que tienen pocas instancias estén espaciados de manera pareja, en lugar de estar muy separados, probablemente sea necesario aumentar el peso para esos valores específicos, pero no para otros valores de ese criterio.
Una función pseudoaleatoria que selecciona todos los pares posibles de la lista en igual distribución puede tener una eficiencia ligeramente mejor por selección que una selección aleatoria normal.
fuente
Es interesante qué diferentes enfoques toman las personas. Yo haría lo siguiente:
En función de todas las pistas reproducidas hasta ahora, asigne una puntuación a cada una. Reproduzca la pista con el puntaje más bajo (o, en el caso de puntajes idénticos, uno aleatorio que coincida con el puntaje más bajo). Repetir.
Lo difícil, por supuesto, es dar un puntaje. Para cada pista posible que pueda reproducir a continuación, deberá pasar por cada una (o un número limitado de) pistas que ya haya reproducido. Si la pista [posible siguiente] y la pista [recientemente reproducida] tienen algo en común, se agrega a la puntuación, dependiendo de cuánto tienen en común, qué tienen en común y cuánto tiempo hace que era la pista [recientemente reproducida] jugó. Probablemente desee que "nada en común" sea 0, por lo que puede comenzar con todas las pistas como 0.
Para comenzar, es probable que desee experimentar con algunas listas de reproducción hechas a mano, para obtener las matemáticas correctas: ¿desea el número de palabras en común, o el cuadrado del número de palabras en común, o la raíz cuadrada del número? de palabras en común? Ejecute toda su lista de reproducción, vea cuáles flotan a la cima como "más en común" y modifique manualmente los factores para obtener el equilibrio correcto. Tal vez quieras ir por letra, así que "Duke Ellington" tiene un puntaje alto en comparación con "Duke Elington", pero un puntaje aún mayor en comparación con "King Elle Duton" (si no he perdido ninguna letra :) . Debe considerar con mucho cuidado qué campos desea comparar y si desea comparar entre campos. Incluso podría considerar bigrams (pares de letras; en el caso de Duke ellington, "Du", "
Tenga en cuenta que, si tiene muchos artistas en particular, ese artista puede ser prioritario: puede escuchar una pista de un artista único 5 veces, antes de escuchar las 10 pistas de Duke Ellington. Esto podría o no ser lo que quieres. Puede evitar esto estableciendo un diccionario de todo lo que tiene que comparar y con qué frecuencia ocurren, por lo que si tiene muchas pistas de Duke Ellington, dos pistas de Duke Ellington son "menos similares" que dos de Billy Joe Shaver .
Incluso podría valer la pena calcular previamente una tabla con cada combinación de dos pares de canciones. Además, al considerar qué canción tocar a continuación, solo necesita recordar la mejor canción hasta el momento; Si la siguiente a considerar tiene una puntuación peor que la mejor canción hasta ahora, puede pasar a la siguiente.
fuente