IEnumerator のクローンを作成できないのはなぜですか?

StackOverflow https://stackoverflow.com/questions/807991

  •  03-07-2019
  •  | 
  •  

質問

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

IEnumerator にはクローン メソッドがありません。(より正確に言えば、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 いくつかの IEnumerable)」はひどく非効率的です。

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

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

役に立ちましたか？

解決

論理は容赦ない！ 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＃の方法で便利に使用できます。

質問に答えるには：

  

誰もが現実的なことを提案できますか、   便利な、IEnumerableの例   できないオブジェクト   効率的な＆quot; Clone（）＆quot;を提供します。方法？   問題があるのでしょうか？   「歩留り」構築しますか？

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 操作よりも少しクリーンです。

追加の質問：

  

最低レベルは何だろう   ＆quot; primitive（s）＆quot;私はそのようなものが必要だろう   私がやりたいことは何でも   SchemeインタープリターのIEnumerable   むしろスキームで実装できます   ビルトインとして。

簡単な答えは、 Abelson and Sussman 特に部分ストリームについて。 IEnumerable はストリームであり、リストではありません。そして、それらは、それらを使用するために、マップ、フィルター、蓄積などの特別なバージョンが必要な方法を説明します。また、セクション4.2でリストとストリームを統合するというアイデアも得ています。

他のヒント

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

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

元の列挙子を解放できる場合、つまりもう使用しない場合は、「クローン」を実装できます。元の列挙子を取り、それを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
ユーザー名とパスワードは両方とも引用符なしの「ゲスト」です。

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

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();
    }
}

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

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インスタンスを複製して、反復状態のコピーを保存することは可能ですか？

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

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

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

編集：はい、読み間違えました。Paul の言うとおりです。これは IEnumerable でのみ機能します。

これは役立つかもしれません。 IEnumeratorでDispose（）を呼び出すためのコードが必要です。

class Program
{
    static void Main(string[] args)
    {
        //var list = MyClass.DequeueAll().ToList();
        //var list2 = MyClass.DequeueAll().ToList();

        var clonable = MyClass.DequeueAll().ToClonable();


        var list = clonable.Clone().ToList();
        var list2 = clonable.Clone()ToList();
        var list3 = clonable.Clone()ToList();
    }
}

class MyClass
{
    static Queue<string> list = new Queue<string>();

    static MyClass()
    {
        list.Enqueue("one");
        list.Enqueue("two");
        list.Enqueue("three");
        list.Enqueue("four");
        list.Enqueue("five");
    }

    public static IEnumerable<string> DequeueAll()
    {
        while (list.Count > 0)
            yield return list.Dequeue();
    }
}

static class Extensions
{
    public static IClonableEnumerable<T> ToClonable<T>(this IEnumerable<T> e)
    {
        return new ClonableEnumerable<T>(e);
    }
}

class ClonableEnumerable<T> : IClonableEnumerable<T>
{
    List<T> items = new List<T>();
    IEnumerator<T> underlying;

    public ClonableEnumerable(IEnumerable<T> underlying)
    {
        this.underlying = underlying.GetEnumerator();
    }

    public IEnumerator<T> GetEnumerator()
    {
        return new ClonableEnumerator<T>(this);
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }

    private object GetPosition(int position)
    {
        if (HasPosition(position))
            return items[position];

        throw new IndexOutOfRangeException();
    }

    private bool HasPosition(int position)
    {
        lock (this)
        {
            while (items.Count <= position)
            {
                if (underlying.MoveNext())
                {
                    items.Add(underlying.Current);
                }
                else
                {
                    return false;
                }
            }
        }

        return true;
    }

    public IClonableEnumerable<T> Clone()
    {
        return this;
    }


    class ClonableEnumerator<T> : IEnumerator<T>
    {
        ClonableEnumerable<T> enumerable;
        int position = -1;

        public ClonableEnumerator(ClonableEnumerable<T> enumerable)
        {
            this.enumerable = enumerable;
        }

        public T Current
        {
            get
            {
                if (position < 0)
                    throw new Exception();
                return (T)enumerable.GetPosition(position);
            }
        }

        public void Dispose()
        {
        }

        object IEnumerator.Current
        {
            get { return this.Current; }
        }

        public bool MoveNext()
        {
            if(enumerable.HasPosition(position + 1))
            {
                position++;
                return true;
            }
            return false;
        }

        public void Reset()
        {
            position = -1;
        }
    }


}

interface IClonableEnumerable<T> : IEnumerable<T>
{
    IClonableEnumerable<T> Clone();
}

「クローン化可能」の目的列挙子の主な目的は、反復位置を保存し、後でその位置に戻ることができるようにすることです。つまり、反復コンテナは IEnumerable よりも豊富なインターフェイスを提供する必要があります。実際には、 IEnumerable と IList の間の何かです。 IList を使用して、整数インデックスを列挙子として使用するか、リストと現在の位置への参照を保持する単純な不変のラップクラスを作成できます。

コンテナがランダムアクセスをサポートせず、前方にしか反復できない場合（一方向リンクリストなど）、少なくとも前の要素または一部の反復への参照を持つ次の要素を取得する機能を提供する必要があります州＆quot;イテレータで保持できます。そのため、インターフェースは次のようになります。

interface IIterable<T>
{
    IIterator<T> GetIterator(); // returns an iterator positioned at start
    IIterator<T> GetNext(IIterator<T> prev); // returns an iterator positioned at the next element from the given one
}

interface IIterator<T>
{
    T Current { get; }
    IEnumerable<T> AllRest { get; }
}

イテレータは不変であり、「前方に移動」することはできません。次の位置を指す新しいイテレータを提供するように反復可能なコンテナに要求することしかできません。その利点は、必要な限りどこにでもイテレータを格納できることです。たとえば、イテレータのスタックを持ち、必要なときに以前に保存した位置に戻ります。整数インデックスを使用する場合と同様に、変数に代入することにより、後で使用するために現在の位置を保存できます。

AllRest プロパティは、 foraech やLinQなどの標準言語反復機能を使用して、指定された位置からコンテナの最後まで反復する必要がある場合に役立ちます。イテレータの位置は変更されません（イテレータは不変です）。実装は、繰り返し GetNext および yleid return を実行できます。

GetNext メソッドは、実際には次のようにイテレータ自体の一部にすることができます。

interface IIterable<T>
{
    IIterator<T> GetIterator(); // returns an iterator positioned at start
}

interface IIterator<T>
{
    T Current { get; }
    IIterator<T> GetNext { get; } // returns an iterator positioned at the next element from the given one
    IEnumerable<T> AllRest { get; }
}

これはほとんど同じです。次の状態を決定するロジックは、コンテナ実装からイテレータに移動されただけです 実装。イテレータはまだ不変であることに注意してください。 「前方に移動」することはできません。次の要素を指し示す別の要素のみを取得できます。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top