C＃では、リストを特定の場所に回転させるにはどうすればよいですか？

Question

リストを特定の場所に回転させるコードを書いていますが、以下のコードは動作しますが、これを行うより効率的な方法があるかどうかを知りたいと思います。

public void Test8(List<int> items, int places) 
    { 
     int nums; 
     for (int i = 0; i < places; i++) 
     { 
      nums = items[items.Count() - 1]; 
      items.RemoveAt(items.Count - 1); 
      items.Insert(0, nums); 

     } 
    } 

Answer 1

リスト要素を挿入したり削除したりしています。それに関連するオーバーヘッドがあります。リストはインデックスでアクセスできます。したがって、リストをループして要素をその位置に移動させることができます。リストデータを上書きしないように一時的な整数変数を使用する必要があります。

Answer 2

また、ローテーションが無意味でないことを確認すること、つまり5Kを削除して5K倍の長さのリストを回転させることは意味がありません。前にplaces%=items.Count;のようにあなたは回転を開始します。

Answer 3

これは古典的なコンピュータ科学の問題です。

// If we want to shift two places, start with an array 
[1, 2, 3, 4, 5, 6, 7, 8] 
// Then reverse the entire array 
[8, 7, 6, 5, 4, 3, 2, 1] 
// Then reverse the first n elements, two in our case 
[7, 8, 6, 5, 4, 3, 2, 1] 
^^^^ 
// Then reverse the remaining items 
[7, 8, 1, 2, 3, 4, 5, 6] 
     ^^^^^^^^^^^^^^^^ 

または、コードとして：

static void Reverse(List<int> items, int posFrom, int posTo) 
{ 
    // Helper to reverse a sub portion of an array in place 
    while (posFrom < posTo) 
    { 
     // Swap the first and last items 
     int temp = items[posFrom]; 
     items[posFrom] = items[posTo]; 
     items[posTo] = temp; 
     // Shrink down to the next pair of items 
     --posTo; 
     ++posFrom; 
    } 
} 

static void Test8(List<int> items, int places) 
{ 
    // Sanity, if we try to rotate more than there are 
    // items in the array, it just loops around 
    places %= items.Count; 
    // Reverse the entire array 
    Reverse(items, 0, items.Count - 1); 
    // Reverse the first group of items 
    Reverse(items, 0, places - 1); 
    // Reverse the second group of items 
    Reverse(items, places, items.Count - 1); 
} 

これはO（N）時間の関わらずであるわずかに速いだ一つの技術は、アレイの2つのチャンクを逆次いで、アレイ全体を逆にすることですシフトサイズ

Answer 4

サーキュラーアレイのQUEUE（実際にはリストよりもメモリ管理が優れています）を使用して実装する方が速くなります。これは既存のデータを物理的に回転させる必要がないため、元のコードよりも速くなければなりません。

ところで、あなたは元のために、あなたの知識を豊かにするのStackOverflowで他の文献を読むことができます：ここで

• Easiest way to Rotate a List in c#
• Performance differences... so dramatic?

Answer 5

は同様の質問です： C# Collection - Order by an element (Rotate)

また、これを試してください：

static void Main(string[] args) 
{ 
    var items = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; 
    var rotatedItems = Rotate(items, 4); 
    // rotated is now {5, 6, 7, 8, 9, 1, 2, 3, 4}    
    Console.WriteLine(string.Join(", ", rotatedItems)); 
    Console.Read(); 
} 

public static IEnumerable<int> Rotate(IEnumerable<int> items, int places) 
{ 
    return items.Skip(places).Concat(items.Take(places)); 
}