ToArray vs ToList

2011-08-03

LINQの結果は遅延評価なので、その場で全部評価して欲しかったりする場合などに使うToArrayとToList。どちらを使っていますか？私はToArrayのほうが好みです。と、いうのも、LINQで書く以上、長さは決まったようなものなので、これ以上AddやRemoveしたいことなんてほとんどない。勿論、必ずないとは言いませんので、その場合だけToListを使いますが、そうでない場合は、長さが固定だという意図を示すためにもToArrayが好ましい。

パフォーマンス

T[]やList<T>に変換されたあとだと、T[]のほうが、大体においてパフォーマンスは良い。という点でもToArrayがいいかなあ、と思うわけですが、それはさておき、ではToArrayとToListメソッドそれ自体のパフォーマンスはどちらのほうが良いでしょうか？理屈の上ではToListのほうが上です。というのも、変換処理は下記の図のようになっているからです。

元ソースがIEnumerable<T>である以上、長さは分からないので、ToArrayでも動的配列としていっぱいになったら二倍に拡大する、という動作を行うのはToListと変わりありません。この辺の話は動的配列への追加コストはなぜ O(1)?や、２倍だけじゃないを参考に。.NETは2倍です。そして、最後に拡大された配列の長さを整えるためコピーするのがToArray、そのまま渡すのがToList。つまり、ToArrayのほうが最後の一回のコピー動作が増えているわけです。

でも、ベンチマークをとると、ToArrayのほうが速かったりします。

// 適当さ溢れている（若干恣意的な）測り方なので、それはそれとしてくだしあ
// ToArray:00:00:01.5002685
// ToList :00:00:01.8124284
var source = Enumerable.Range(1, 100000000);

var sw = Stopwatch.StartNew();
source.ToArray();
Console.WriteLine("ToArray:" + sw.Elapsed);
GC.Collect();
sw.Restart();
source.ToList();
Console.WriteLine("ToList:" + sw.Elapsed);

へー、ToArrayのほうが速いんだー、ではなくて、要素数1億件でこの程度しかでないので、どうでもいい程度の差でしかないということです。ここ注意。こういう適当なマイクロベンチのマイクロな差で、こっちのほうが速いからこうしなければならない、これが最適化のための10箇条、みたいなことをやるのは間抜けだと思います。JavaScriptにはそういう記事があまりにも多すぎるとも思っています。

それはともかく、何で理屈の上ではコピーが多いToArrayのほうが"速い"のか。それは中身をゴニョゴニョしてみてみれば分かりますが

public static List<T> ToList<T>(this IEnumerable<T> source)
{
    // ICollection<T>の場合はnew List<T>(source)の中で最適化されてます
    // 最適化されない場合はforach(var item in source) this.Add(item) という感じ
    return new List<T>(source)
}

// 実際のコードとは違います、あくまでイメージです
public static T[] ToArray<T>(this IEnumerable<T> source)
{
    // ICollection<T>の場合はCopyToで最適化
    var collection = source as ICollection<T>;
    if (collection!= null)
    {
        var dest = new T[collection.Count];
        collection.CopyTo(dest, 0);
        return dest;
    }

    // そうでないなら列挙して配列を伸ばしながら作る
    var array = new T[4];
    var count = 0;
    foreach (var item in source)
    {
        if (array.Length == count)
        {
            var dest = new T[count * 2];
            Array.Copy(array, dest, count);
            array = dest;
        }
        array[count++] = item;
    }

    // 生成したものと長さが同じならそのまま返す
    if (array.Length == count) return array;

    // そうでないなら長さを整えてから返す
    var result = new T[count];
    Array.Copy(array, result, count);
    return result;
}

これだけだとよくわからない？うーん、そうですね。ToArrayの場合は配列を作る、それだけに最適化されていて余計なコードが一切ありません。反面、ToList、というかnew List<T>(source)は、内部では少し色々なものの呼び出し回数が多かったりしています。その辺のことが、コピー回数以上に「ほんの少しだけ」速度の差を生んでいるのではないかな、ということのようです。

// パフォーマンスを一切考えないのならこれでいいのよね
public static T[] ToArray<T>(this IEnumerable<T> source)
{
    // 実際はreturn new Buffer<T>(source).ToArray();
    return new List<T>(source).ToArray();
}

理屈的にはこれでいいわけですが、実際はBuffer<T>クラスというものをinternalでもっていて、それはLINQで使うためだけに余計なものが一切ない動的配列で、LINQ to Objectsの各メソッドは、動的配列が必要な場合ではList<T>ではなく、そのBuffer<T>クラスを使っています。DRYはどうした、という気は少しだけしますが、まあ、ユーザーとしては速いに越したことはないです。

Array.Copy

ところで、Array.CopyやICollection<T>のCopyToって面倒くさいですよね、長さを持った空の配列を作って、渡さなければならないって。と、Array Copy - Memo+の記事を見て改めて思いましたが、しかし、一番よくあるケースである一次元配列のコピーならToArrayを使えばOKです。↑の実装イメージであるように、ちゃんとis asで判定して最適化してくれているので、LINQだとforeachで全部舐めるから遅いんじゃないかなー、と考えなくても大丈夫。

まとめ

今日、Twitterで間違ったこと投稿しちゃって恥ずかすぃかったので反省して書いた。まる。とりあえずToArray使えばいいです。

ToArray vs ToList

パフォーマンス

Array.Copy

まとめ

Profile

Archive