.NETのコレクション概要とImmutable Collectionsについて

2013-10-31

先週の土曜日に、「プログラミング .NET Framework 第4版」座談会でOverview of the .NET Collection Framework and Immutable Collectionsとして、コレクションフレームワークとImmutable Collectionsについて話してきました。

Overview of the .Net Collection Framework and Immutable Collections from Yoshifumi Kawai

案外コレクションについてまとまった話って、ない(or .NET 4.5からReadOnly系が入ってきて、話が更新されているもの)ので、資料として役に立つのではないかと思います。

Collection Framework

前半部分ですが、これのジューヨーなところはILinqable<T>、じゃなくて(スライド資料では出てないのでナンノコッチャですが)、ReadOnly系の取り扱いですね。MutableとReadOnlyが枝分かれしている理由とか対処方法とか、が伝えたかった点です。いやあ、コレクション作る時は両方実装しよう！とかしょうもないですねえ、shoganaiのですねぇ……。

IEnumerable<T>とIReadOnlyCollection<T>の差異は実体化されていない「可能性がある」かどうか。で、なのでメソッドの引数などで内部で実体化されてるのを前提にほげもげしたい場合は、IReadOnlyCollection<T>を受け取るほうが望ましいといえば望ましいのですが、汎用的にIEnumerableのままで……という場合は、以下のようなメソッドを用意しとくといいでしょう。

/// <summary>
/// sourceが遅延状態の場合、実体化して返し、既に実体化されている場合は何もせずそれ自身を返します。
/// </summary>
/// <param name="source">対象のシーケンス。</param>
/// <param name="nullToEmpty">trueの場合、sourceがnull時は空シーケンスを返します。falseの場合はArgumentNullExceptionを吐きます。</param>
public static IEnumerable<T> Materialize<T>(this IEnumerable<T> source, bool nullToEmpty = true)
{
    if (nullToEmpty && source == null)
    {
        return Enumerable.Empty<T>();
    }
    else
    {
        if (source == null) throw new ArgumentNullException("sourceがnullです");
    }

    if (source is ICollection<T>)
    {
        return source;
    }
    if (source is IReadOnlyCollection<T>)
    {
        return source;
    }

    return source.ToArray();
}

こんなのを作って、冒頭で呼べば、二度読みなどもOKに。

public static void Hoge<T>(IEnumerable<T> source)
{
    source = source.Materialize(); // ここで実体化する

    // あとは好きに書けばいいのではないでせうか
}

どうでしょ。また、二度読みなら列挙したらキャッシュして、再度読む時はそっから読んでくれればいいのに！というリクエストあるかと思います。それは一般的にはメモ化(Memoization)といいます。というわけで、シーケンスに実装してみましょう。

public static IEnumerable<T> Memoize<T>(this IEnumerable<T> source)
{
    if (source == null) throw new ArgumentNullException("sourceがnull");
    return new MemoizedEnumerable<T>(source);
}

class MemoizedEnumerable<T> : IEnumerable<T>, IDisposable
{
    readonly IEnumerable<T> source;
    readonly List<T> cache = new List<T>();
    bool cacheComplete = false;
    IEnumerator<T> enumerator;

    public MemoizedEnumerable(IEnumerable<T> source)
    {
        this.source = source;
    }

    public IEnumerator<T> GetEnumerator()
    {
        if (enumerator == null) enumerator = source.GetEnumerator();
        return new Enumerator(this);
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    public void Dispose()
    {
        if (enumerator != null) enumerator.Dispose();
    }

    class Enumerator : IEnumerator<T>
    {
        readonly MemoizedEnumerable<T> enumerable;
        int index = 0;

        public Enumerator(MemoizedEnumerable<T> enumerable)
        {
            this.enumerable = enumerable;
        }

        public T Current { get; private set; }

        public void Dispose()
        {

        }

        object System.Collections.IEnumerator.Current
        {
            get { return Current; }
        }

        public bool MoveNext()
        {
            if (index < enumerable.cache.Count)
            {
                Current = enumerable.cache[index];
                index++;
                return true;
            }

            if (enumerable.cacheComplete) return false;

            if (enumerable.enumerator.MoveNext())
            {
                Current = enumerable.enumerator.Current;
                enumerable.cache.Add(Current);
                index++;
                return true;
            }

            enumerable.cacheComplete = true;
            enumerable.enumerator.Dispose();
            return false;
        }

        public void Reset()
        {
            throw new NotSupportedException("Resetは産廃");
        }
    }
}

こうしておけば、

// hoge:xが出力されるのは1回だけ
var seq = Enumerable.Range(1, 5)
    .Select(x =>
    {
        Console.WriteLine("hoge:" + x);
        return x;
    })
    .Memoize();

// なんど
foreach (var item in seq.Zip(seq, (x, y) => new { x, y }).Take(4))
{
    Console.WriteLine(item);
}

// ぐるぐるしても一度だけ
foreach (var item in seq.Zip(seq, (x, y) => new { x, y }))
{
    Console.WriteLine(item);
}

といった感じ。Materializeより合理的といえば合理的だし、そうでないといえばそうでない感じです。私はMaterializeのほうが好み。というのもMemoizeは完了していないEnumeratorを保持しなければいけない関係上、Disposeの扱いがビミョーなんですよ、そこが結構引っかかるので。

あと、IEnumerable<T>ですが、スレッドセーフではない。そう、IEnumerable<T>にはスレッドセーフの保証は実はない。というのを逆手に取ってる（まぁ、それはあんまりなので気になる人はlockかけたりしましょう）。ちなみにReadOnlyCollectionだってラップ元のシーケンスが変更されたらスレッドセーフじゃない。そして、スレッドセーフ性が完璧に保証されているのがImmutable Collections。という話につながったりつながらなかったり。

Immutable Collections

Immutable Collectionsは実装状況が.NET Framework Blogで随時触れられていて、リリース時のImmutable collections ready for prime timeを読めば、なんなのかっては分かるのではかと。その上で私が今回で割と酸っぱく言いたかったのは、ReadOnly「ではない」ってことです。そして結論はアリキタリに使い分けよう、という話でした。

セッション後の話とかTwitterで、バージョニングされたコレクションって捉えるといいんじゃないの？と意見頂いたのですが、なるほどしっくりきそうです。

スピーカー予定

今後ですが、大阪です！12/14、第3回 LINQ勉強会で発表する予定なので、関西圏の人は是非是非どうぞ。セッションタイトルは「An Internal of LINQ to Objects」を予定しています。これを聞けばLINQ to ObjectsのDeep Diveの部分は全部OK、といった内容にするつもりです。もう初心者向けってこともないので、完全に上級者がターゲットで。

.NETのコレクション概要とImmutable Collectionsについて

Collection Framework

Immutable Collections

スピーカー予定

Profile

Archive