読者です 読者をやめる 読者になる 読者になる

IEnumerator 色々

.NET Python

.NET の IEnumerator の欠点

C#の似たようなものとして、IEnumeratorというのがありますが、それの方式は、

  • MoveNextで次の要素に移動
  • 移動できたら真、移動できなかったら偽を返す
  • Currentで現在の要素を取得する

というインターフェイスです。

これだと上のような問題は起きません。

欠点としては、要素をCurrentメソッドで取得できるよう、現在の要素を保持していないといけない、ということでしょうか。

そして、Javaの方式でもC#の方式でも同様に当てはまる欠点として、「一回の反復につき、2回以上のメソッド呼び出しが必要となってしまう」という問題があります。

確かに.
C# (あるいは BCL) 設計当時は値型の boxing を排除することで頭がいっぱいで,そっちまで考慮されてなかったんですかねぇ.来週来日される中の人(id:NyaRuRu:20070802:p1) に直接聞いたら,その辺の真実が明らかになるかも?
で確かに,今の C# で IEnumerator を作るなら,これでいいよなぁと.今のところやばげなシナリオは思いつかず.T が値型のときのコピーを回避できるメリットもありますし.

public interface IEnumeratorEx<T> : IDisposable
{
    bool TryGetNext(out T value);
    // void Dispose() Inherited from IDisposable
}

って out をサポートしない言語もあったっけ?

遅延リストの Reset

ところで,遅延リストの Reset って需要あるんですかねぇ?
.NET の場合は,どう考えても Reset が実装不能なケースに IEnumerator が使われまくった結果,Reset を呼ぶときにはかなりの高確率で例外を覚悟すべしという状況です.こんな状況で Reset に依存したコードを書く人なんて居るわけもなく*1.とまあ IEnumerator.Reset は,少なくとも .NET の世界では,「死に設定」なのですが.

配列に対する foreach の最適化

C# の foreach ですが,相手が配列の場合は実はちょっと特殊.

foreach(var item in seq)
{
   ......
}

コンパイル時に seq が1次元配列であると分かっているとき,Microsoft の C# コンパイラは,配列に対する for ループに置き換えた CIL を出力します.
JIT コンパイラじゃなくて C# コンパイラが,というのがミソ.1 次元配列は中間言語に専用命令があるので,現状の CLR ではこのコンパイル時最適化によって速度が激しく変わります.

for(int i = 0; i < seq.Length; ++i)
{
   ......
}

ちなみに,この置き換えを可能とするために,配列の列挙子は未来永劫 IDisposable を実装できません.

内部イテレータと外部イテレータ

System.Collections.Generic.List<T> のように,コレクションクラスの内部で配列を使ってオブジェクトを保持する場面を考えます.
下のコードをご覧ください.デリゲートを受け取ってコレクションの内部でループを行うか (ForEach メソッド),IEnumerator<T> を通してメソッド外部でループを行うかの 2 通りがあるわけですが,どちらが速いかという話です.

public partial class MyCollection<T> : IEnumerable<T>
{
    private T[] _internalArray;
    private int _length;
    public void ForEach(Action<T> action)
    {
        for (int i = 0; i < _length; ++i)
        {
            action(_internalArray[i]);
        }
    }
    public IEnumerator<T> GetEnumerator()
    {
        for (int i = 0; i < _length; ++i)
        {
            yield return _internalArray[i];
        }
    }
    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

現行の CLR 実装では,ループ内で行われる処理のコストが小さくなると,配列ループ方式で稼いだ速度で勝負が決まることが知られていて,マイクロベンチマークの結果は大抵 ForEach メソッドの圧勝に終わります.ベンチマーク結果はこの辺.

個人的おすすめとしては,サイズの大きな値型を想定して,ref 渡し版を追加するのも良いかなと.

public delegate void ByRefAction<T>(ref T item);
public partial class MyCollection<T>
{
    public void ForEach(ByRefAction<T> action)
    {
        for (int i = 0; i < _length; ++i)
        {
            action(ref _internalArray[i]);
        }
    }
}

IEnumerator<T> と IDisposable

たまたま見つけたのですが,「C# で作る Prolog 処理系: 外部イテレータと try-finally とカットの実装」がおもしろかったです.このイテレータ宙ぶらりん問題,Python 2.5 2.4 以前にもあったんですね.

*1:COM の IEnumHogehoge にマップしたいときは書くかも.