10

基本的なSchemeインタープリターをC#で実装する際に、恐ろしいことに、次の問題を発見しました。

IEnumeratorにはcloneメソッドがありません!(より正確には、IEnumerableは「クローン可能な」列挙子を提供できません)。

私が欲しいもの:

interface IEnumerator<T>
{
    bool MoveNext();
    T Current { get; }
    void Reset();
    // NEW!
    IEnumerator<T> Clone();
}

効率的にクローン化可能なIEnumerator(ベクトル、リンクリストなど)を提供できないIEnumerableの実装を思い付くことができません。すべて、上記で指定したIEnumeratorのClone()の簡単な実装を提供できます...とにかくReset()メソッドを提供するよりも簡単です!)。

Cloneメソッドがないということは、シーケンスを列挙するという機能的/再帰的なイディオムが機能しないことを意味します。

また、IEnumerableをLispの「リスト」(car / cdrを使用して再帰的に列挙する)のように「シームレスに」動作させることができないことも意味します。つまり、「(cdr some IEnumerable)」の唯一の実装はひどく非効率的です。

効率的な「Clone()」メソッドを提供できないIEnumerableオブジェクトの現実的で便利な例を誰かが提案できますか?「yield」構造に問題があるということですか?

誰かが回避策を提案できますか?

4

8 に答える 8

23

ロジックは容赦ないです!IEnumerableは をサポートしておらずClone、 が必要なCloneので、使用しないでくださいIEnumerable

もっと正確に言えば、Scheme インタープリターで作業するための基本的な基礎としてそれを使用するべきではありません。代わりに、単純な不変のリンク リストを作成してみませんか?

public class Link<TValue>
{
    private readonly TValue value;
    private readonly Link<TValue> next;

    public Link(TValue value, Link<TValue> next)
    {
        this.value = value;
        this.next = next;
    } 

    public TValue Value 
    { 
        get { return value; }
    }

    public Link<TValue> Next 
    {
        get { return next; }
    }

    public IEnumerable<TValue> ToEnumerable()
    {
        for (Link<TValue> v = this; v != null; v = v.next)
            yield return v.value;
    }
}

このToEnumerableメソッドは、標準の C# の方法で便利に使用できることに注意してください。

あなたの質問に答えるには:

効率的な「Clone()」メソッドを提供できないIEnumerableオブジェクトの現実的で有用な例を誰かが提案できますか? 「利回り」構造に問題があるということですか?

IEnumerable は、そのデータのために世界中のどこにでも行くことができます。コンソールから行を読み取る例を次に示します。

IEnumerable<string> GetConsoleLines()
{
    for (; ;)
        yield return Console.ReadLine();
}

これには 2 つの問題があります。第 1 に、Clone関数を書くのは特に簡単ではありません (そしてReset意味がありません)。第二に、シーケンスは無限です - これは完全に許容されます。シーケンスは怠惰です。

もう一つの例:

IEnumerable<int> GetIntegers()
{
    for (int n = 0; ; n++)
        yield return n;
}

これらの両方の例で、受け入れた「回避策」は、使用可能なメモリを使い果たすか、永遠にハングアップするだけなので、あまり役に立ちません。しかし、これらはシーケンスの完全に有効な例です。

C# と F# のシーケンスを理解するには、Scheme のリストではなく、Haskell のリストを見る必要があります。

無限のものはニシンだと思う場合は、ソケットからバイトを読み取るのはどうですか:

IEnumerable<byte> GetSocketBytes(Socket s)
{
    byte[] buffer = new bytes[100];
    for (;;)
    {
        int r = s.Receive(buffer);
        if (r == 0)
            yield break;

        for (int n = 0; n < r; n++)
            yield return buffer[n];       
    }
}

ソケットに送信されるバイト数がある場合、これは無限のシーケンスにはなりません。それでも、Clone を作成するのは非常に困難です。コンパイラはどのように IEnumerable 実装を生成して自動的に実行しますか?

クローンが作成されるとすぐに、両方のインスタンスが共有するバッファ システムから動作する必要があります。可能ですが、実際には必要ありません。これは、これらの種類のシーケンスが使用されるように設計されている方法ではありません。シーケンス内の場所を「命令的に」記憶するのではなく、値のように純粋に「機能的に」扱い、フィルターを再帰的に適用します。低レベルcar/cdr操作よりも少しクリーンです。

さらなる質問:

私のSchemeインタプリタでIEnumerableを使ってやりたいことがビルトインではなくスキームで実装できるようにするために必要な最低レベルの「プリミティブ」は何だろうか。

私が思う簡単な答えは、Abelson と Sussman、特にストリームに関する部分を調べることです。IEnumerableリストではなくストリームです。また、マップ、フィルター、アキュムレートなどの特別なバージョンを使用して作業する方法についても説明しています。彼らはまた、セクション 4.2 でリストとストリームを統合するという考えにも触れています。

于 2009-04-30T17:28:06.280 に答える
4

回避策として、複製を行った IEnumerator の拡張メソッドを簡単に作成できます。列挙子からリストを作成し、要素をメンバーとして使用するだけです。

ただし、列挙子のストリーミング機能は失われます-新しい「クローン」であるため、最初の列挙子が完全に評価されます。

于 2009-04-30T17:03:00.427 に答える
3

元の列挙子を手放すことができる場合、つまり. もう使用しない場合は、元の列挙子を取得し、それを 1 つ以上の列挙子のソースとして使用する "クローン" 関数を実装できます。

つまり、次のようなものを構築できます。

IEnumerable<String> original = GetOriginalEnumerable();
IEnumerator<String>[] newOnes = original.GetEnumerator().AlmostClone(2);
                                                         ^- extension method
                                                         produce 2
                                                         new enumerators

これらは、列挙された値を追跡するために、元の列挙子とリンクされたリストを内部的に共有できます。

これにより、次のことが可能になります。

  • 両方の列挙子が前方に進む限り、無限のシーケンス (リンクされたリストは、両方の列挙子が特定のポイントを通過すると、GC できるように記述されます)
  • 遅延列挙、元の列挙子からまだ取得されていない値を必要とする 2 つの列挙子の最初の列挙子は、それを取得し、それを生成する前にリンクされたリストに格納します。

ここでの問題はもちろん、列挙子の 1 つが他の列挙子よりもはるかに先に移動した場合でも、大量のメモリが必要になることです。

これがソースコードです。Subversion を使用している場合は、Visual Studio 2008 ソリューション ファイルと、以下のコードを含むクラス ライブラリ、および別の単体テスト プロジェクトをダウンロードできます。

リポジトリ: http://vkarlsen.serveftp.com:81/svnStackOverflow/SO847655
ユーザー名とパスワードはどちらも引用符なしで「guest」です。

このコードはまったくスレッドセーフではないことに注意してください。

public static class EnumeratorExtensions
{
    /// <summary>
    /// "Clones" the specified <see cref="IEnumerator{T}"/> by wrapping it inside N new
    /// <see cref="IEnumerator{T}"/> instances, each can be advanced separately.
    /// See remarks for more information.
    /// </summary>
    /// <typeparam name="T">
    /// The type of elements the <paramref name="enumerator"/> produces.
    /// </typeparam>
    /// <param name="enumerator">
    /// The <see cref="IEnumerator{T}"/> to "clone".
    /// </param>
    /// <param name="clones">
    /// The number of "clones" to produce.
    /// </param>
    /// <returns>
    /// An array of "cloned" <see cref="IEnumerator[T}"/> instances.
    /// </returns>
    /// <remarks>
    /// <para>The cloning process works by producing N new <see cref="IEnumerator{T}"/> instances.</para>
    /// <para>Each <see cref="IEnumerator{T}"/> instance can be advanced separately, over the same
    /// items.</para>
    /// <para>The original <paramref name="enumerator"/> will be lazily evaluated on demand.</para>
    /// <para>If one enumerator advances far beyond the others, the items it has produced will be kept
    /// in memory until all cloned enumerators advanced past them, or they are disposed of.</para>
    /// </remarks>
    /// <exception cref="ArgumentNullException">
    /// <para><paramref name="enumerator"/> is <c>null</c>.</para>
    /// </exception>
    /// <exception cref="ArgumentOutOfRangeException">
    /// <para><paramref name="clones"/> is less than 2.</para>
    /// </exception>
    public static IEnumerator<T>[] Clone<T>(this IEnumerator<T> enumerator, Int32 clones)
    {
        #region Parameter Validation

        if (Object.ReferenceEquals(null, enumerator))
            throw new ArgumentNullException("enumerator");
        if (clones < 2)
            throw new ArgumentOutOfRangeException("clones");

        #endregion

        ClonedEnumerator<T>.EnumeratorWrapper wrapper = new ClonedEnumerator<T>.EnumeratorWrapper
        {
            Enumerator = enumerator,
            Clones = clones
        };
        ClonedEnumerator<T>.Node node = new ClonedEnumerator<T>.Node
        {
            Value = enumerator.Current,
            Next = null
        };

        IEnumerator<T>[] result = new IEnumerator<T>[clones];
        for (Int32 index = 0; index < clones; index++)
            result[index] = new ClonedEnumerator<T>(wrapper, node);
        return result;
    }
}

internal class ClonedEnumerator<T> : IEnumerator<T>, IDisposable
{
    public class EnumeratorWrapper
    {
        public Int32 Clones { get; set; }
        public IEnumerator<T> Enumerator { get; set; }
    }

    public class Node
    {
        public T Value { get; set; }
        public Node Next { get; set; }
    }

    private Node _Node;
    private EnumeratorWrapper _Enumerator;

    public ClonedEnumerator(EnumeratorWrapper enumerator, Node firstNode)
    {
        _Enumerator = enumerator;
        _Node = firstNode;
    }

    public void Dispose()
    {
        _Enumerator.Clones--;
        if (_Enumerator.Clones == 0)
        {
            _Enumerator.Enumerator.Dispose();
            _Enumerator.Enumerator = null;
        }
    }

    public T Current
    {
        get
        {
            return _Node.Value;
        }
    }

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

    public Boolean MoveNext()
    {
        if (_Node.Next != null)
        {
            _Node = _Node.Next;
            return true;
        }

        if (_Enumerator.Enumerator.MoveNext())
        {
            _Node.Next = new Node
            {
                Value = _Enumerator.Enumerator.Current,
                Next = null
            };
            _Node = _Node.Next;
            return true;
        }

        return false;
    }

    public void Reset()
    {
        throw new NotImplementedException();
    }
}
于 2009-05-11T11:13:46.090 に答える
1

これは、リフレクションを使用して新しいインスタンスを作成し、新しいインスタンスに値を設定します。また、C# in Depth のこの章が非常に役立つこともわかりました。 Iterator ブロックの実装の詳細: 自動生成されたステート マシン

static void Main()
{
    var counter = new CountingClass();
    var firstIterator = counter.CountingEnumerator();
    Console.WriteLine("First list");
    firstIterator.MoveNext();
    Console.WriteLine(firstIterator.Current);

    Console.WriteLine("First list cloned");
    var secondIterator = EnumeratorCloner.Clone(firstIterator);

    Console.WriteLine("Second list");
    secondIterator.MoveNext();
    Console.WriteLine(secondIterator.Current);
    secondIterator.MoveNext();
    Console.WriteLine(secondIterator.Current);
    secondIterator.MoveNext();
    Console.WriteLine(secondIterator.Current);

    Console.WriteLine("First list");
    firstIterator.MoveNext();
    Console.WriteLine(firstIterator.Current);
    firstIterator.MoveNext();
    Console.WriteLine(firstIterator.Current);
}

public class CountingClass
{
    public IEnumerator<int> CountingEnumerator()
    {
        int i = 1;
        while (true)
        {
            yield return i;
            i++;
        }
    }
}

public static class EnumeratorCloner
{
    public static T Clone<T>(T source) where T : class, IEnumerator
    {
        var sourceType = source.GetType().UnderlyingSystemType;
        var sourceTypeConstructor = sourceType.GetConstructor(new Type[] { typeof(Int32) });
        var newInstance = sourceTypeConstructor.Invoke(new object[] { -2 }) as T;

        var nonPublicFields = source.GetType().GetFields(BindingFlags.NonPublic | BindingFlags.Instance);
        var publicFields = source.GetType().GetFields(BindingFlags.Public | BindingFlags.Instance);
        foreach (var field in nonPublicFields)
        {
            var value = field.GetValue(source);
            field.SetValue(newInstance, value);
        }
        foreach (var field in publicFields)
        {
            var value = field.GetValue(source);
            field.SetValue(newInstance, value);
        }
        return newInstance;
    }
}

この回答は、次の質問でも使用されました IEnumerable インスタンスを複製して、反復状態のコピーを保存できますか?

于 2010-02-23T01:51:02.660 に答える
0

これを拡張メソッドとして使用しない理由:

public static IEnumerator<T> Clone(this IEnumerator<T> original)
{
    foreach(var v in original)
        yield return v;
}

これは基本的に、元の列挙子を完全に評価することなく、新しい列挙子を作成して返します。

編集:はい、読み間違えました。Paul は正しいです。これは IEnumerable でのみ機能します。

于 2009-04-30T17:08:37.870 に答える
-2

IEnumerable.GetEnumerator という最初の列挙子を作成したのと同じ方法で、新しい列挙子を作成する方法が既にあります。同じことをするために別のメカニズムが必要な理由がわかりません。

そして、DRY 原則の精神に基づいて、新しい IEnumerator インスタンスを作成する責任を、列挙可能なクラスと列挙子クラスの両方で複製する必要がある理由に興味があります。列挙子に、必要以上の追加の状態を維持するように強制することになります。

たとえば、リンクされたリストの列挙子を想像してください。IEnumerable の基本的な実装では、そのクラスは現在のノードへの参照を保持するだけで済みます。ただし、クローンをサポートするには、リストの先頭への参照も保持する必要があります-それ以外の場合は使用されません*。ソース (IEnumerable) に移動して別の列挙子を取得できるのに、なぜその余分な状態を列挙子に追加するのでしょうか?

また、テストする必要があるコード パスの数を 2 倍にする必要があるのはなぜでしょうか? オブジェクトを製造する新しい方法を作成するたびに、複雑さが増しています。

*Reset を実装した場合はヘッド ポインターも必要になりますが、 docs によると、Reset は COM 相互運用のためにのみ存在し、自由に NotSupportedException をスローできます。

于 2009-04-30T17:27:15.750 に答える