TIM Labs

遅延評価とメモ化は別物(LINQ編)

| コメント(0) | トラックバック(0)

問題

以下のC#のコードに含まれる誤りを指摘しなさい:

Send()
{
    var xs = (
        GatherItems()
        .SelectMany(i => i.SubItems)
        .Select(i => i.MakeLocation())
    );

    SendLocations(xs);
}

SendLocations(IEnumerable<Location> ls)
{
    var now = DateTime.Now;

    foreach (var l in ls)
        l.UpdatedAt = now;

    foreach (var l in ls)
        l.Send();
}

解答

上記の SendLocations を実行過程が分かり易くなるよう書き換えると以下のようになります:

SendLocations(IEnumerable<Item> items)
{
    var now = DateTime.Now;

    foreach (var l in items
                      .SelectMany(i => i.SubItems)
                      .Select(i => i.MakeLocation()))
        l.UpdatedAt = now;

    foreach (var l in items
                      .SelectMany(i => i.SubItems)
                      .Select(i => i.MakeLocation()))
        l.Send();
}

このように書き換えると何が問題かは一目瞭然でしょう。 SendLocationsSelect の結果をあたかも普通の配列と同じように扱っているのですが、 実際には新しいデータを作っては捨て、作っては捨て、作っては捨て......ということを繰り返しているのです。 結果として l.UpdatedAt に対する更新が全て無駄になり、誤った結果が l.Send されていいます。

この場合、以下のように Select の結果を実体化し、その結果を使いまわす形に変更すれば、 期待通りに動くようになります:

SendLocations(IEnumerable<Location> ls)
{
    var now = DateTime.Now;
    var _ls = ls.ToArray();

    foreach (var l in _ls)
        l.UpdatedAt = now;

    foreach (var l in _ls)
        l.Send();
}

補足

Select 等の LINQ の大抵のメソッドは遅延評価です。 より正確には、 メソッドの戻り値(何らかのシーケンスが生成される)が列挙されるまで 実際の処理(Select ならば値の写像)は遅延されます。 逆に言えば、Select 等の戻り値は列挙される度に遅延されている処理が実行されるのです。

つまり、実際の処理が遅延されるだけであって、 結果としてできあがる値のシーケンスがメモ化されることはありません。 遅延評価とメモ化は直交する概念なのですが、 Scheme (R5RS) の delay 等のように 遅延評価とメモ化をセットで取り扱っているライブラリもあるため、 最初にこのようなライブラリに触れていると「遅延評価された結果はメモ化されるものだ」と勘違いされる場合があります (具体的に言うと筆者のことです)。

遅延評価とメモ化をセットで考えていると今回問題にしたようなコードを書いてしまいがちです。 注意しましょう。

また、解答では Select の結果を実体化するために ToArray を使っていますが、 本当に配列が欲しい訳ではなく、結果が実体化されていれば十分です。 なのに ToArray を使っていると一体何がしたいのかコードをぱっと見て判別できません。 ですので以下のような拡張メソッドを用意しておいた方が良いかも知れません:

public static IEnumerable<T> ToInstance(this IEnumerable<T> xs)
{
    return xs.ToArray();
}

トラックバック(0)

トラックバックURL: http://labs.timedia.co.jp/mt/mt-tb.cgi/264

コメントする

このブログ記事について

このページは、kanaが2011年10月15日 00:00に書いたブログ記事です。

ひとつ前のブログ記事は「Python で Android の指リストパターンを数え上げる」です。

次のブログ記事は「Python で Android の指リストパターンを数え上げる (その2)」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。