60

今、 vsに関するいくつかの投稿List<T>LinkedList<T>を読んだので、いくつかの構造を自分でベンチマークすることにしました。Stack<T>Queue<T>、およびフロント/エンドとの間でデータを追加および削除することにより、List<T>ベンチマークLinkedList<T>を行いました。ベンチマーク結果は次のとおりです。

               Pushing to Stack...  Time used:      7067 ticks
              Poping from Stack...  Time used:      2508 ticks

               Enqueue to Queue...  Time used:      7509 ticks
             Dequeue from Queue...  Time used:      2973 ticks

    Insert to List at the front...  Time used:   5211897 ticks
RemoveAt from List at the front...  Time used:   5198380 ticks

         Add to List at the end...  Time used:      5691 ticks
  RemoveAt from List at the end...  Time used:      3484 ticks

         AddFirst to LinkedList...  Time used:     14057 ticks
    RemoveFirst from LinkedList...  Time used:      5132 ticks

          AddLast to LinkedList...  Time used:      9294 ticks
     RemoveLast from LinkedList...  Time used:      4414 ticks

コード:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace Benchmarking
{
    static class Collections
    {
        public static void run()
        {
            Random rand = new Random();
            Stopwatch sw = new Stopwatch();
            Stack<int> stack = new Stack<int>();
            Queue<int> queue = new Queue<int>();
            List<int> list1 = new List<int>();
            List<int> list2 = new List<int>();
            LinkedList<int> linkedlist1 = new LinkedList<int>();
            LinkedList<int> linkedlist2 = new LinkedList<int>();
            int dummy;


            sw.Reset();
            Console.Write("{0,40}", "Pushing to Stack...");
            sw.Start();
            for (int i = 0; i < 100000; i++)
            {
                stack.Push(rand.Next());
            }
            sw.Stop();
            Console.WriteLine("  Time used: {0,9} ticks", sw.ElapsedTicks);
            sw.Reset();
            Console.Write("{0,40}", "Poping from Stack...");
            sw.Start();
            for (int i = 0; i < 100000; i++)
            {
                dummy = stack.Pop();
                dummy++;
            }
            sw.Stop();
            Console.WriteLine("  Time used: {0,9} ticks\n", sw.ElapsedTicks);


            sw.Reset();
            Console.Write("{0,40}", "Enqueue to Queue...");
            sw.Start();
            for (int i = 0; i < 100000; i++)
            {
                queue.Enqueue(rand.Next());
            }
            sw.Stop();
            Console.WriteLine("  Time used: {0,9} ticks", sw.ElapsedTicks);
            sw.Reset();
            Console.Write("{0,40}", "Dequeue from Queue...");
            sw.Start();
            for (int i = 0; i < 100000; i++)
            {
                dummy = queue.Dequeue();
                dummy++;
            }
            sw.Stop();
            Console.WriteLine("  Time used: {0,9} ticks\n", sw.ElapsedTicks);


            sw.Reset();
            Console.Write("{0,40}", "Insert to List at the front...");
            sw.Start();
            for (int i = 0; i < 100000; i++)
            {
                list1.Insert(0, rand.Next());
            }
            sw.Stop();
            Console.WriteLine("  Time used: {0,9} ticks", sw.ElapsedTicks);
            sw.Reset();
            Console.Write("{0,40}", "RemoveAt from List at the front...");
            sw.Start();
            for (int i = 0; i < 100000; i++)
            {
                dummy = list1[0];
                list1.RemoveAt(0);
                dummy++;
            }
            sw.Stop();
            Console.WriteLine("  Time used: {0,9} ticks\n", sw.ElapsedTicks);


            sw.Reset();
            Console.Write("{0,40}", "Add to List at the end...");
            sw.Start();
            for (int i = 0; i < 100000; i++)
            {
                list2.Add(rand.Next());
            }
            sw.Stop();
            Console.WriteLine("  Time used: {0,9} ticks", sw.ElapsedTicks);
            sw.Reset();
            Console.Write("{0,40}", "RemoveAt from List at the end...");
            sw.Start();
            for (int i = 0; i < 100000; i++)
            {
                dummy = list2[list2.Count - 1];
                list2.RemoveAt(list2.Count - 1);
                dummy++;
            }
            sw.Stop();
            Console.WriteLine("  Time used: {0,9} ticks\n", sw.ElapsedTicks);


            sw.Reset();
            Console.Write("{0,40}", "AddFirst to LinkedList...");
            sw.Start();
            for (int i = 0; i < 100000; i++)
            {
                linkedlist1.AddFirst(rand.Next());
            }
            sw.Stop();
            Console.WriteLine("  Time used: {0,9} ticks", sw.ElapsedTicks);
            sw.Reset();
            Console.Write("{0,40}", "RemoveFirst from LinkedList...");
            sw.Start();
            for (int i = 0; i < 100000; i++)
            {
                dummy = linkedlist1.First.Value;
                linkedlist1.RemoveFirst();
                dummy++;
            }
            sw.Stop();
            Console.WriteLine("  Time used: {0,9} ticks\n", sw.ElapsedTicks);


            sw.Reset();
            Console.Write("{0,40}", "AddLast to LinkedList...");
            sw.Start();
            for (int i = 0; i < 100000; i++)
            {
                linkedlist2.AddLast(rand.Next());
            }
            sw.Stop();
            Console.WriteLine("  Time used: {0,9} ticks", sw.ElapsedTicks);
            sw.Reset();
            Console.Write("{0,40}", "RemoveLast from LinkedList...");
            sw.Start();
            for (int i = 0; i < 100000; i++)
            {
                dummy = linkedlist2.Last.Value;
                linkedlist2.RemoveLast();
                dummy++;
            }
            sw.Stop();
            Console.WriteLine("  Time used: {0,9} ticks\n", sw.ElapsedTicks);
        }
    }
}

違いはとても劇的です!

ご覧のとおり、 と のパフォーマンスStack<T>Queue<T>高速で同等です。これは予想どおりです。

の場合List<T>、フロントとエンドの使い分けが違いすぎる!そして驚いたことに、最後からの追加/削除のパフォーマンスは、実際には のパフォーマンスに匹敵しStack<T>ます。

の場合LinkedList<T>、フロントでの操作は (-er よりもList<T>)高速ですが、エンドの場合は、エンドでの操作を削除するのが非常に遅くなります。


だから...専門家は次のことを説明できますか?

  1. Stack<T>の使用と終了のパフォーマンスの類似List<T>
  2. の先頭と末尾の使用の違いList<T>、および
  3. end of の使用LinkedList<T>非常に遅い理由 ( CodesInChaos のおかげでLast()、Linq の の使用によるコーディング エラーであるため、該当しません)?

List<T>フロントをうまく処理できない理由はわかっていると思います...そうList<T>するときにリスト全体を前後に移動する必要があるためです。私が間違っている場合は修正してください。

PS MySystem.Diagnostics.Stopwatch.Frequency2435947で、プログラムは .NET 4 Client Profile を対象としており、Windows 7 Visual Studio 2010 で C# 4.0 でコンパイルされています。

4

6 に答える 6

40

1について:

Stack<T>List<T>のパフォーマンスが類似していることは驚くべきことではありません。どちらも倍増戦略で配列を使用することを期待しています。これにより、償却された一定時間の追加が発生します。

使用できるList<T>場所ならどこでも使用できますがStack<T>コードの表現力が低下します

2について:

List<T>フロントをうまく処理できない理由はわかっていると思います...そうList<T>するときにリスト全体を前後に移動する必要があるためです。

そのとおりです。最初に要素を挿入/削除すると、すべての要素が移動するため、コストがかかります。一方、最初に要素を取得または置換するのは安価です。

3について:

あなたの遅いLinkedList<T>.RemoveLast値は、ベンチマーク コードの間違いです。

二重にリンクされたリストの最後の項目を削除または取得するのは安価です。その場合は安いLinkedList<T>ということです。RemoveLastLast

しかし、あなたはLastプロパティを使用していませんでしたが、LINQ の拡張メソッドを使用していましたLast()。実装されていないコレクションではIList<T>、リスト全体を反復し、O(n)ランタイムを提供します。

于 2012-11-03T17:11:16.577 に答える
13

List<T>動的な過剰割り当て配列です(他の多くの言語の標準ライブラリにも見られるデータ構造)。これは、内部で「静的」配列(サイズ変更できない配列、.NETでは単に「配列」と呼ばれる)を使用することを意味します。これは、リストのサイズよりも大きい場合があります。次に、追加すると、単にカウンターがインクリメントされ、以前は使用されていなかった内部アレイの次のスロットが使用されます。配列は、すべてのアイテムを収容するために内部配列が小さくなった場合にのみ再割り当てされます(すべての要素をコピーする必要があります)。その場合、配列のサイズは(定数ではなく)係数(通常は2)だけ増加します。

これにより、最悪の場合でも、追加の償却時間計算量(基本的に、操作の長いシーケンスにわたる操作あたりの平均時間)がO(1)になることが保証されます。前に追加する場合、そのような最適化は実行できません(少なくとも、ランダムアクセスと最後に追加するO(1)の両方を維持している間は実行できません)。すべての要素をコピーして新しいスロットに移動する必要があります(最初のスロットに追加された要素用のスペースを作成します)。Stack<T> 同じことをします。一方の端(速い方)でしか操作しないため、前面に追加することとの不一致に気付くことはありません。

リンクリストの終わりを取得することは、リストの内部に大きく依存します。最後の要素への参照を維持することはできますが、これによりリスト上のすべての操作がより複雑になり、(手元に例がありませんが)一部の操作がはるかに高価になる可能性があります。このような参照がないため、最後に追加するには、リンクリストのすべての要素を調べて最後のノードを見つける必要があります。これは、もちろん、重要なサイズのリストの場合は非常に遅くなります。

@CodesInChaosが指摘しているように、リンクリストの操作に欠陥がありました。上記のように、現在表示されている終了の高速検索はLinkedList<T>、最後のノードへの参照を明示的に維持していることが原因である可能性があります。どちらの端にもない要素を取得するのはまだ遅いことに注意してください。

于 2012-11-03T17:06:20.757 に答える
5

速度は、基本的に、アイテムの挿入、削除、または検索に必要な操作の数によって決まります。既にお気付きのように、リストにはメモリ転送が必要です。

スタックはリストであり、最上位の要素でのみアクセスできます。コンピューターは、それがどこにあるかを常に認識しています。

リンクされたリストは別のものです。リストの先頭はわかっているため、先頭から追加または削除するのは非常に高速ですが、最後の要素を見つけるには時間がかかります。最後の要素OTOHの場所をキャッシュすることは、追加する価値があるだけです。削除するには、完全なリストから 1 つの要素を引いたものをトラバースして、最後の要素への「フック」またはポインターを見つける必要があります。

数値を見るだけで、各データ構造の内部構造について知識に基づいた推測を行うことができます。

  • 予想通り、スタックからのポップは高速です
  • スタックへのプッシュは遅くなります。リストの最後に追加するよりも遅くなります。なんで?
    • どうやら、スタックのアロケーション ユニット サイズの方が小さいようです。スタック サイズを 100 だけ増やすことができますが、リストの拡大は 1000 単位で行うことができます。
  • リストは静的配列のようです。先頭のリストにアクセスするにはメモリ転送が必要で、リストの長さに比例して時間がかかります。
  • 基本的なリンクされたリストの操作は、それほど長くはかからないはずです。通常、必要なのは
    • new_item.next = list_start; list_start = new_item; // たす
    • list_start = list_start.next; // 削除する
    • ただし、addLast は非常に高速であるため、リンクされたリストに追加または削除するときにも、最後の要素へのポインターを更新する必要があることを意味します。したがって、余分な簿記があります。
  • 二重にリンクされたリスト OTOH を使用すると、リストの両端での挿入と削除が比較的高速になります (より良いコードでは DLL を使用することがわかっています)。
    • 前の項目と次の項目へのリンクも簿記の作業を 2 倍にします
于 2012-11-03T17:03:47.857 に答える
1

スタックとリストの終わりを使用した場合のパフォーマンスの類似性、

delnanが説明しているように、どちらも内部で単純な配列を使用しているため、最後に作業するときは非常によく似た動作をします。スタックは、最後のオブジェクトにアクセスするだけのリストであることがわかります。

リストの前と最後の使用の違い

あなたはすでにそれを正しく疑っています。リストの先頭を操作するということは、基になる配列を変更する必要があることを意味します。アイテムを追加するということは、通常、削除するのと同じように、他のすべての要素を1つシフトする必要があることを意味します。リストの両端を操作することがわかっている場合は、リンクリストを使用することをお勧めします。

LinkedListの終わりを使用するのがとても遅い理由は?

通常、リンクリストの要素の挿入と削除は、最大2つのポインターを変更するだけでよいため、任意の位置で一定時間で実行できます。問題はちょうどその位置に到達することです。通常のリンクリストには、最初の要素へのポインタがあります。したがって、最後の要素に到達したい場合は、すべての要素を反復処理する必要があります。リンクリストで実装されたキューは通常、最後の要素への追加のポインタを持つことでこの問題を解決するため、要素を一定時間で追加することも可能です。より洗練されたデータ構造は、最初と最後の要素への両方のポインターを持ち、各要素に次と前の要素へのポインターも含まれる二重リンクリストです。

これについて学ぶ必要があるのは、単一の目的のために作成された多くの異なるデータ構造があり、それらは非常に効率的に処理できるということです。正しい構造を選択することは、あなたが何をしたいかに大きく依存します。

于 2012-11-03T17:24:53.243 に答える
1

私には Java のバックグラウンドがあり、あなたの質問は特定の言語よりも一般的なデータ構造に関連していると思います。また、私の発言が間違っていたら申し訳ありません。

1. Stack と End of List を使用した場合のパフォーマンスの類似性

2. リストの先頭と末尾の使用の違い、および

少なくとも Java では、スタックは配列を使用して実装されます(C# の場合ではない場合は申し訳ありません。実装のソースを参照できます)。リストの場合も同様です。配列の場合は通常、最初の挿入に対応するために配列内の既存の値を下に移動する必要があるため、最後のすべての挿入は最初よりも時間がかかりません。

Stack.java ソースとそのスーパークラスVectorへのリンク

3. LinkedList の末尾の使用が非常に遅い理由は?

LinkedListはランダム アクセスを許可せず、挿入ポイントに到達する前にノードをトラバースする必要があります。最後のノードのパフォーマンスが遅いことがわかった場合は、LinkedList の実装は単一リンク リストにする必要があると思います。最後に要素にアクセスする際に最適なパフォーマンスを得るには、二重にリンクされたリストを検討することをお勧めします。

http://en.wikipedia.org/wiki/Linked_list

于 2012-11-03T17:03:31.157 に答える