4

値を動的に追加/削除できるため、arraylist の構築に使用されるデータ構造。

リンクリストを使用していると想定していましたが、グーグルを行った後、ベクトルを使用していることがわかりました..しかし、それについての詳細はありません。

4

5 に答える 5

14

最新のプロセッサでは、メモリ キャッシュが重要です。キャッシュを効率的に使用すると、非常に大きな違いが生じます。プログラムがコンテンツがキャッシュされていないアドレスにアクセスし、非常に遅いメモリバスがデータを提供するのを待つと、プロセッサは簡単に数百サイクル停止する可能性があります。

メモリーへのアクセスは、順次アクセスする場合に最も効率的です。その場合、1 バイトがキャッシュで使用可能になる確率が最大になり、同じキャッシュ ラインに存在する可能性が非常に高くなります。これにより、配列要素に順番にインデックスを付けると仮定すると、配列が最も効率的なコレクション オブジェクトになります。

したがって、LinkedList を除くすべての .NET コレクション クラスは、配列を使用してデータを格納します。ハッシュされたコレクション (Hashtable、Dictionary、Hashset) を含め、それらは配列の配列を使用します。ArrayList を含みます。LinkedList は、キャッシュの局所性が非常に貧弱であるため、回避する必要があります。

配列の問題は、配列のサイズが固定されているため、ArrayList のような自動サイズ変更コレクションの実装が困難になることです。これは、意図的にアドレス空間を浪費することで解決されます。配列が容量いっぱいになると、配列が再割り当てされ、要素がコピーされます。再割り当ては以前のサイズの 2 倍です。これは、Capacity プロパティから確認できます。これはコストがかかるように思えますが、アルゴリズムは O(1) で償却され、オペレーティング システムの仮想メモリ サブシステムにより、使用しないメモリに対して実際に料金が発生しないことが保証されます。

事前に容量を推測することで、それほど安くないコピーを回避できます。詳細については、この回答を参照してください。

于 2012-06-30T15:45:59.210 に答える
2

Arraylistは、内部で配列を使用してデータを格納し、必要に応じて配列のサイズを変更します。

ArraylistのJava実装は、初期サイズの配列を内部的に作成し、配列のサイズを変更します。

ここで実装を見ることができます：http： //www.docjar.com/html/api/java/util/ArrayList.java.html

これはJava用ですが、概念は.NETでも同じです。

于 2012-06-30T14:57:54.603 に答える
1

MSDNページから：

必要に応じてサイズが動的に増加する配列を使用して、IListインターフェイスを実装します。

配列の代わりにクラスを直接使用する利点のいくつかは次のとおりです。

  • どこでも使用できますIList
  • 配列の中央からアイテムを追加/削除するときに、サイズ変更とコピーを処理します
  • 配列の「最後の」項目を追跡します
  • 配列内のアイテムをバイナリ検索するためのメソッドを提供します
于 2012-06-30T15:04:09.760 に答える
1

ここを参照してください: ArrayList ソース

すでに述べたように、それは下の配列です。

private object[] _items;

Add() メソッドは次のとおりです。

public virtual int Add(object value)
{
    if (this._size == this._items.Length)
    {
        this.EnsureCapacity(this._size + 1);
    }
    this._items[this._size] = value;
    ArrayList expr_2D = this;
    ArrayList arg_2E_0 = expr_2D;
    expr_2D._version = arg_2E_0._version + 1;
    ArrayList expr_3B = this;
    ArrayList arg_3C_0 = expr_3B;
    ArrayList arg_45_0 = expr_3B;
    int expr_41 = arg_3C_0._size;
    int arg_42_0 = expr_41;
    int arg_44_0 = expr_41;
    int i = arg_42_0;
    arg_45_0._size = arg_44_0 + 1;
    return i;
}

ご覧のとおり、EnsureCapacity が呼び出され、最終的に set_Capacity が呼び出されます。

public virtual void set_Capacity(int value)
{
    if (value < this._size)
    {
        throw new ArgumentOutOfRangeException("value", Environment.GetResourceString("ArgumentOutOfRange_SmallCapacity"));
    }
    if (value != this._items.Length)
    {
        if (value <= 0)
        {
            this._items = new object[4];
            goto IL_65;
        }
        object[] array = new object[value];
        if (this._size > 0)
        {
            Array.Copy(this._items, 0, array, 0, this._size);
        }
        this._items = array;
        return;
    }
    IL_65:
}

容量を増やす必要がある場合は、アレイ全体をより大きなアレイにコピーします。

于 2012-06-30T15:11:14.157 に答える
1

は、ArrayList値をオブジェクトの配列として内部的に格納し、いくつかのパブリック ヘルパー メソッドを公開して、配列を簡単に操作できるようにします (IListインターフェイスを介して公開されます)。

アイテムが挿入されると、挿入ポイントの右側にあるすべての要素が右に移動するため、挿入がかなり非効率になります。一方、追加は要素をシフトする必要がないため高速です (内部配列が容量に達しない限り、その場合はより大きな配列に置き換えられます)。

値は配列として内部的に保存されるため、配列の利点が得られます (値がソートされている場合の効率的な検索など)。

于 2012-06-30T15:10:07.373 に答える