IEnumerableをシャッフルするためのこれらの2つのアルゴリズムのパフォーマンスに違いはありますか？

Question

これら二つの質問は、IEnumerableをシャッフルするために同様のalgorthimsを与える：ここで

• C#: Is using Random and OrderBy a good shuffle algorithm?
• Can you enumerate a collection in C# out of order?は2つの方法ですサイド・バイ・サイド：彼らはある

  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); 
      } 
  } 
  

  基本的に同一ですが、Listを使用し、1つは配列を使用します。概念的には、第2のものは私には明らかです。しかし、配列を使用することで得られる大きなパフォーマンス上の利点はありますか？たとえBig-Oの時間が同じであっても、それが数倍速ければ、それは顕著な違いを作り出すことができる。

Answer 1

2番目のバージョンは、おそらくRemoveAtのために少し遅くなります。リストは実際に要素を追加すると拡大する配列なので、途中で挿入と削除が遅くなります（実際にはRemoveAtにO（n）の複雑さがあります）。

とにかく、プロファイラを使用して両方の方法を比較するのが最も良い方法です。

Answer 2

最初のアルゴリズムは、各反復でO（1）スワップを実行するループを持つため、O（n）です。 2番目のアルゴリズムは、各反復でO（n）RemoveAt操作を実行するので、O（n^2）です。さらに、リストのインデクサは配列のインデックスよりも遅くなります。これは、前者がメソッド呼び出しであり、後者がIL命令であるためです。

したがって、2つのうちの最初のものは、より高速になる可能性があります。それは、あなたがパフォーマンスの後にいる場合、なぜ結果を生み出すかと思いますか？すでに配列に変換されていますので、その場所をシャッフルして配列を直接返します（または、変更する人が気になる場合はReadOnlyCollection<T>で囲んでください）。

両方のメソッドには、Randomの動作が複数のスレッドで使用されている場合、定義されていないため、おそらくthread-safe random number generatorを使用する必要があるというバグがあります。

Answer 3

最初のものはコンパイルされませんが、あなたが列挙可能なものを正式化しようとしていることは明らかですが、その後Fisher-Yatesを実装します。それはおそらく正しいアプローチであり、前に配列をシャッフルしたことがある人にとっては不明瞭ではありません。 RemoveAtを使用して2番目のは、他のコメント者によって記載された理由で悪いです。

EDIT：あなたのトップインプリメンテーションは正しいように見えますが、これは良い方法です。