2009-04-30 22 views
8

En la implementación de un intérprete de Scheme básica en C# descubrí, para mi horror, el problema siguiente:¿Por qué no se puede clonar IEnumerator?

IEnumerator no tiene un método de clon! (o más precisamente, IEnumerable no puede proporcionarme un enumerador "clonable").

Lo que me gustaría:

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

no puede subir con una implementación de IEnumerable que no sería capaz de suministrar un eficiente Cloneable IEnumerator (vectores, listas enlazadas, etc., todos serían capaces de proporcionar una implementación trivial de IEnumerator's Clone() como se especifica arriba ... ¡sería más fácil que proporcionar un método Reset() de todos modos!).

La ausencia del método Clone significa que cualquier modismo funcional/recursivo de enumerar a lo largo de una secuencia no funcionará.

También significa que no puedo hacer que "Imperablemente" haga que IEnumerable se comporte como Lisp "listas" (para las cuales usa car/cdr para enumerar recursivamente). es decir, la única implementación de "(cdr algunos IEnumerable)" sería lamentablemente ineficiente.

¿Alguien puede sugerir un ejemplo realista y útil de un objeto IEnumerable que no podría proporcionar un método eficiente "Clone()"? ¿Es que habría un problema con la construcción de "rendimiento"?

¿Alguien puede sugerir una solución?

+0

No estoy seguro de por qué quiere un IEnumerator clonable, pero ¿sería útil un IEnumerable clonable? – Lucas

+1

FYI, se puede clonar. Mi respuesta hace mucho tiempo muestra cómo. En realidad clona el IEnumerator y no los valores creados a partir de él. – BenMaddox

Respuesta

23

¡La lógica es inexorable! IEnumerable no es compatible con Clone, y necesita Clone, por lo que no debe usar IEnumerable.

O más exactamente, no debe utilizarlo como la base fundamental para trabajar en un intérprete de Scheme. ¿Por qué no hacer una lista vinculada inmóvil trivial en su lugar?

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

Tenga en cuenta que el método ToEnumerable le da el uso conveniente en el directorio C# forma estándar.

Para responder a su pregunta:

Puede alguien sugerir un realista, útil, ejemplo de un objeto IEnumerable que no sería capaz de proporcionar un método "() Clon" eficiente? ¿Es que habría un problema con el constructo "yield"?

Un IEnumerable puede ir a cualquier parte del mundo para sus datos. He aquí un ejemplo que lee líneas desde la consola:

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

Hay dos problemas con este: en primer lugar, una función Clone no sería particularmente fácil de escribir (y Reset no tendría sentido). En segundo lugar, la secuencia es infinita, lo cual es perfectamente permisible. Las secuencias son flojas.

Otro ejemplo:

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

Para estos dos ejemplos, la "solución" que haya aceptado no sería de mucha utilidad, ya que acaba de agotar la memoria disponible o colgar para siempre. Pero estos son ejemplos perfectamente válidos de secuencias.

Para comprender las secuencias C# y F #, debe consultar las listas en Haskell, no las listas en Scheme.

En caso de que creo la materia infinita es una pista falsa, ¿qué hay de la lectura de los bytes desde un socket:

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

Si hay algún número de bytes que se envían por el zócalo, esto no será una secuencia infinita Y sin embargo escribir Clone sería muy difícil. ¿Cómo generaría el compilador la implementación IEnumerable para hacerlo automáticamente?

Tan pronto como se creó un clon, ambas instancias tendrían que funcionar desde un sistema de búfer que compartieron. Es posible, pero en la práctica no es necesario, así no es cómo se diseñan estos tipos de secuencias para su uso. Los trata de manera puramente "funcional", como valores, aplicando filtros recursivamente, en lugar de recordar "imperativamente" una ubicación dentro de la secuencia.Es un poco más limpio que la manipulación de bajo nivel car/cdr.

Además pregunta:

Me pregunto, ¿cuál es el nivel más bajo "primitivo (s)" que necesitaría tal que nada de lo que desee hacer con un IEnumerable en mi esquema intérprete podría implementarse en el esquema en lugar de que como un built-in.

La respuesta corta, creo que sería buscar en Abelson and Sussman y en particular the part about streams. IEnumerable es una secuencia, no una lista. Y describen cómo necesita versiones especiales de mapa, filtro, acumulación, etc. para trabajar con ellos. También tienen la idea de unificar listas y flujos en la sección 4.2.

+0

Sí, sé cómo escribir una lista vinculada. Estoy tratando de evitar que todo el código C# (en particular, cualquier función personalizada) tenga que convertir todos los IEnumerables en listas vinculadas por adelantado. Me doy cuenta de que eso no es posible ... pero ahora me pregunto * por qué * ¿no hicieron IEnumerator clonable? –

+0

nota: He votado su respuesta de todos modos, gracias a la entrada –

+0

Vea la respuesta actualizada para el "por qué", también una razón por la cual la solución "hacer una copia" no es del todo correcta. –

4

Como solución alternativa, puede hacer fácilmente un método de extensión para IEnumerator que realizó su clonación. Simplemente cree una lista del enumerador y use los elementos como miembros.

Sin embargo, perdería las capacidades de transmisión de un enumerador, ya que su nuevo "clon" haría que el primer enumerador lo evaluara por completo.

+0

mejor, la respuesta más útil hasta el momento ... pero aún me gustaría un ejemplo de por qué no podían hacer IEnumerator clonable ... (resaltó el bit en negrita en mi pregunta). –

+0

Como mencioné, cualquier caso en el que se aproveche de la transmisión (ejecución diferida) de un IEnumerator se romperá o al menos perderá las ventajas, tan pronto como haya clonado el enumerador. Es más una cuestión de costos versus beneficios de proporcionar funcionalidad de clonación. –

+0

sí, no, me doy cuenta del costo en su solución ... el punto es, ¿hay alguna implementación * realista * si IEnumerable/IEnumerator que no podría proporcionar un método de clonación eficiente ...? –

0

Por qué no esto como un método de extensión:

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

Esto, básicamente, crear y devolver una nueva empadronador sin evaluar plenamente la original.

Editar: Sí, he leído mal. Paul tiene razón, esto solo funcionaría con IEnumerable.

+0

Eso no funcionará, no puede foreach sobre un IEnumerator, ¿verdad? Solo sobre un IEnumerable ... –

+0

Este código ni siquiera compilará, no puede foreach sobre IEnumerator original y no puede usar yield para devolver IEnumerator . Probablemente se refería a IEnumerable en ambos casos. – Lucas

-2

Ya existe una manera de crear un nuevo enumerador, del mismo modo que creó el primero: IEnumerable.GetEnumerator. No estoy seguro de por qué necesita otro mecanismo para hacer lo mismo.

Y siguiendo el espíritu del DRY principle, tengo curiosidad por saber por qué querrías que la responsabilidad de crear nuevas instancias de IEnumerator se duplicara tanto en tu enumerable como en tus clases de enumerador. Usted estaría forzando al enumerador a mantener un estado adicional más allá de lo requerido.

Por ejemplo, imagine un enumerador para una lista vinculada. Para la implementación básica de IEnumerable, esa clase solo necesitaría mantener una referencia al nodo actual. Pero para respaldar su Clone, también debería mantener una referencia al encabezado de la lista, algo que de otra manera no le serviría *. ¿Por qué agregaría ese estado adicional al enumerador, cuando puede ir al origen (el IEnumerable) y obtener otro enumerador?

¿Y por qué doblaría la cantidad de rutas de código que necesita probar? Cada vez que crea una nueva forma de fabricar un objeto, agrega complejidad.

* También sería necesario el puntero cabeza si ha implementado Reset, pero according to the docs, Reset es allí sólo para la interoperabilidad COM, y usted es libre de lanzar una NotSupportedException.

+1

Un enumerador clonado no apuntaría al primer elemento de la secuencia. Apuntaría al elemento actual del enumerador original. El objetivo sería poder recordar la posición actual. –

+1

Algunos enumeradores podían clonar su posición actual, pero muchos no podían hacerlo. Cursores de base de datos orientados solo hacia adelante, por ejemplo; o cualquier cosa que lea desde un flujo de red o tubería. Incluso algo que lea de un recurso local, como una secuencia de archivos, requeriría mucho trabajo para poder clonarse, ya que un manejador de archivo solo tiene una posición actual. –

0

Esto podría ayudar. Se necesita un poco de código para llamar a Dispose() en el 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(); 
} 
2

Si puede dejar que el empadronador original de ir, es decir. No lo use más, puede implementar una función "clonar" que toma el enumerador original y lo usa como fuente para uno o más enumeradores.

En otras palabras, se podría construir algo como esto:

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

Estos podrían compartir internamente el empadronador original, y una lista enlazada, para realizar un seguimiento de los valores enumerados.

Esto permitiría:

  • secuencias infinitas, siempre que ambos enumeradores progresan hacia adelante (la lista enlazada sería escrita de tal manera que una vez que ambos enumeradores han pasado un punto específico, ésos se pueden GC'ed)
  • enumeración perezoso, el primero de los dos encuestadores que necesitan un valor que no se ha recuperado del empadronador original, sin embargo, que obtendría y almacenarlo en la lista enlazada antes de ceder su

problema aquí es por supuesto th en eso todavía requeriría mucha memoria si uno de los enumeradores se mueve mucho más adelante que el otro.

Aquí está el código fuente. Si usa Subversion, puede descargar el archivo de solución de Visual Studio 2008 con una biblioteca de clase con el código siguiente, así como un poryecto de prueba de unidad por separado.

Repositorio: http://vkarlsen.serveftp.com:81/svnStackOverflow/SO847655
nombre de usuario y la contraseña es a la vez 'invitado', sin las comillas.

Tenga en cuenta que este código no es seguro para subprocesos, en absoluto.

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

Inteligente ... por lo que es como una versión perezosamente evaluada de la respuesta de Reed Copsey (por lo que solo utiliza todos los elementos de la lista si realmente la usa de esa manera). –

+0

Bien, publicaré un ejemplo de implementación un poco más tarde, enseñando una clase en este momento. –

+0

Estaré muy interesado en ver esto. Empecé a escribir lo mismo para mi respuesta el otro día, pero nunca lo terminé. –

1

Este utiliza la reflexión para crear una nueva instancia y luego establece los valores de la nueva instancia. También encontré que este capítulo de C# en profundidad es muy útil. Iterator block implementation details: auto-generated state machines

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

Esta respuesta también se utilizó en la siguiente pregunta Is it possible to clone an IEnumerable instance, saving a copy of the iteration state?

+1

Esto no funcionará en todos los casos, y se basa en el comportamiento no documentado (puede funcionar ahora, pero no más adelante). Ver este comentario: http://stackoverflow.com/questions/807991/why-cant-ienumerators-be-cloned#comment621350_808121 Sin embargo, si ha creado el enumerador usted mismo, no solo puede verificar que es seguro hacer un clon de miembro , pero también puedes hacer un método de clonación adecuado. – Brent

0

El propósito de enumeradores "clonable" es principalmente para poder guardar la posición iteración y ser capaz de volver a ella más tarde. Eso significa que el contenedor iterado debe proporcionar una interfaz más completa que solo IEnumerable. En realidad, es algo entre IEnumerable y IList. Trabajando con IList puede simplemente usar un índice entero como enumerador, o crear una clase de envoltura inmutable simple, manteniendo una referencia a la lista y posición actual.

Si su contenedor no es compatible con el acceso aleatorio y solo puede repetirse (como la lista unidireccional), al menos debe proporcionar la capacidad de obtener el siguiente elemento, haciendo referencia al anterior o a alguna "iteración" declara "que puedes mantener en tu iterador". Por lo tanto, la interfaz puede tener este aspecto:

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

Tenga en cuenta que el iterador es inmutable, no puede ser "movido hacia adelante", sólo se puede solicitar a nuestro contenedor iterable para darnos un nuevo iterador que apunta a la siguiente posición. El beneficio de esto es que puede almacenar iteradores en cualquier lugar todo el tiempo que lo necesite, por ejemplo, tener una pila de iteradores y regresar a la posición previamente guardada cuando lo necesite. Puede guardar la posición actual para su uso posterior asignándola a una variable, tal como lo haría con un índice entero.

La propiedad AllRest puede ser útil si necesita iterar desde la posición dada hasta el final del contenedor utilizando funciones de iteración de lenguaje estándar, como foraech o LinQ. No cambiará la posición del iterador (recuerde, nuestro iterador es inmutable). La implementación puede repetidamente GetNext y yleid return.

El método GetNext puede ser en realidad una parte de iterador en sí, así:

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

Esto es más o menos lo mismo. La lógica de determinar el siguiente estado se acaba de pasar de la implementación del contenedor a la implementación del iterador . Tenga en cuenta que el iterador sigue siendo inmutable. No puedes "moverlo hacia adelante", solo puedes obtener otro, apuntando al siguiente elemento.

Cuestiones relacionadas