|
アクセス数 累計：000,102,932 昨日：000,000,133 本日：000,000,181
|
|
|
|
|
|
|
【Amazon ランキング：本 - 資格・検定・就職】
|
私は List と聞くとリスト構造を想像してしまうのですが、.NET で使われる Listクラスはどうやら名前だけで内部構造は配列ではないかという疑惑が湧いてきました。
その疑惑を思い起こさせたのは List のヘルプにある Capacity プロパティの次の１文を社内の人間に指摘されたからであります。
「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));
}
}
}
|
|
|
| 検証結果 |
検証プログラムをそれぞれ５回実行して平均をとりました。
|
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. |
|
|
|
|
