LinkedListとArrayの速度が全く違う件

今回の内容は軽めです。

前回の多項式の因数分解プログラムのリファクタリング中に気づいたのですが、約数の一覧を配列で持たせるかLinkedListで持たせるかで実行速度が数倍違うような気がしました（どうも勘違いで、実際にはほとんど変わってなかったみたいです）。

実験

本当にLinkedListで持たせてるのが遅くなっている原因なのか調べるために、次のような簡単なC#のコードを書いて実験してみました。単に1からnまでの整数の和を求めるだけのコードです。

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

class Program
{
    static void Main()
    {
        int n = 10000000;	// テストするデータ数
        var sw = new Stopwatch();
        long res;

        Console.WriteLine("----- LinkedList");
        sw.Reset();
        sw.Start();
        var ll1 = new LinkedList<int>();
        for (int i = 0; i < n; ++i) {
            ll1.AddLast(i);
        }
        sw.Stop();
        Console.WriteLine("Generate: {0:e6}[ms]", sw.Elapsed.TotalMilliseconds);
        sw.Reset();
        sw.Start();
        res = 0;
        foreach (var x in ll1) {
            res += x;
        }
        sw.Stop();
        Console.WriteLine("Compute : {0:e6}[ms]", sw.Elapsed.TotalMilliseconds);

        Console.WriteLine();

        Console.WriteLine("----- Array");
        sw.Reset();
        sw.Start();
        var a1 = new int[n];
        for (int i = 0; i < n; ++i) {
            a1[i] = i;
        }
        sw.Stop();
        Console.WriteLine("Generate: {0:e6}[ms]", sw.Elapsed.TotalMilliseconds);
        sw.Reset();
        sw.Start();
        res = 0;
        foreach (var x in a1) {
            res += x;
        }
        sw.Stop();
        Console.WriteLine("Compute : {0:e6}[ms]", sw.Elapsed.TotalMilliseconds);

        Console.WriteLine();

        Console.WriteLine("----- LinkedList -> Array");
        sw.Reset();
        sw.Start();
        var ll2 = new LinkedList<int>();
        for (int i = 0; i < n; ++i) {
            ll2.AddLast(i);
        }
        sw.Stop();
        Console.WriteLine("Generate: {0:e6}[ms]", sw.Elapsed.TotalMilliseconds);
        sw.Reset();
        sw.Start();
        var a2 = ll2.ToArray();
        sw.Stop();
        Console.WriteLine("ToArray : {0:e6}[ms]", sw.Elapsed.TotalMilliseconds);
        sw.Reset();
        sw.Start();
        res = 0;
        foreach (var x in a2) {
            res += x;
        }
        sw.Stop();
        Console.WriteLine("Compute : {0:e6}[ms]", sw.Elapsed.TotalMilliseconds);
    }
}

手元のPCで実行した結果は下のとおりです。

----- LinkedList
Generate: 1.343535e+003[ms]
Compute : 8.357720e+001[ms]

----- Array
Generate: 2.087620e+001[ms]
Compute : 1.494910e+001[ms]

----- LinkedList -> Array
Generate: 1.392360e+003[ms]
ToArray : 5.870290e+001[ms]
Compute : 1.685090e+001[ms]

生成時間が2桁も違うのはアレですが、和の計算時間もおよそ5.6倍も開きがあります。

さらに驚きなのは、LinkedListのまま先頭から末尾まで走査して和を計算するより、一旦配列に変換してから先頭から末尾まで走査して和を計算するほうが、配列変換にかかる時間を考えても短いことですね。

理由

LinkedListは遅いと断定できたところで私は思い出したんですが、みなさんご存知の通り、線形リストの動作は一般に非常に遅いです。

これはコンピュータのしくみとも関係があるのですが、配列の場合はデータを記憶するために必要なデータ量が必要最小限で済んでしかもデータがメモリ上に連続的に配置されるのでデータが高速なキャッシュメモリに乗りやすく、そのお陰で動作も高速です。

一方線形リストの場合は、データを記憶するために必要なデータ量が多く（LinkedListの場合は双方向リストなので、64bit環境でint型のデータを格納する場合は、配列に比べておよそ5倍のデータ量が必要です）、データもメモリ上に連続的に配置されるとは限らないのでキャッシュミスが必然的に多くなり、動作が遅くなってしまうわけです。

となると、「なんでLinkedListそのままで全部の数の和を計算するよりもToArrayしてから全部の数の和を計算するほうが速いのか。LinkedListのままで和を計算するのもToArrayするのもどうせデータの先頭から末尾まで操作するんだから時間は後者のほうが長くなるはずなのに」という疑問が湧いてくるわけですが、さっきのテストプログラムを逆アセンブル（ILのコードを人間が読みやすいように変換）して実行可能ファイルを見てみると、どうやらToArrayはCLRの内部関数に投げちゃってるらしいです。

CLRの内部関数なんだから恐らく僕達が適当に書くより速く動作するんでしょう。知らないけど。

ということで（アセンブラあまり読めないし）こういうことで適当に納得することにしました。

結論

ここまで書くと、なんで線形リストなんか存在するんだっていう感じですが、ちゃんと存在理由はあります。

線形リストの最大の利点は、「要素の追加・削除・挿入がとても簡単にできる」ということです。配列の場合はサイズ変更が必要になったときにデータの移動が必要ですが、線形リストはそんなの全く必要ないですからね。

また、LinkedListは単なる双方向線形リストですが、線形リストクラスを自分で作るなどすれば、ノードのつなぎかたによっては循環リストだとかそういうのも作ることができて応用範囲が非常に広いです。

ということでLinkedListと配列の使いどころのまとめ。

LinkedList

• いくつ入るかわからないデータの格納に使う
• データの追加・挿入・削除が簡単
• LinkedListに持たせたデータの処理は、ToArrayでLinkedListを配列に変換してからやるほうが速そう。何回もそのデータを使うような場面なら効果絶大
• 参照型とかintみたいな単純な値型ならToArrayする方が速いけど、フィールドがたくさんある複雑な値型ならToArrayが遅そうな気がする（だからLinkedListのままデータ処理する方がよさそう）

そもそも大量のデータ持ってるときにさらにToArrayしたら使うメモリががが

配列

• 最初からいくつ入るかわかってるデータの格納に使うといい
• データの参照とかが高速
• 使うメモリが必要最小限

というかパフォーマンス気にしなきゃいけないような段階にきたらまずは使うアルゴリズム変えるのを検討しろよって僕は思うので、普段のコーディングではLinkedListでも配列でも使いやすい方を使いましょう。

以上、おしまい。