連載:[完全版]究極の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バイト程度のメモリを消費していた。


 INDEX
  [完全版]究極のC#プログラミング
  Chapter2 ジェネリック
    1.2.1 ジェネリックとは何か?
    2.2.2 新しいコレクションの紹介
  3.2.3 新しいコレクションクラス―LinkedListクラス
    4.2.4 新しいコレクションクラス―SortedDictionaryクラス
    5.2.5 ジェネリックコレクションの使い方
    6.2.6 ジェネリックメソッドと型推論
    7.2.7 HashtableクラスとDictionaryクラスの非互換性
    8.2.8 ジェネリックなクラスを自作する
    9.2.9 制約の付いたジェネリックなクラス/C++のtemplate機能との相違/練習問題
 
インデックス・ページヘ  「[完全版]究極のC#プログラミング」

@IT Special

- PR -

TechTargetジャパン

Insider.NET フォーラム 新着記事
  • 第2回 簡潔なコーディングのために (2017/7/26)
     ラムダ式で記述できるメンバの増加、throw式、out変数、タプルなど、C# 7には以前よりもコードを簡潔に記述できるような機能が導入されている
  • 第1回 Visual Studio Codeデバッグの基礎知識 (2017/7/21)
     Node.jsプログラムをデバッグしながら、Visual Studio Codeに統合されているデバッグ機能の基本の「キ」をマスターしよう
  • 第1回 明瞭なコーディングのために (2017/7/19)
     C# 7で追加された新機能の中から、「数値リテラル構文の改善」と「ローカル関数」を紹介する。これらは分かりやすいコードを記述するのに使える
  • Presentation Translator (2017/7/18)
     Presentation TranslatorはPowerPoint用のアドイン。プレゼンテーション時の字幕の付加や、多言語での質疑応答、スライドの翻訳を行える
@ITメールマガジン 新着情報やスタッフのコラムがメールで届きます(無料)
- PR -

イベントカレンダー

PickUpイベント

- PR -

アクセスランキング

もっと見る

ホワイトペーパーTechTargetジャパン

注目のテーマ

Insider.NET 記事ランキング

本日 月間
ソリューションFLASH