すらすらプログラマーへのお問い合わせ
すらすらのブログ
アクセス数  累計:000,610,477  昨日:000,000,153  本日:000,000,007
Loading
やってみよう!
.NET プログラミング
プロパティグリッド
印刷
リストボックス
スレッド
リストビュー
インストーラー
やってみよう!

できるVisual Studio 2015 Windows /Android/iOS アプリ対応

独習C# 第3版

VisualBasic2013パーフェクトマスター (Perfect Master SERIES)

プログラミング.NET Framework 第4版 (Microsoft Press)

VisualBasic2013逆引き大全555の極意

猫でもわかるWindowsプログラミング 第4版 (猫でもわかるプログラミング)

VisualC#2013逆引き大全555の極意

リストは配列? 最終更新:2010/07/15
【Amazon ランキング:DVD - 海外映画】

私は List と聞くとリスト構造を想像してしまうのですが、.NET で使われる Listクラスはどうやら名前だけで内部構造は配列ではないかという疑惑が湧いてきました。
その疑惑を思い起こさせたのは List のヘルプにある Capacity プロパティの次の1文を社内の人間に指摘されたからであります。

「Capacity は、常に Count 以上です。要素を追加しているときに Count が Capacity を超えた場合は、古い要素をコピーして新しい要素を追加する前に、内部配列を自動的に再割り当てすることによって、リストの容量が増加します。」

この文章の中に「内部配列を自動的に再割り当て」とあるように、内部は配列ではないかと?
そこで、List クラスは本当に配列なのかを検証してみることにしました。
検証方法
配列かリストかを検証するには、Listクラスの前後に値を追加すれば検証できます。
リスト構造の場合 リスト構造の場合、オブジェクトを追加してもポインタを付け替えるだけなのでリストの前後どちらに追加しても速度は変わらない。
配列の場合 配列の場合、リストの後ろへの追加は高速だが、リストの先頭に追加する場合は配列全体をずらさないといけないので遅くなる。
検証プログラム作成
List クラスの構造を解析するために以下のようなプログラムを作成しました。
C#[ListForm.cs]
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace list
{
    
public partial class ListForm : Form
    {
        
public ListForm()
        {
            InitializeComponent();
        }

        
private const int LOOP_CNT = 5000;

        
/// <summary>
        /// リストに Add
        /// </summary>
        private void button1_Click(object sender, EventArgs e)
        {
            
DateTime t = DateTime.Now;

            
for (int i = 0; i < LOOP_CNT; i++)
            {
                
List<int> list = new List<int>(LOOP_CNT);
                
for (int j = 0; j < LOOP_CNT; j++)
                {
                    list.Add(j);
                }
            }

            
TimeSpan span = DateTime.Now - t;

            
Console.WriteLine(string.Format(
                
"List.Add time {0}.{1:000}", span.Seconds, span.Milliseconds));
        }

        
/// <summary>
        /// リストの先頭に Insert
        /// </summary>
        private void button2_Click(object sender, EventArgs e)
        {
            
DateTime t = DateTime.Now;

            
for (int i = 0; i < LOOP_CNT; i++)
            {
                
List<int> list = new List<int>(LOOP_CNT);
                
for (int j = 0; j < LOOP_CNT; j++)
                {
                    list.Insert(0, j);
                }
            }

            
TimeSpan span = DateTime.Now - t;

            
Console.WriteLine(string.Format(
                
"List.Insert1 time {0}.{1:000}", span.Seconds, span.Milliseconds));
        }

        
/// <summary>
        /// リストの最後に Insert
        /// </summary>
        private void button3_Click(object sender, EventArgs e)
        {
            
DateTime t = DateTime.Now;

            
for (int i = 0; i < LOOP_CNT; i++)
            {
                
List<int> list = new List<int>(LOOP_CNT);
                
for (int j = 0; j < LOOP_CNT; j++)
                {
                    list.Insert(j, j);
                }
            }

            
TimeSpan span = DateTime.Now - t;

            
Console.WriteLine(string.Format(
                
"List.Insert2 time {0}.{1:000}", span.Seconds, span.Milliseconds));
        }
    }
}
検証結果
検証プログラムをそれぞれ5回実行して平均をとりました。
1回目 2回目 3回目 4回目 5回目 平均
Add で最後に追加 0.221 秒 0.220 秒 0.219 秒 0.218 秒 0.226 秒 0.220 秒
Insert で先頭に追加 14.580 秒 14.626 秒 14.618 秒 14.611 秒 13.565 秒 14.400 秒
Insert で最後に追加 0.254 秒 0.253 秒 0.254 秒 0.254 秒 0.254 秒 0.253 秒
上記の計測結果から、List の先頭への追加は後ろに追加するよりも時間がかかることから List クラスの内部構造は配列だ言うことが分かります。
おまけ
List クラスの内部構造が配列だと分かったので、もうひとつ List クラス作成時に Capacity を指定した場合とそうでない場合の速度を比較してみました。

上記のサンプルコードの List クラスを New している部分を

                List<int> list = new List<int>();     ← Capacity の指定をしない
と変更してもう一度検証してみました。
1回目 2回目 3回目 4回目 5回目 平均
Add で最後に追加 0.233 秒 0.232 秒 0.231 秒 0.231 秒 0.232 秒 0.231 秒
Insert で先頭に追加 13.105 秒 13.014 秒 12.920 秒 12.998 秒 12.982 秒 13.003 秒
Insert で最後に追加 0.264 秒 0.261 秒 0.261 秒 0.267 秒 0.261 秒 0.262 秒
Capacity 指定のありとなしの比較です。
Capacty 指定あり Capacty 指定なし 時間差
Add で最後に追加 0.220 秒 0.231 秒 +0.011 秒
Insert で先頭に追加 14.400 秒 13.003 秒 -1.397 秒
Insert で最後に追加 0.253 秒 0.262 秒 +0.009 秒
計測する前は、Capacty なしでは処理時間は全てにおいて処理が遅くなると思っていたのですが、上記の表を見ると Insert で先頭に追加する場合は逆に速くなっています。おそらく Capacty を指定しない場合は、指定した場合よりもシフトする要素数が少なくてすむため若干速く高速になったものと推測されます。実際にこうして計測してい見ると面白発見があるものです。
※このページで紹介しているサンプルコードについて管理者は動作保障をいたしません※
※サンプルコードを使用する場合は、自己責任でお願いします※

【楽天 ランキング:パソコン・周辺機器 - ネットワーク機器】




このサイトはフリーソフトのMerge HTMLで作成されています。
このサイトはリンクフリーです。

ページの先頭に戻る Copyright© 2010-2015 Jun.Shiozaki All rights reserved.