10

在用 C# 实现一个基本的 Scheme 解释器时,令我惊恐的是,我发现了以下问题:

IEnumerator 没有克隆方法!(或者更准确地说,IEnumerable 无法为我提供“可克隆”枚举器)。

我想要什么:

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

我无法想出一个 IEnumerable 的实现,它无法提供一个有效的可克隆 IEnumerator(向量、链表等),所有这些都能够提供一个简单的 IEnumerator 的 Clone() 实现,如上所述......它会无论如何都比提供 Reset() 方法更容易!)。

没有 Clone 方法意味着枚举序列的任何功能/递归习惯用法都不起作用。

这也意味着我不能“无缝”使 IEnumerable 的行为像 Lisp“列表”(您使用 car/cdr 递归枚举)。即“(cdr some IEnumerable)”的唯一实现将非常低效。

任何人都可以提出一个现实、有用的 IEnumerable 对象示例,该对象无法提供有效的“Clone()”方法吗?“产量”结构是否存在问题?

任何人都可以提出解决方法吗?

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# 方式方便地使用。

要回答您的问题:

任何人都可以提出一个现实、有用的 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 实现来自动执行它?

一旦创建了克隆,两个实例现在都必须从它们共享的缓冲区系统中工作。这是可能的,但实际上它不是必需的——这不是这些序列的设计使用方式。您将它们纯粹“功能性地”对待,就像值一样,递归地对它们应用过滤器,而不是“强制性地”记住序列中的位置。它比低级car/cdr操作要干净一些。

进一步的问题:

我想知道,我需要的最低级别的“原语”是什么,这样我可能想在我的 Scheme 解释器中对 IEnumerable 做的任何事情都可以在 scheme 中实现,而不是作为内置实现。

我认为简短的答案是查看Abelson 和 Sussman,尤其是有关流的部分IEnumerable是一个流,而不是一个列表。它们描述了您如何需要特殊版本的地图、过滤器、累积等来使用它们。他们还在 4.2 节中提出了统一列表和流的想法。

于 2009-04-30T17:28:06.280 回答
4

作为一种解决方法,您可以轻松地为进行克隆的 IEnumerator 创建一个扩展方法。只需从枚举器创建一个列表,并将元素用作成员。

但是,您将失去枚举器的流式传输功能 - 因为您是新的“克隆”,所以会导致第一个枚举器完全评估。

于 2009-04-30T17:03:00.427 回答
3

如果您可以让原始枚举数离开,即。不再使用它,您可以实现一个“克隆”函数,该函数采用原始枚举器,并将其用作一个或多个枚举器的源。

换句话说,你可以构建这样的东西:

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
用户名和密码都是“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 的这一章非常有用。 迭代器块实现细节:自动生成的状态机

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 回答
1

“可克隆”枚举器的目的主要是为了能够保存迭代位置并能够稍后返回。这意味着,迭代容器必须提供更丰富的接口,而不仅仅是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 )从给定位置迭代到容器末尾,该属性会很有用。它不会改变迭代器的位置(记住,我们的迭代器是不可变的)。执行可以反复GetNextyleid 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; }
}

这几乎是一样的。确定下一个状态的逻辑只是从容器实现转移到迭代器实现。请注意,迭代器仍然是不可变的。你不能“向前移动”,你只能得到另一个,指向下一个元素。

于 2016-04-13T23:19:09.450 回答
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 回答
0

这可能会有所帮助。它需要一些代码来调用 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();
}
于 2009-04-30T22:20:59.337 回答
-2

已经有一种方法可以创建一个新的枚举器——与创建第一个枚举器的方式相同:IEnumerable.GetEnumerator。我不确定为什么你需要另一种机制来做同样的事情。

本着DRY 原则的精神,我很好奇为什么您希望在您的可枚举类和您的枚举类中复制创建新 IEnumerator 实例的责任。您将强制枚举器保持超出所需的额外状态。

例如,想象一个链表的枚举器。对于 IEnumerable 的基本实现,该类只需要保留对当前节点的引用。但是为了支持你的克隆,它还需要保留对列表头部的引用——否则它对*没有用处。当您可以直接转到源(IEnumerable)并获取另一个枚举器时,为什么要将那个额外的状态添加到枚举器?

为什么要将需要测试的代码路径数量增加一倍?每次你用一种新的方法来制造一个物体,你都在增加复杂性。

*如果您实现了重置,您还需要头指针,但根据文档,重置仅用于 COM 互操作,您可以随意抛出 NotSupportedException。

于 2009-04-30T17:27:15.750 回答