Y a-t-il une différence de performance entre ces deux algorithmes pour mélanger un IEnumerable?

Question

Ces deux questions donnent algorthims similaires pour brouiller un IEnumerable:

• C#: Is using Random and OrderBy a good shuffle algorithm?
• Can you enumerate a collection in C# out of order?

Voici les deux méthodes côte à côte:

public static IEnumerable<T> Shuffle1<T> (this IEnumerable<T> source) 
{ 
    Random random = new Random(); 
    T [] copy = source.ToArray(); 

    for (int i = copy.Length - 1; i >= 0; i--) { 
     int index = random.Next (i + 1); 
     yield return copy [index]; 
     copy [index] = copy [i]; 
    } 
} 


public static IEnumerable<T> Shuffle2<T> (this IEnumerable<T> source) 
{ 
    Random random = new Random(); 
    List<T> copy = source.ToList(); 

    while (copy.Count > 0) { 
     int index = random.Next (copy.Count); 
     yield return copy [index]; 
     copy.RemoveAt (index); 
    } 
} 

Ils sont fondamentalement identique, sauf un utilise un List, et on utilise un tableau. Conceptuellement, le second me semble plus clair. Mais y a-t-il un avantage substantiel de performance à gagner en utilisant un tableau? Même si le temps Big-O est le même, s'il est plusieurs fois plus rapide, cela pourrait faire une différence notable.

Answer 1

La deuxième version sera probablement un peu plus lente à cause de RemoveAt. Les listes sont en réalité des tableaux qui se développent lorsque vous ajoutez des éléments, et ainsi, l'insertion et la suppression au milieu sont lentes (en fait, MSDN indique que RemoveAt a une complexité O (n)).

Quoi qu'il en soit, le mieux serait simplement d'utiliser un profileur pour comparer les deux méthodes.

Answer 2

Le premier algorithme est O (n) car il a une boucle qui effectue un échange O (1) à chaque itération. Le deuxième algorithme est O (n^2) car il effectue une opération O (n) RemoveAt à chaque itération. De plus, les indexeurs sur les listes sont plus lents que les index sur les tableaux car le premier est un appel de méthode alors que le second est une instruction IL.

Donc, sur les deux le premier est susceptible d'être plus rapide. Cela dit, si vous êtes après la performance, pourquoi s'embêter à donner les résultats? Il est déjà en train de convertir en un tableau donc il suffit de mélanger et de renvoyer le tableau directement (ou de le mettre dans un ReadOnlyCollection<T> si vous êtes inquiet au sujet des modifications), ce qui est probablement encore plus rapide. Sur une note de côté, les deux méthodes ont des bogues que le comportement de Random lorsqu'il est utilisé par plusieurs threads est indéfini, donc ils devraient probablement utiliser un thread-safe random number generator.

Answer 3

Le premier ne compile pas, bien qu'il soit apparent que vous essayez de réifier l'énumérable, puis d'implémenter Fisher-Yates; C'est probablement la bonne approche, et il ne devrait pas être clair pour quiconque a déjà battu un tableau avant. La seconde utilisant RemoveAt est mauvaise pour les raisons indiquées par d'autres commentateurs.

EDIT: Votre version supérieure semble être correcte maintenant, et c'est un bon moyen de le faire.