21

リストが与えられた場合:

List<object> SomeList = new List<object>();

やっている：

SomeList.Insert(i, val);

対。

SomeList.Add(val);

パフォーマンスにペナルティはありますか? その場合、どのように依存するか:
- i- 挿入インデックス
- SomeList.Count- リストのサイズ

4

7 に答える 7

24

List クラスは、ArrayList クラスに相当する一般的なクラスです。必要に応じてサイズが動的に増加する配列を使用して、IList ジェネリック インターフェイスを実装します。

（ソース）

内部データが配列として格納されていることを意味するため、実行するinsertにはすべての要素を移動してスペースを空ける必要がある可能性が高いため、その複雑さは O(N)addですが、(償却された) 定数時間ですO(1) 操作なので、はい。

要約 - はい、ほとんどの場合遅くなり、リストが大きくなるほど遅くなります。

于 2013-09-03T08:20:22.993 に答える
13

疑問がある場合は、経験的な実験を実行してください。

List<object> SomeList = new List<object>();

Stopwatch sw = new Stopwatch();
sw.Start();
for (var i = 0; i < 100000; i++)
    SomeList.Insert(0, String.Empty);
sw.Stop();
Console.WriteLine(sw.Elapsed.TotalMilliseconds);
sw.Reset();

SomeList = new List<object>();
sw.Start();
for (var i = 0; i < 100000; i++)
    SomeList.Add(String.Empty);
sw.Stop();
Console.WriteLine(sw.Elapsed.TotalMilliseconds);

私のInsertマシンでは2800ミリ秒かかります。0.8msAddかかります。そうです、Insertパフォーマンスははるかに低くなります。

于 2013-09-03T08:25:51.327 に答える
8

これについてはすでに完全に回答されていることを認識していますが、この情報は MSDN ドキュメントですぐに入手できることを指摘したいと思います。

状態のドキュメントList<T>.Insert():

このメソッドは O(n) 操作です。ここで、n はカウントです。

状態のドキュメントList<T>.Add():

Count が Capacity より小さい場合、このメソッドは O(1) 操作です。新しい要素に対応するために容量を増やす必要がある場合、このメソッドは O(n) 操作になります。ここで、n はカウントです。

リストの前後に頻繁に追加を実行したい状況があるためにこの質問をしている場合、使用する適切なデータ構造はDeque.

Stephen Clearyは、ここで適切な Deque 実装を提供しています: http://nitodeque.codeplex.com/

于 2013-09-03T08:36:46.917 に答える
3

Insert私の最初の考えは、「はい、リスト内のすべてのアイテムを1スロット移動して新しいアイテム用のスペースを空ける必要があるため、パフォーマンスが低下する」というものでしたが、その後、質問をより注意深く読みました。そう：

一般にInsert、リスト内のすべてのアイテムを移動して新しいアイテム用のスペースを確保する必要があるため、(おそらくもっと多くの) 時間がかかります。そのため、リストの長さに対する O(n) 操作です (リストが容量がいっぱいになると、サイズも変更する必要がありますが、それでも O(n) 操作です)。一方、Add何も移動する必要がなく、新しいアイテムを単純に追加するだけなので、O(1) 操作になります (上記のようにリストのサイズを変更する必要がない場合)。

この特定の例では、最初はリストが空で、パフォーマンスの違いはありません。

もちろん、文書化されたパフォーマンスの問題がない限り、意図に基づいてメソッドを選択する必要があるため、これはすべて意味のないものです。

于 2013-09-03T08:27:32.573 に答える
3

空のリストの場合も同様です。

しかし、前に挿入するには、バッキング配列全体を右に1つシフトする必要があるため、それ以外の場合は遅くする必要があります*。

Add※増毛の原因となる場合は除きCapacityます。

于 2013-09-03T08:27:46.287 に答える
2

もちろんそうです。

は配列によってサポートされているためList<T>、リストの先頭に挿入する操作では、配列の他のすべての要素を移動 (またはコピー) する必要があります。リストの最後に追加する操作は、リスト内のアイテムの数に関係なく、一定の時間で発生します。

于 2013-09-03T08:26:25.720 に答える
2

私は Pattermiester のパフォーマンス テストをもとに構築しました。挿入について考えるとき、私は配列を考えます。配列に追加するには、挿入するインデックスを指定する必要があります。Add(0, object) を実行するのは直感に反するようです。また、パフォーマンス テストを実行するときは、常に最初にスロー アウェイ ランを作成します。場合によっては、実際よりも時間がかかることがあります。

結果

2.282 - Throw Away Run
2.6847 - List Insert By Index without Capacity
10544.9766 - List Insert At Index 0 without Capacity
1.8426 - List Add without Capacity
2.0835 - List Insert By Index with Capacity
1.4952 - List Add with Capacity
9323.699 - List Insert at Index 0 with Capacity

コード

        var size = 200000;
        //First test sometimes has a bad count
        List<object> SomeList = new List<object>();
        Stopwatch sw = new Stopwatch();
        sw.Start();
        for (var i = 0; i < size; i++)
            SomeList.Insert(i, String.Empty);
        sw.Stop();
        Console.WriteLine(sw.Elapsed.TotalMilliseconds + " - Throw Away Run");
        sw.Reset();

        SomeList = new List<object>();
        sw = new Stopwatch();
        sw.Start();
        for (var i = 0; i < size ; i++)
            SomeList.Insert(i, String.Empty);
        sw.Stop();
        Console.WriteLine(sw.Elapsed.TotalMilliseconds+" - List Insert By Index without Capacity");
        sw.Reset();

        SomeList = new List<object>();
        sw = new Stopwatch();
        sw.Start();
        for (var i = 0; i < size; i++)
            SomeList.Insert(0, String.Empty);
        sw.Stop();
        Console.WriteLine(sw.Elapsed.TotalMilliseconds + " - List Insert At Index 0 without Capacity");
        sw.Reset();

        SomeList = new List<object>();
        sw.Start();
        for (var i = 0; i < size; i++)
            SomeList.Add(String.Empty);
        sw.Stop();
        Console.WriteLine(sw.Elapsed.TotalMilliseconds+" - List Add without Capacity");
        sw.Reset();

        SomeList = new List<object>(size);
        sw = new Stopwatch();
        sw.Start();
        for (var i = 0; i < size; i++)
            SomeList.Insert(i, String.Empty);
        sw.Stop();
        Console.WriteLine(sw.Elapsed.TotalMilliseconds+" - List Insert By Index with Capacity");
        sw.Reset();

        SomeList = new List<object>(size);
        sw.Start();
        for (var i = 0; i < size; i++)
            SomeList.Add(String.Empty);
        sw.Stop();
        Console.WriteLine(sw.Elapsed.TotalMilliseconds+" - List Add with Capacity");
        sw.Reset();

        SomeList = new List<object>(size);
        sw = new Stopwatch();
        sw.Start();
        for (var i = 0; i < size; i++)
            SomeList.Insert(0, String.Empty);
        sw.Stop();
        Console.WriteLine(sw.Elapsed.TotalMilliseconds + " - List Insert at Index 0 with Capacity");

したがって、追加は挿入よりも少しパフォーマンスが高いようです。ただし、Insert(0, "") を使用している場合は、確実にパフォーマンスが低下します。最高のパフォーマンスが必要な場合は、容量を使用してください。

于 2020-02-18T03:54:48.120 に答える