#retosMSDN: Solución al Reto 4 – Mezclando con eficiencia en C#

Aquí tienes la solución que proponemos para el cuarto de nuestros #retosMSDN: Reto 4 – Mezclando con eficiencia en C#, basado en una idea de @maktub82. Gracias Sergio por la idea y gracias una vez más a todos los que habéis participado en el reto.

 

Nuestra solución

En esta ocasión pedíamos velocidad a la hora de realizar las operaciones, además de cumplir con los requisitos del reto. Nosotros para nuestra solución hemos optado por un algoritmo de mezcla basado en el de Fisher-Yates, y hemos usado la clase Random para generar los números aleatorios. Como bien puntualizaba @lantoli hay algoritmos con mejores propiedades aleatorias pero más lentos, y clases con aleatoriedad más fuerte como RNGCryptoServiceProvider, pero también más lentas.

 

 public static class ListExtensions
{
    private static Random random = new Random();

    public static List<T> Shuffle<T>(this List<T> original)
    {
        T[] shuffled = original.ToArray();

        for (int index = shuffled.Length - 1; index > 0; index--)
        {
            int randomIndex = random.Next(index);

            T temp = shuffled[index];
            shuffled[index] = shuffled[randomIndex];
            shuffled[randomIndex] = temp;
        }

        return shuffled.ToList();
    }
}

 

El método Shuffle que hemos implementado es un método de extensión de la clase List, ya que los tests unitarios lo usan así:

 List<int> original = GenerateTestList(10000000);

List<int> shuffled = original.Shuffle();

El método Shuffle no viene de serie con la clase List, y no podemos heredar de la clase List.

El método además es genérico para poder funcionar con cualquier tipo de datos, y no sólo con los int que se usan en los tests unitarios para pruebas.

 

El código completo lo puedes encontrar en esta solución de Visual Studio 2013 que puedes descargarte de GitHub.

 

Vuestras soluciones

Muchos nos habéis enviado soluciones muy similares a la nuestra, pero manipulando directamente un objeto de tipo List, en lugar de un array. Algo como esto:

 

 public static List<T> Shuffle<T>(this List<T> original)
{
    List<T> shuffled = original.ToList();

    for (int index = shuffled.Count - 1; index > 0; index--)
    {
        int randomIndex = random.Next(index);

        T temp = shuffled[index];
        shuffled[index] = shuffled[randomIndex];
        shuffled[randomIndex] = temp;
    }

    return shuffled;
}

 

Tomando tiempos en mi máquina, este método tarda casi un 50% más de tiempo en mezclar 10 millones de elementos que el que utiliza el array.

Si utilizamos el Profiler de los tests unitarios con el método TestShuffle10000000Items, podemos ver donde se nos va más el tiempo cuando utilizamos el objeto List en lugar del array:

 

Donde más se nos va el tiempo es leyendo y escribiendo los elementos que intercambiamos de la lista. Usando un array en su lugar, encontrar un elemento por su índice es bastante más rápido.

 

@lantoli nos ha enviado una solución prácticamente idéntica a la nuestra, y @angel_g_santos nos ha enviado una solución también muy similar, aunque con una pequeña variación, ya que usa un método para intercambiar los elementos del array, cosa que apenas tiene impacto en el rendimiento del método Shuffle:

 

 public static class ListTExtensionMethods
{
    static readonly Random generator = new Random();

    public static List<TObject> Shuffle<TObject>(this List<TObject> obj)
    {
        TObject[] input = obj.ToArray();
        int swap;
        for (var top = input.Length - 1; top > 0; --top)
        {
            swap = generator.Next(top);
            Swap(ref input[top], ref input[swap]);
        }

        return new List<TObject>(input);
    }

    private static void Swap<TObject>(ref TObject first, ref TObject second)
    {
        TObject tmp = first;
        first = second;
        second = tmp;
    }
}

 

¡El próximo viernes 31 de octubre publicaremos el siguiente de nuestros #retosMSDN! Y si quieres retar al resto de la comunidad con tu propio reto, recuerda que puedes enviárnoslo a esmsdn@microsoft.com.

Un saludo,

Alejandro Campos Magencio (@alejacma)

Technical Evangelist

PD: Mantente informado de todas las novedades de Microsoft para los desarrolladores españoles a través del Twitter de MSDN, el Facebook de MSDN, el Blog de MSDN y la Newsletter MSDN Flash.