6

これで、配列にメモリを動的に割り当てるためのアルゴリズムができました。

  • 配列がいっぱいの場合は、2倍のサイズの新しい配列を作成し、アイテムをコピーします。
  • 配列が4分の1いっぱいの場合は、半分のサイズの新しい配列を作成し、アイテムをコピーします。

これは、新しく割り当てられた配列に要素をコピーするという余分なオーバーヘッドがあるにもかかわらず、動的メモリ割り当てのためのかなり高速なアルゴリズムです。

  1. より高速な、List<T>または配列に基づくそのようなアルゴリズムは何ですか？何を使うことをお勧めしますか？

  2. List<T>内部データ構造として単純な配列を使用しますか？

4

6 に答える 6

9

あなたの質問に答えるには：

確かに、C＃のList<T>実装では、次のような内部配列を使用しています。

  1. シリアル化可能
  2. スレッドセーフ
  3. 実装IEnumerable<T>（つまり、LINQクエリ、foreachedなど）
  4. バイナリ検索

等々

List<T>したがって、私はあなたにあなた自身のリストの代わりに使用するようにお願いします。

ああ、ところで、MicrosoftのソースコードがList<T>必要な場合は、ここにあります

List.cs

編集

EnsureCapacityinのソースコードList<T>は次のとおりです。

    // Ensures that the capacity of this list is at least the given minimum
    // value. If the currect capacity of the list is less than min, the
    // capacity is increased to twice the current capacity or to min,
    // whichever is larger.
    private void EnsureCapacity(int min) {
        if (_items.Length < min) {
            int newCapacity = _items.Length == 0? _defaultCapacity : _items.Length * 2;
            if (newCapacity < min) newCapacity = min;
            Capacity = newCapacity;
        }
    }
于 2013-02-16T18:38:41.103 に答える
6

特に信じる理由がない限り、C＃に付属のライブラリを使用することをお勧めします。これらの実装は、適切に実装され、十分にデバッグされ、十分にテストされています。

説明しているデータ構造は動的配列データ構造の標準実装であり、ほとんどの言語はこれをデフォルトのリスト実装として使用します。のドキュメントをList<T>見ると、この実装を使用しているようです。List<T>そのドキュメントには内部容量への参照があり、サイズが容量よりも小さい限り、O（1）の追加が保証されているためです。

つまり、必要がない限り、車輪の再発明は避けてください。

お役に立てれば！

于 2013-02-16T18:35:31.913 に答える
4

List<T>内部で配列を使用し、同様の戦略を使用します。長さが配列の長さを超える場合は、配列のサイズが2倍になります。ただし、サイズがはるかに小さい場合でも、サイズは小さくなりません。

の関連する方法mscorlib：

private void EnsureCapacity(int min)
{
    if (this._items.Length < min)
    {
        int num = (this._items.Length == 0) ? 4 : (this._items.Length * 2);
        if (num < min)
        {
            num = min;
        }
        this.Capacity = num;
    }
}

配列のサイズ変更は、実際にはのセッターで行われList<T>.Capacityます。

于 2013-02-16T18:35:23.187 に答える
2

はい、オブジェクトを保持するために内部的にList<T>使用します。T[]

.NET 4.0のソースコードから覚えている限り、新しいオブジェクトを追加する前に、配列に新しい数のオブジェクトを保持するのに十分な容量があることを確認します。既存の配列が新しい数のオブジェクトを保持できない場合は、2倍のサイズの新しい配列に置き換えられ、すべてのオブジェクトとすべての既存の参照が新しい配列にコピーされます。

于 2013-02-16T18:35:30.653 に答える
2

車輪の再発明をする必要はありません。

MSDNから：

容量は、サイズ変更が必要になる前にList <（Of <（T>）>）が格納できる要素の数であり、Countは、実際にList <（Of <（T>）>）にある要素の数です。

容量は常にカウント以上です。要素の追加中にカウントが容量を超える場合、古い要素をコピーして新しい要素を追加する前に内部配列を自動的に再割り当てすることにより、容量が増加します。

TrimExcessメソッドを呼び出すか、Capacityプロパティを明示的に設定することにより、容量を減らすことができます。Capacityの値が明示的に設定されている場合、指定された容量に対応するために内部配列も再割り当てされ、すべての要素がコピーされます。

このプロパティの値の取得はO（1）操作です。プロパティの設定はO（n）操作です。ここで、nは新しい容量です。

于 2013-02-18T04:08:26.470 に答える
0

それは基本的にList<T>（そして他の多くの言語の動的配列）も同様に行うことです。サイズ変更の要素は異なる場合があり、要素を削除するときにバッキング配列自体を縮小することはないと思いTrimToSizeますが、自分で設定することもできCapacityます。これにより、クライアントコードでこの機能をうまく使用できれば、より効率的な戦略が可能になります。しかし、基本的には、漸近的に同等です。

List<T>どちらを使用するかについて：ユースケースに最適ではなく、違いが重要である（明らかにこの知識をまだ持っていない）冷たくて硬いデータがない限り、それを使用する必要があります。あなた自身の実装はバグが多く、機能が豊富ではなく（cf. IEnumerable<T>、IList<T>多数のメソッド）、最適化されておらず、広く認識されておらず、他のライブラリでは受け入れられません（したがって、高価なコピーを作成するか、少なくともより多くの作業を行う必要がありますList<T>相互作用するために）など、そしておそらく絶対に何も得られないでしょう。

于 2013-02-16T18:36:10.127 に答える