c# - リスト内の要素を最初の要素にする最速の方法

Question

リストがあり、その要素の1つを最初の要素にするための短くて速い方法が必要です。以下のコードを使用して 10 番目の要素を選択し、最初に作成することを念頭に置いています。しかし、より良いソルンを探しています

tempList.Insert(0, tempList[10]);
tempList.RemoveAt(11);

Answer 1

残りの順序を気にしない場合は、実際に位置 0 と 10 の 2 つのアイテムを入れ替えることができます。挿入と削除を行うよりも優れていると思います。

var other = tempList[0];
tempList[0]=tempList[10];
tempList[10] = other;

使いやすくするために、これを List の拡張にすることもできます。

 public static void Swap<T>(this List<T> list, int oldIndex, int newIndex)
 { 
      // place the swap code here
 }

Answer 2

より良いパフォーマンスを得ることができる特別なケースがいくつかあります (単純にするために、値は常に取得元の位置の前に挿入されると想定しています)。

class Program
{
    const int Loops = 10000;
    const int TakeLoops = 10;
    const int ItemsCount = 100000;
    const int Multiplier = 500;
    const int InsertAt = 0;

    static void Main(string[] args)
    {
        var tempList = new List<int>();
        var tempDict = new Dictionary<int, int>();
        for (int i = 0; i < ItemsCount; i++)
        {
            tempList.Add(i);
            tempDict.Add(i, i);
        }

        var limit = 0;
        Stopwatch
            sG = new Stopwatch(),
            s1 = new Stopwatch(),
            s2 = new Stopwatch();
        TimeSpan
            t1 = new TimeSpan(),
            t2 = new TimeSpan();

        for (int k = 0; k < TakeLoops; k++)
        {
            var takeFrom = k * Multiplier + InsertAt;
            s1.Restart();
            for (int i = 0; i < Loops; i++)
            {
                tempList.Insert(InsertAt, tempList[takeFrom]);
                tempList.RemoveAt(takeFrom + 1);
            }
            s1.Stop();
            t1 += s1.Elapsed;
            s2.Restart();
            for (int i = 0; i < Loops; i++)
            {
                var e = tempDict[takeFrom];
                for (int j = takeFrom - InsertAt; j > InsertAt; j--)
                {
                    tempDict[InsertAt + j] = tempDict[InsertAt + j - 1];
                }
                tempDict[InsertAt] = e;
            }
            s2.Stop();
            t2 += s2.Elapsed;
            if (s2.Elapsed > s1.Elapsed || limit == 0)
                limit = takeFrom;
        }

        sG.Start();
        for (int k = 0; k < TakeLoops; k++)
        {
            var takeFrom = k * Multiplier + InsertAt;
            if (takeFrom >= limit)
            {
                for (int i = 0; i < Loops; i++)
                {
                    tempList.Insert(InsertAt, tempList[takeFrom]);
                    tempList.RemoveAt(takeFrom + 1);
                }
            }
            else
            {
                for (int i = 0; i < Loops; i++)
                {
                    var e = tempDict[takeFrom];
                    for (int j = takeFrom - InsertAt; j > InsertAt; j--)
                    {
                        tempDict[InsertAt + j] = tempDict[InsertAt + j - 1];
                    }
                    tempDict[InsertAt] = e;
                }
            }
        }
        sG.Stop();
        Console.WriteLine("List:       {0}", t1);
        Console.WriteLine("Dictionary: {0}", t2);
        Console.WriteLine("Optimized:  {0}", sG.Elapsed);

        /***************************
        List:       00:00:11.9061505
        Dictionary: 00:00:08.9502043
        Optimized:  00:00:08.2504321
        ****************************/
    }
}

上記の例でDictionary<int,int>は、各要素のインデックスを格納するために a が使用されています。insertAtとの間のギャップtakeFromが小さいほど、より良い結果が得られます。この間隔が長くなると、パフォーマンスが低下します。このギャップを評価し、その値に基づいて最適なブランチを選択することをお勧めします。