【C#】ListオブジェクトのCapacityの変化を観察する。

  • 2012.07.01 Sunday
  • 04:20
JUGEMテーマ:コンピュータ

「アルゴリズムを学ぼう」を参考にすると、Vectorは配列と違い要素を後ろから追加したり、削除したりできるものと紹介されています。実装的にはC++/STLのVectorまたはJavaのVectorを指しているっぽいですが、この文中のVectorはアルゴリズム用語なのだろうと思います。

とりあえずC#ではこの「Vector」の実装はおそらくList<T>が該当すると思うので挙動を調べてみてみました。

List<T>の実装は、内部的に配列をラップしています。配列は、要素数をコンストラクタ時に決定しなければならず、要素数を可変と扱えません。つまり、List<T>の内部的には、配列の要素を超える要素が追加された場合は、新たに配列を作成し、コピーしなければならないということになります。コピーは計算時間を長くしてしまうため、このコピーの回数をなるべく減らす事が、計算時間を短くすることができるツボということらしいです。

ということで、List<T>のインスタンスに要素を一つずつ追加してみて、
どのタイミングで配列の要素数が増えていくかどうか見てみました。

コードは下記の通り

static void Main()
{
    var list = new List<int>();
    int capacity = list.Capacity;
    Console.WriteLine("{0}:{1}", "new List<int>()", capacity);
    foreach (int i in Enumerable.Range(1, 10000))
    {
        list.Add(i);
        if (list.Capacity > capacity)
        {
            capacity = list.Capacity;
            Console.WriteLine("{0}:{1}", i, capacity);
        }
    }

    list.Clear();
    Console.WriteLine("{0}:{1}", "list.Clear()", list.Capacity);

}

実行結果は
------------------------------------

new List<int>():0
1:4
5:8
9:16
17:32
33:64
65:128
129:256
257:512
513:1024
1025:2048
2049:4096
4097:8192
8193:16384
list.Clear():16384

------------------------------------

newされたタイミングでは、
内部の配列が用意されていないのかどうか分かりませんが、
とにかく0ということが分かります。
要素が一つ追加されると、配列の要素数は4
要素数4が超えると、次は8
要素数超えるたびに、4,8,16,32,64,128,256・・・
と、要素数の2倍の数の新しい配列が容易さてていることが分かります。

List<T>では、要素数を超えた場合、2倍の要素数をもつ配列が新たに用意される

ということが確認できました。


List<T>では、要素数が大きくなると予想される場合は、Capacityを自分で指定することもできます。
下記のように

var list = new List<int>() { Capacity = 16384 };

としておけば、先ほどと異なる実行結果となります。

static void Main()
{
    var list = new List<int>() { Capacity = 16384 };
    int capacity = list.Capacity;
    Console.WriteLine("{0}:{1}", "new List<int>()", capacity);
    foreach (int i in Enumerable.Range(1, 10000))
    {
        list.Add(i);
        if (list.Capacity > capacity)
        {
            capacity = list.Capacity;
            Console.WriteLine("{0}:{1}", i, capacity);
        }
    }

    list.Clear();
    Console.WriteLine("{0}:{1}", "list.Clear()", list.Capacity);
}

実行結果
-------------------------------------
new List<int>():16384
list.Clear():16384

これで内部的にコピーが繰り返されることを、低減させたことになります。

これまでは「実行速度」という観点からの効率を考察しましたが、逆にメモリ空間的な効率を考えると
TrimExcessメソッドを利用すると、無駄に増えたCapacityを削除することができ、
不要なメモリ空間の軽減につながるかと思います。

static void Main()
{
    var list = new List<int>() { Capacity = 16384 };
    list.AddRange(Enumerable.Range(0, 10));
    Console.WriteLine(list.Capacity);
    list.TrimExcess();
    Console.WriteLine(list.Capacity);
}

実行結果
---------------------------------------
16384
10

あと、List<T>.AddメソッドとList<T>.AddRangeメソッドの実行速度なども
観察してみるとおもしろいかもしれません。

まあ兎にも角にも、本で紹介されている内容を、実際に実装されているライブラリーなどに対して
実験してみるのは楽しい作業です。面白いですよ。おすすめです。

コメント
管理者の承認待ちコメントです。
  • -
  • 2018/06/17 5:08 AM
コメントする








    
この記事のトラックバックURL
トラックバック

calendar

S M T W T F S
  12345
6789101112
13141516171819
20212223242526
2728293031  
<< January 2019 >>

あわせて読みたい

あわせて読みたいブログパーツ

selected entries

categories

archives

recent comment

  • 【キーボード】6年前のRealForceを復活させることはできる!?その3
    art55 (05/22)
  • 【キーボード】6年前のRealForceを復活させることはできる!?その3
    分解大好き (05/18)
  • 【.NET Framework 4.5】 IListがIReadOnlyListを継承してない理由。
    art55 (02/04)
  • 【.NET Framework 4.5】 IListがIReadOnlyListを継承してない理由。
    Gen (02/04)
  • 【キーボード】RealForce が壊れて帰ってきた。
    art55 (04/29)
  • 【.NET Framework 4.5】 IListがIReadOnlyListを継承してない理由。
    art55 (02/23)
  • 【.NET Framework 4.5】 IListがIReadOnlyListを継承してない理由。
    かるあ (02/22)
  • 【C#】Dictionaryの実装・データ構造・アルゴリズムを観察する。
    art55 (01/16)
  • 【C#】Dictionaryの実装・データ構造・アルゴリズムを観察する。
    karuakun (01/16)
  • 【NetOffice】【Excel】死なないExcelプロセスをKillする。
    art55 (12/05)

recent trackback

recommend

recommend

recommend

C#プログラマのための.NETアプリケーション最適化技法 (Programmer's SELECTION)
C#プログラマのための.NETアプリケーション最適化技法 (Programmer's SELECTION) (JUGEMレビュー »)
Sasha Goldshtein,Dima Zurbalev,Ido Flatow,サシャ・ゴルドシュタイン,ディマ・ズルバレフ,イド・フラトー

recommend

ろんりと集合
ろんりと集合 (JUGEMレビュー »)
中内 伸光
とてもわかりやすいです。

recommend

recommend

シャノン・ノイマン・ディジタル世界
シャノン・ノイマン・ディジタル世界 (JUGEMレビュー »)
市川 忠男
4章がリレーショナルデータベースな内容になってます。ページ数があまりありませんが、ポイントがものすごく的確にまとまっていて、感動します。

recommend

recommend

東プレ Realforce91UBK-S 静音キーボード 静電容量無接点方式 変荷重 ブラック NG01BS
東プレ Realforce91UBK-S 静音キーボード 静電容量無接点方式 変荷重 ブラック NG01BS (JUGEMレビュー »)

テンキーレス、静音のRealForce91UBK-S。スコスコ感がたまらなく気持ちいいです。家と会社で2台持ってます。

recommend

recommend

プログラミング.NET Framework 第4版 (プログラミングシリーズ)
プログラミング.NET Framework 第4版 (プログラミングシリーズ) (JUGEMレビュー »)
Jeffrey Richter
発売予定美 2013年10月10日。.NET Frameworkとお付き合いする人のバイブルですね。

recommend

recommend

キャット・シッターの君に。
キャット・シッターの君に。 (JUGEMレビュー »)
喜多嶋 隆
私のイラストレータデビュー本です。

recommend

Essential .NET ― 共通言語ランタイムの本質
Essential .NET ― 共通言語ランタイムの本質 (JUGEMレビュー »)
ドン・ボックス,クリス・セルズ,Don Box,Chris Sells,吉松 史彰

links

profile

search this site.

others

mobile

qrcode

powered

無料ブログ作成サービス JUGEM