2

C＃のリストに関する速度テストをいくつか行いました。これは私が説明できない結果です。誰かが何が起こっているのか理解できることを願っています。

cloneList.Add（next）の前にcloneList.RemoveAt（cloneList.Count-1）が呼び出された場合、1000回の反復のミリ秒：xミリ秒。

cloneList.RemoveAt（cloneList.Count-1）がcloneList.Add（next）の前に呼び出されない場合の1000回の反復のミリ秒：少なくとも20xミリ秒。

もう1つのステートメントがある場合、私のコードは20倍速くなるようです（以下のコードを参照）。

        Stopwatch stopWatch = new Stopwatch();
        Random random = new Random(100);

        TimeSpan caseOneTimeSpan = new TimeSpan();
        TimeSpan caseTwoTimeSpan = new TimeSpan();


        int len = 1000;

        List<int> myList = new List<int>();
        myList.Capacity = len + 1;

        // filling the list
        for (int i = 0; i < len; i++)
            myList.Add(random.Next(1000));

        // number of tests (1000)
        for (int i = 0; i < 1000; i++)
        {
            List<int> cloneList = myList.ToList();
            int next = random.Next();

            // case 1 - remove last item before adding the new item
            stopWatch.Start();
            cloneList.RemoveAt(cloneList.Count - 1);
            cloneList.Add(next);
            caseOneTimeSpan += stopWatch.Elapsed;

            // reset stopwatch and clone list

            stopWatch.Reset();
            cloneList = myList.ToList();

            // case 2 - add without removing
            stopWatch.Start();
            cloneList.Add(next);
            caseTwoTimeSpan += stopWatch.Elapsed;


            stopWatch.Reset();

        }

        Console.WriteLine("Case 1: " + caseOneTimeSpan.TotalMilliseconds);
        Console.WriteLine("Case 2: " + caseTwoTimeSpan.TotalMilliseconds);
        Console.WriteLine("Case 2 / Case 1: " + caseTwoTimeSpan.TotalMilliseconds / caseOneTimeSpan.TotalMilliseconds);
4

2 に答える 2

3

リストにアイテムを追加する場合、2つの可能性があります。

  1. 内部バッファは、別のアイテムを追加するのに十分な大きさです。アイテムは次の無料の場所に配置されます。 速度：O（1）（これは最も一般的なケースです。）
  2. 内部バッファが十分に大きくありません。新しい、より大きなバッファを作成します。古いバッファから新しいバッファにすべてのアイテムをコピーします。次のアイテムを新しいバッファに追加します。 速度：O（n）（これは頻繁に発生することはありません）

ほとんどのAdd呼び出しはO（1）ですが、一部はO（n）です。

最後の項目の削除は常にO（1）です。

リストのサイズに依存することがあるためAdd、リストが大きい場合は時間がかかります（呼び出しに新しいバッファが必要な場合）。新しいアイテムを追加するときに常にアイテムを削除する場合は、内部バッファーに常に十分なスペースがあることを確認しています。

のCapacityプロパティを見て、内部バッファの現在のサイズを確認し、それを、リストに実際にあるアイテムの数であるListと比較することができます。Count（したがってCapacity-Count、バッファー内の空きアイテムの数があります。）実際のプログラムではあまり役に立ちませんが、アプリケーションのデバッグまたは開発時にこれらのツールを確認すると、その下で何が起こっているかを確認するのに役立ちます。

于 2012-09-13T21:03:15.050 に答える
0

これにより、違いがなくなるはずです。

        // reset stopwatch and clone list
        stopWatch.Reset();
        cloneList = myList.ToList();
        cloneList.Capacity = cloneList.Capacity + 1;   // add this

        // case 2 - add without removing
        stopWatch.Start();
        cloneList.Add(next);
        caseTwoTimeSpan += stopWatch.Elapsed;
于 2012-09-13T21:08:49.410 に答える