Почему нельзя клонировать IEnumerator?

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

  •  03-07-2019
  •  | 
  •  

Вопрос

При реализации интерпретатора basic Scheme на C # я, к своему ужасу, обнаружил следующую проблему:

В IEnumerator нет метода клонирования!(или, точнее, IEnumerable не может предоставить мне "клонируемый" перечислитель).

Чего бы я хотел:

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

Я не могу придумать реализацию IEnumerable, которая не смогла бы предоставить эффективно клонируемый IEnumerator (векторы, связанные списки и т.д.все они были бы в состоянии обеспечить тривиальную реализацию функции Clone() IEnumerator, как указано выше...в любом случае, это было бы проще, чем предоставлять метод Reset()!).

Отсутствие метода Clone означает, что любая функциональная / рекурсивная идиома перечисления по последовательности не будет работать.

Это также означает, что я не могу "плавно" заставить IEnumerable вести себя как Lisp "списки" (для которых вы используете car / cdr для рекурсивного перечисления).т. е.единственная реализация "(cdr некоторые IEnumerable)" было бы крайне неэффективно.

Кто-нибудь может предложить реалистичный, полезный пример объекта IEnumerable, который не смог бы обеспечить эффективный метод "Clone ()"?Дело в том, что возникнет проблема с конструкцией "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 , который не смог бы предоставить эффективный метод "Clone ()"?Это из-за того, что возникла бы проблема с конструкцией "yield"?

IEnumerable может обратиться за своими данными в любую точку мира.Вот пример, который считывает строки из консоли:

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

С этим связаны две проблемы:во-первых, a Clone функция была бы не особенно проста в написании (и Reset было бы бессмысленно).Во-вторых, последовательность бесконечна, что вполне допустимо.Последовательности ленивы.

Другой пример:

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

Для обоих этих примеров "обходной путь", который вы приняли, не принес бы большой пользы, потому что он просто исчерпал бы доступную память или зависнул бы навсегда.Но это вполне допустимые примеры последовательностей.

Чтобы понять последовательности C # и F #, вам нужно посмотреть на списки в Haskell, а не на списки в Scheme.

В случае, если вы думаете, что бесконечный материал - это отвлекающий маневр, как насчет чтения байтов из сокета:

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];       
    }
}

Если по сокету передается некоторое количество байтов, это не будет бесконечной последовательностью.И все же написать клон для него было бы очень сложно.Как бы компилятор сгенерировал реализацию IEnumerable, чтобы сделать это автоматически?

Как только был создан Клон, оба экземпляра теперь должны были работать из буферной системы, которую они совместно использовали.Это возможно, но на практике в этом нет необходимости - такие последовательности предназначены не для такого использования.Вы обрабатываете их чисто "функционально", как значения, применяя к ним фильтры рекурсивно, а не "императивно" запоминая местоположение в последовательности.Это немного чище, чем низкоуровневый car/cdr манипуляция.

Следующий вопрос:

Интересно, какой самый низкий уровень "примитивы" мне понадобились бы для того, чтобы все, что я мог бы захотеть сделать с Интерфейс IEnumerable в моей схеме переводчика может быть реализован в схеме, а чем как строение.

Короткий ответ, я думаю, состоял бы в том, чтобы заглянуть в Абельсон и Сассман и в частности часть о потоках. IEnumerable это поток, а не список.И они описывают, как вам нужны специальные версии map, filter, accumulate и т.д.работать с ними.Они также переходят к идее объединения списков и потоков в разделе 4.2.

Другие советы

В качестве обходного пути вы могли бы легко создать метод расширения для IEnumerator, который выполнил ваше клонирование.Просто создайте список из перечислителя и используйте элементы в качестве членов.

Однако вы потеряете возможности потоковой передачи перечислителя - поскольку вы новичок, "клонирование" приведет к полной оценке первого перечислителя.

Если вы можете отпустить исходный перечислитель, т.е..чтобы больше не использовать его, вы можете реализовать функцию "clone", которая берет исходный перечислитель и использует его в качестве источника для одного или нескольких перечислителей.

Другими словами, вы могли бы построить что-то вроде этого:

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

Они могли бы совместно использовать исходный перечислитель и связанный список, чтобы отслеживать перечисленные значения.

Это позволило бы:

  • Бесконечные последовательности, до тех пор, пока оба счетчика продвигаются вперед (связанный список будет написан таким образом, что как только оба счетчика пройдут определенную точку, они могут быть объединены)
  • Ленивое перечисление, первый из двух счетчиков, которому требуется значение, которое еще не было извлечено из исходного счетчика, он получит его и сохранит в связанном списке, прежде чем выдавать его

Проблема здесь, конечно, в том, что для этого все равно потребуется много памяти, если один из счетчиков будет намного опережать другой.

Вот исходный код.Если вы используете 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;
}

Это в основном привело бы к созданию и возврату нового перечислителя без полной оценки оригинала.

Редактировать:Да, я неправильно понял.Пол прав, это будет работать только с IEnumerable.

Это могло бы помочь.Нужен некоторый код для вызова Dispose() в IEnumerator:

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 вы можете просто использовать целочисленный индекс в качестве перечислителя или создать простой неизменяемый класс переноса, содержащий ссылку на список и текущую позицию.

Если ваш контейнер не поддерживает произвольный доступ и может быть повторен только вперед (например, однонаправленный связанный список), он должен, по крайней мере, обеспечивать возможность получения следующего элемента, имеющего ссылку на предыдущий или на некоторое "состояние итерации", которое вы можете сохранить в своем итераторе.Итак, интерфейс может выглядеть следующим образом: 

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

Это почти то же самое.Логика определения следующего состояния просто перенесена из реализации контейнера в реализацию итератора .Обратите внимание, что итератор по-прежнему неизменяемый.Вы не можете "переместить его вперед", вы только можете получить другой, указывающий на следующий элемент.

Уже есть способ создать новый перечислитель - так же, как вы создали первый:IEnumerable.GetEnumerator.Я не уверен, зачем вам нужен другой механизм для выполнения того же самого.

И в духе СУХОЙ принцип, Мне любопытно, почему вы хотели бы, чтобы ответственность за создание новых экземпляров IEnumerator дублировалась как в вашем enumerable, так и в вашем enumerator классах.Вы бы вынудили перечислитель поддерживать дополнительное состояние сверх того, что требуется.

Например, представьте себе перечислитель для связанного списка.Для базовой реализации IEnumerable этому классу потребуется только сохранить ссылку на текущий узел.Но для поддержки вашего Клона ему также необходимо было бы сохранить ссылку на начало списка - то, для чего в противном случае он бесполезен *.Зачем вам добавлять это дополнительное состояние к перечислителю, когда вы можете просто перейти к источнику (IEnumerable) и получить другой перечислитель?

И зачем вам удваивать количество путей к коду, которые вам нужно протестировать?Каждый раз, когда вы изобретаете новый способ изготовления объекта, вы усложняете его.

* Вам также понадобился бы указатель head, если бы вы реализовали Reset, но согласно документам, Сброс доступен только для COM-взаимодействия, и вы можете создать исключение NotSupportedException .

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top