| |
|
連載：［完全版］究極のC#プログラミング
Chapter2 ジェネリック
川俣 晶
2009/08/17 |
 |
|
2.3 新しいコレクションクラス―LinkedListクラス
LinkedListクラスは、1次元のリストを扱うという意味ではArrayList/Listクラスに似た機能を持っているが、異なる性質を持っている。
主な相違点は2つある。1つは、インデックスによるアクセスができないこと。つまり、添え字を付けて2番目、3番目といった番号指定で要素にアクセスできないのである。リストの途中の要素が必要となる場合は、先頭あるいは末尾から順にたどっていかなければならない。なぜそのような回りくどい機能制限を設けているのかといえば、その代わりに中間の要素に対する挿入/削除が素早くできるようにするためである。
実は、このような仕様はリーズナブルなものである。なぜなら、サイズ不定のコレクションに番号でアクセスすることはあまり多くはなく、あったとしても0から順にすべてにアクセスしているだけで、番号そのものには意味がないことが多いためだ。単に、順番にアクセスするだけなら、番号を使わない方法でもよい。つまり、最初や最後の要素を得る手段と、次ないし手前の要素を得る手段さえあれば、番号でアクセスできずともさほど困らないのである。
逆に、リストの中間に要素を挿入/削除する性能が意味を持つことは多い。加えて、それが高速に処理できれば、メリットになることも多いだろう。
ここでは実際に、ListクラスとLinkedListクラスの挿入性能の差を見てみよう。次のリスト2.3は、2つの要素を持つリストの中間に、1万個の要素を挿入する作業を100回繰り返すサンプルコードである。ListクラスとLinkedListクラスについて、それぞれ同じ回数の処理を行っている。
using System;
using System.Collections.Generic;
class Program
{
static void Main(string[] args)
{
// Listクラスの利用
DateTime start1 = DateTime.Now;
for (int i = 0; i < 100; i++)
{
List<string> list1 = new List<string>();
list1.Add("First");
list1.Add("Last");
for (int j = 0; j < 10000; j++)
{
list1.Insert(1, "Inserted");
}
}
DateTime end1 = DateTime.Now;
Console.WriteLine(end1 - start1);
// LinkedListクラスの利用
DateTime start2 = DateTime.Now;
for (int i = 0; i < 100; i++)
{
LinkedList<string> list2 = new LinkedList<string>();
list2.AddFirst("First");
list2.AddLast("Last");
for (int j = 0; j < 10000; j++)
{
list2.AddAfter(list2.First, "Inserted");
}
}
DateTime end2 = DateTime.Now;
Console.WriteLine(end2 - start2);
}
}
|
|
| リスト2.3 ListとLinkedListの挿入性能の差 |
00:00:05.3480694 （Listクラス利用時）
00:00:00.0820164 （LinkedListクラス利用時）
|
|
| リスト2.3の実行結果 |
| 実行結果は、Pentium D 3.2GHzのマシンでのデバッグビルドによるもの。 |
結果は見てのとおり、桁違いの性能差が出ている。
ちなみに、LinkedListクラスを使うと、データの入れ物となるLinkedListNodeクラスの存在も意識しなければならず、コーディングがやや煩雑になる。しかし、LinkedListNodeクラスのインスタンスは、リストに含めたり除外したりすることが容易であり、その特徴をうまく活用するとリストをばらして再構築するような処理の効率が上がる。ArrayList/Listクラスを使って思うような性能が出ない場合は、LinkedListクラスを試してみるとよいだろう。
ただし、メモリの使用量（確保されるオブジェクトの数）はLinkedListクラスのほうが大きくなるというデメリットもある。上記のプログラムの前半と後半を別々に実行させると、プログラム終了時点でListクラスのほうは約6Mバイト程度のメモリを消費しているのに対して、LinkedListクラスはより多い約11Mバイト程度のメモリを消費していた。
Insider.NET 記事ランキング
本日
月間
