Algoritmo de lista de reproducción aleatoria

Question

Necesito crear una lista de números de un rango (por ejemplo, de xay) en un orden aleatorio para que cada orden tenga las mismas posibilidades.

Necesito esto para un reproductor de música que escribo en C#, para crear listas de reproducción en orden aleatorio.

¿Alguna idea?

Gracias.

EDITAR: No estoy interesado en cambiar la lista original, simplemente tome los índices aleatorios de un rango en orden aleatorio para que cada orden tenga las mismas posibilidades.

Aquí es lo que he wrriten hasta ahora:

public static IEnumerable<int> RandomIndexes(int count) 
    { 
     if (count > 0) 
     { 
      int[] indexes = new int[count]; 
      int indexesCountMinus1 = count - 1; 

      for (int i = 0; i < count; i++) 
      { 
       indexes[i] = i; 
      } 

      Random random = new Random(); 

      while (indexesCountMinus1 > 0) 
      { 
       int currIndex = random.Next(0, indexesCountMinus1 + 1); 
       yield return indexes[currIndex]; 

       indexes[currIndex] = indexes[indexesCountMinus1]; 
       indexesCountMinus1--; 
      } 

      yield return indexes[0]; 
     } 
    } 

Está funcionando, pero el único problema de esto es que necesito para asignar una matriz en la memoria en el tamaño de count. Estoy buscando algo que la dosis no requiera asignación de memoria.

Gracias.

Answer 1

Esto realmente puede ser complicado si no tiene cuidado (es decir, usando un ingenuo algoritmo de mezcla aleatoria). Eche un vistazo a Fisher-Yates/Knuth shuffle algorithm para una distribución adecuada de los valores.

Una vez que tenga el algoritmo de mezcla, el resto debería ser fácil.

Aquí está more detail de Jeff Atwood.

Por último, aquí está el implementation and description de Jon Skeet.

EDITAR

No creo que hay una solución que satisfaga sus dos requisitos conflictivos (en primer lugar, a ser al azar, sin repeticiones y segundo para no asignar ninguna memoria adicional). Creo que es posible que optimice prematuramente su solución, ya que las implicaciones de memoria deberían ser insignificantes, a menos que esté incrustado. O, tal vez, no soy lo suficientemente inteligente como para encontrar una respuesta.

Con eso, aquí hay un código que creará una matriz de índices aleatorios distribuidos uniformemente utilizando el algoritmo Knuth-Fisher-Yates (con una ligera modificación). Puede almacenar en caché la matriz resultante o realizar cualquier cantidad de optimizaciones dependiendo del resto de su implementación.

private static int[] BuildShuffledIndexArray(int size) { 

    int[] array = new int[size]; 
    Random rand = new Random(); 
    for (int currentIndex = array.Length - 1; currentIndex > 0; currentIndex--) { 
     int nextIndex = rand.Next(currentIndex + 1); 
     Swap(array, currentIndex, nextIndex); 
    } 
    return array; 
    } 

    private static void Swap(IList<int> array, int firstIndex, int secondIndex) { 

    if (array[firstIndex] == 0) { 
     array[firstIndex] = firstIndex; 
    } 
    if (array[secondIndex] == 0) { 
     array[secondIndex] = secondIndex; 
    } 
    int temp = array[secondIndex]; 
    array[secondIndex] = array[firstIndex]; 
    array[firstIndex] = temp; 
    } 

NOTA: Se puede utilizar en lugar de ushortint a la mitad del tamaño de la memoria, siempre y cuando usted no tiene más de 65.535 artículos en su lista de reproducción. Siempre puede cambiar de forma programática a int si el tamaño excede ushort.MaxValue. Si yo, personalmente, agregué más de 65 mil elementos a una lista de reproducción, no me sorprendería la mayor utilización de la memoria.

Recuerde, también, que este es un lenguaje administrado. La máquina virtual siempre reservará más memoria de la que está utilizando para limitar el número de veces que necesita pedirle al sistema operativo más RAM y limitar la fragmentación.

EDITAR

bien, último intento: podemos mirar para modificar el comercio de rendimiento de memoria/apagado: Usted podría crear su lista de enteros, a continuación, escribir en el disco. Luego solo mantenga un puntero al desplazamiento en el archivo. Luego, cada vez que necesite un número nuevo, solo tendrá que lidiar con las E/S de disco. Quizás usted puede encontrar un cierto equilibrio aquí, y acaba de leer N bloques -sized de datos en la memoria, donde N es un número que se sienta cómodo.

parece como un montón de trabajo para un algoritmo aleatorio, pero si estás muerto-set en la conservación de la memoria, entonces por lo menos es una opción.

Answer 2

Personalmente, para un reproductor de música, yo no generar una lista arrastrando los pies, y entonces el juego que, a continuación, generar otra lista arrastrando los pies cuando eso se acabe, pero hacer algo más como:

IEnumerable<Song> GetSongOrder(List<Song> allSongs) 
{ 
    var playOrder = new List<Song>(); 
    while (true) 
    { 
     // this step assigns an integer weight to each song, 
     // corresponding to how likely it is to be played next. 
     // in a better implementation, this would look at the total number of 
     // songs as well, and provide a smoother ramp up/down. 
     var weights = allSongs.Select(x => playOrder.LastIndexOf(x) > playOrder.Length - 10 ? 50 : 1); 

     int position = random.Next(weights.Sum()); 
     foreach (int i in Enumerable.Range(allSongs.Length)) 
     { 
      position -= weights[i]; 
      if (position < 0) 
      { 
       var song = allSongs[i]; 
       playOrder.Add(song); 
       yield return song; 
       break; 
      } 
     } 

     // trim playOrder to prevent infinite memory here as well. 
     if (playOrder.Length > allSongs.Length * 10) 
      playOrder = playOrder.Skip(allSongs.Length * 8).ToList(); 
    }  
} 

Esto haría Haga las canciones recogidas en orden, siempre y cuando no se hayan reproducido recientemente. Esto proporciona transiciones "más suaves" desde el final de una secuencia aleatoria a la siguiente, porque la primera canción de la próxima mezcla podría ser la misma canción que la última mezcla con probabilidad de 1/(canciones totales), mientras que este algoritmo tiene una menor (y configurable) oportunidad de escuchar una de las últimas x canciones de nuevo.

Answer 3

Creo que debería apegarse a su solución actual (la de su edición).

para hacer un nuevo pedido sin repeticiones & no hacen su código se comporta poco fiable, hay que realizar un seguimiento de lo que ya han utilizado/igual que al mantener los índices no utilizados o indirectamente mediante el canje de la lista original.

que sugieren que verlo en el contexto de la aplicación de trabajo es decir, si su significado de cualquier vs. la memoria utilizada por otras piezas del sistema.

Answer 4

A menos que barajar la lista de canciones originales (que usted ha dicho que no quiere hacer), vas a tener que destinar algo de memoria adicional para lograr lo que está buscando.

Si genera la permutación aleatoria de los índices de canción de antemano (como lo está haciendo), obviamente tiene que asignar una cantidad no trivial de memoria para almacenarla, ya sea codificada o como una lista.

Si el usuario no necesita poder ver la lista, puede generar el orden aleatorio de las canciones sobre la marcha: después de cada canción, elija otra canción aleatoria del grupo de canciones no reproducidas. Aún debe hacer un seguimiento de qué canciones ya se han reproducido, pero puede usar un campo de bits para eso. Si tiene 10000 canciones, solo necesita 10000 bits (1250 bytes), cada uno representa si la canción se ha reproducido todavía.

No conozco sus limitaciones exactas, pero me pregunto si la memoria requerida para almacenar una lista de reproducción es significativa en comparación con la cantidad requerida para reproducir audio.

Answer 5

se puede utilizar un truco que hacemos en el servidor SQL para ordenar conjuntos en al azar como esto con el uso de GUID. los valores siempre se distribuyen igual a aleatorio.

private IEnumerable<int> RandomIndexes(int startIndexInclusive, int endIndexInclusive) 
{ 
    if (endIndexInclusive < startIndexInclusive) 
     throw new Exception("endIndex must be equal or higher than startIndex"); 

    List<int> originalList = new List<int>(endIndexInclusive - startIndexInclusive); 
    for (int i = startIndexInclusive; i <= endIndexInclusive; i++) 
     originalList.Add(i); 

    return from i in originalList 
      orderby Guid.NewGuid() 
      select i; 
} 

Answer 6

Desde un punto de vista lógico, es posible. Dada una lista de n canciones, hay n! permutaciones; si asigna a cada permutación un número del 1 al n! (o 0 a n! -1 :-D) y elija uno de esos números al azar, puede almacenar el número de la permutación que está utilizando actualmente, junto con la lista original y el índice de la corriente canción dentro de la permutación.

Por ejemplo, si usted tiene una lista de canciones {1, 2, 3}, sus permutaciones son:

0: {1, 2, 3} 
1: {1, 3, 2} 
2: {2, 1, 3} 
3: {2, 3, 1} 
4: {3, 1, 2} 
5: {3, 2, 1} 

Así que los únicos datos que necesito para realizar un seguimiento es la lista original ({1, 2 , 3}), el índice de la canción actual (por ejemplo, 1) y el índice de la permutación (por ejemplo, 3). Entonces, si quiero encontrar la siguiente canción para reproducir, sé que es la tercera (2, pero basada en cero) canción de permutación 3, p. Canción 1.

Sin embargo, este método se basa en que tener un medio eficaz de determinar la i ª canción del j º de permutación, que hasta que haya tenido la oportunidad de pensar (o alguien con una matemática más fuerte antecedentes que puedo interponer) es equivalente a "luego ocurre un milagro". Pero el principio está ahí.

Answer 7

Existen varios métodos para generar permutaciones sin necesidad de almacenar el estado. Ver this question.

Answer 8

Si utiliza un registro de desplazamiento de retroalimentación lineal máxima, usará O (1) de memoria y aproximadamente O (1) tiempo. See here para una práctica implementación de C (¡dos líneas! ¡Woo-hoo!) Y tablas de términos de comentarios para usar.

Y aquí es una solución:

public class MaximalLFSR 
{ 
    private int GetFeedbackSize(uint v) 
    { 
     uint r = 0; 

     while ((v >>= 1) != 0) 
     { 
      r++; 
     } 
     if (r < 4) 
      r = 4; 
     return (int)r; 
    } 

    static uint[] _feedback = new uint[] { 
     0x9, 0x17, 0x30, 0x44, 0x8e, 
     0x108, 0x20d, 0x402, 0x829, 0x1013, 0x203d, 0x4001, 0x801f, 
     0x1002a, 0x2018b, 0x400e3, 0x801e1, 0x10011e, 0x2002cc, 0x400079, 0x80035e, 
     0x1000160, 0x20001e4, 0x4000203, 0x8000100, 0x10000235, 0x2000027d, 0x4000016f, 0x80000478 
    }; 

    private uint GetFeedbackTerm(int bits) 
    { 
     if (bits < 4 || bits >= 28) 
      throw new ArgumentOutOfRangeException("bits"); 
     return _feedback[bits]; 
    } 

    public IEnumerable<int> RandomIndexes(int count) 
    { 
     if (count < 0) 
      throw new ArgumentOutOfRangeException("count"); 

     int bitsForFeedback = GetFeedbackSize((uint)count); 

     Random r = new Random(); 
     uint i = (uint)(r.Next(1, count - 1)); 

     uint feedback = GetFeedbackTerm(bitsForFeedback); 
     int valuesReturned = 0; 
     while (valuesReturned < count) 
     { 
      if ((i & 1) != 0) 
      { 
       i = (i >> 1)^feedback; 
      } 
      else { 
       i = (i >> 1); 
      } 
      if (i <= count) 
      { 
       valuesReturned++; 
       yield return (int)(i-1); 
      } 
     } 
    } 
} 

Ahora, he seleccionado los términos de retroalimentación (mal) de forma aleatoria desde el enlace anterior. También podría implementar una versión que tenga múltiples términos máximos y seleccione uno de ellos al azar, pero ¿sabe qué? Esto es bastante bueno para lo que quieres.

Aquí es el código de prueba:

static void Main(string[] args) 
    { 
     while (true) 
     { 
      Console.Write("Enter a count: "); 
      string s = Console.ReadLine(); 
      int count; 
      if (Int32.TryParse(s, out count)) 
      { 
       MaximalLFSR lfsr = new MaximalLFSR(); 
       foreach (int i in lfsr.RandomIndexes(count)) 
       { 
        Console.Write(i + ", "); 
       } 
      } 
      Console.WriteLine("Done."); 
     } 
    } 

Tenga en cuenta que la máxima del LFSR no generar 0. He hackeado en torno a esta devolviendo el término i - 1. Esto funciona bastante bien. Además, como quieres garantizar la exclusividad, ignoro todo lo que esté fuera del rango: el LFSR solo genera secuencias hasta potencias de dos, por lo que en rangos altos generará demasiados valores en el caso 2x-1. Se omitirán, esto seguirá siendo más rápido que FYK.

Answer 9

Si la memoria era realmente una preocupación después de un cierto número de registros y es seguro decir que si se alcanza ese límite de memoria, hay suficientes elementos en la lista para no importar si hay algunas repeticiones, siempre que el mismo la canción no se repitió dos veces, usaría un método de combinación.

Caso 1: Si cuenta < restricción de memoria máxima, genere la lista de reproducción antes de tiempo y utilice Knuth shuffle (consulte la implementación de Jon Skeet, mencionada en otras respuestas).

Caso 2: Si count> = restricción de memoria máxima, la canción que se reproducirá se determinará en tiempo de ejecución (lo haría tan pronto como la canción comience a reproducirse para que la siguiente canción ya esté generada por el tiempo la canción actual termina). Guarde la última [restricción de memoria máxima, o el valor de token] de las canciones reproducidas, genere un número aleatorio (R) entre 1 y recuento de canciones, y si R = una de las últimas X canciones reproducidas, genere una nueva R hasta que no sea en la lista. Juega esa canción.

Sus limitaciones de memoria máximas siempre se mantendrán, aunque el rendimiento puede sufrir en el caso 2 si ha reproducido muchas canciones/obtiene números aleatorios repetidos con frecuencia por casualidad.

Answer 10

Vas a tener que asignar algo de memoria, pero no tiene que ser mucho. Puede reducir la huella de memoria (el grado en el que no estoy seguro, ya que no sé mucho sobre las agallas de C#) mediante el uso de una matriz bool en lugar de int. En el mejor de los casos, esto solo usará (contar/8) bytes de memoria, lo que no está mal (pero dudo que C# realmente represente bools como bits únicos).

public static IEnumerable<int> RandomIndexes(int count) { 
     Random rand = new Random(); 
     bool[] used = new bool[count]; 

     int i; 
     for (int counter = 0; counter < count; counter++) { 
      while (used[i = rand.Next(count)]); //i = some random unused value 
      used[i] = true; 
      yield return i; 
     } 
    } 

Hope that helps!

Answer 11

Como muchos otros han dicho, debe implementar ENTONCES optimice, y solo optimice las piezas que lo necesitan (que puede controlar con un generador de perfiles). Ofrezco una (esperemos) elegante método de obtener la lista de lo que necesita, lo que no le importa mucho sobre el rendimiento:

using System; 
using System.Collections.Generic; 
using System.Linq; 

namespace Test 
{ 
    class Program 
    { 
     static void Main(string[] a) 
     { 
      Random random = new Random(); 
      List<int> list1 = new List<int>(); //source list 
      List<int> list2 = new List<int>(); 
      list2 = random.SequenceWhile((i) => 
       { 
        if (list2.Contains(i)) 
        { 
         return false; 
        } 
        list2.Add(i); 
        return true; 
       }, 
       () => list2.Count == list1.Count, 
       list1.Count).ToList(); 

     } 
    } 
    public static class RandomExtensions 
    { 
     public static IEnumerable<int> SequenceWhile(
      this Random random, 
      Func<int, bool> shouldSkip, 
      Func<bool> continuationCondition, 
      int maxValue) 
     { 
      int current = random.Next(maxValue); 
      while (continuationCondition()) 
      { 
       if (!shouldSkip(current)) 
       { 
        yield return current; 
       } 
       current = random.Next(maxValue); 
      } 
     } 
    } 
} 

Answer 12

Es casi imposible hacerlo sin la asignación de memoria adicional. Si le preocupa la cantidad de memoria adicional asignada, siempre puede elegir un subconjunto aleatorio y mezclar entre ellos. Obtendrás repeticiones antes de que se toque cada canción, pero con un subconjunto suficientemente grande, garantizaré que pocas personas lo notarán.

const int MaxItemsToShuffle = 20; 
public static IEnumerable<int> RandomIndexes(int count) 
{ 
    Random random = new Random(); 

    int indexCount = Math.Min(count, MaxItemsToShuffle); 
    int[] indexes = new int[indexCount]; 

    if (count > MaxItemsToShuffle) 
    { 
     int cur = 0, subsetCount = MaxItemsToShuffle; 
     for (int i = 0; i < count; i += 1) 
     { 
      if (random.NextDouble() <= ((float)subsetCount/(float)(count - i + 1))) 
      { 
       indexes[cur] = i; 
       cur += 1; 
       subsetCount -= 1; 
      } 
     } 
    } 
    else 
    { 
     for (int i = 0; i < count; i += 1) 
     { 
      indexes[i] = i; 
     } 
    } 

    for (int i = indexCount; i > 0; i -= 1) 
    { 
     int curIndex = random.Next(0, i); 
     yield return indexes[curIndex]; 

     indexes[curIndex] = indexes[i - 1]; 
    } 
}