Почему IEnumerator не может быть клонирован? - PullRequest
8 голосов
/ 30 апреля 2009

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

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

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

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

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

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

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

Может ли кто-нибудь предложить реалистичный, полезный пример объекта IEnumerable, который не сможет обеспечить эффективный метод "Clone ()"? Неужели проблема с конструкцией «yield»?

Может кто-нибудь предложить обходной путь?

Ответы [ 8 ]

23 голосов
/ 30 апреля 2009

логика неумолима! 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 ()"? Это было бы проблемой с конструкция "урожайность"?

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

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

Есть две проблемы с этим: во-первых, функция 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, чтобы сделать это автоматически?

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

Дополнительный вопрос:

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

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

4 голосов
/ 30 апреля 2009

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

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

2 голосов
/ 11 мая 2009

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

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

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

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

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

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

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

Вот исходный код. Если вы используете 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();
    }
}
1 голос
/ 23 февраля 2010

Используется отражение для создания нового экземпляра, а затем задаются значения для нового экземпляра. Я также нашел эту главу из 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, сохранив копию состояния итерации?

0 голосов
/ 14 апреля 2016

Цель «клонируемых» перечислителей состоит в том, чтобы в основном сохранить итерационную позицию и вернуться к ней позже. Это означает, что повторяющийся контейнер должен обеспечивать более богатый интерфейс, чем просто 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; }
}

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

0 голосов
/ 01 мая 2009

Это может помочь. Требуется некоторый код для вызова 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();
}
0 голосов
/ 30 апреля 2009

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

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

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

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

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

0 голосов
/ 30 апреля 2009

Почему бы не использовать этот метод расширения:

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

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

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

...