¿Por qué no se puede clonar IEnumerator?
https://stackoverflow.com/questions/807991
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Al implementar un intérprete de Esquema básico en C # descubrí, para mi horror, el siguiente problema:
¡IEnumerator no tiene un método de clonación! (o, más precisamente, IEnumerable no puede proporcionarme un " enumerable " enumerador).
Lo que me gustaría:
interface IEnumerator<T>
{
bool MoveNext();
T Current { get; }
void Reset();
// NEW!
IEnumerator<T> Clone();
}
No puedo encontrar una implementación de IEnumerable que no pueda suministrar un IEnumerator clonable de manera eficiente (vectores, listas enlazadas, etc.) todos podrían proporcionar una implementación trivial del Clon () del IEnumerator como se especificó anteriormente. . De todos modos, sería más fácil que proporcionar un método de reinicio ().
La ausencia del método de clonación significa que cualquier idioma funcional / recursivo de enumeración sobre una secuencia no funcionará.
También significa que no puedo " perfectamente " hacer que IEnumerable se comporte como Lisp " listas " (para lo cual usas car / cdr para enumerar recursivamente). es decir, la única implementación de " (cdr some IEnumerable ) " sería muy ineficiente.
¿Alguien puede sugerir un ejemplo realista y útil de un objeto IEnumerable que no pueda proporcionar un eficiente " Clone () " ¿método? ¿Es que habría un problema con el " rendimiento " construir?
¿Alguien puede sugerir una solución?
Solución
¡La lógica es inexorable! IEnumerable no es compatible con Clone y necesita Clone , por lo que no debe usar IEnumerable .
O más precisamente, no debería usarlo como la base fundamental para trabajar en un intérprete de Scheme. ¿Por qué no hacer una lista enlazada inmutable 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 brinda un uso conveniente en la forma C # estándar.
Para responder a su pregunta:
¿Alguien puede sugerir un realista, útil, ejemplo de un IEnumerable objeto que no podría proporcionar un eficiente " Clone () " ¿método? Es que habría un problema con el " rendimiento " construir?
Un IEnumerable puede ir a cualquier parte del mundo por sus datos. Aquí hay un ejemplo que lee líneas desde la consola:
IEnumerable<string> GetConsoleLines()
{
for (; ;)
yield return Console.ReadLine();
}
Hay dos problemas con esto: en primer lugar, una función Clonar no sería particularmente sencilla de escribir (y Reset no tendría sentido). En segundo lugar, la secuencia es infinita, lo que es perfectamente permisible. Las secuencias son perezosas.
Otro ejemplo:
IEnumerable<int> GetIntegers()
{
for (int n = 0; ; n++)
yield return n;
}
Para estos dos ejemplos, la " solución temporal " que ha aceptado no sería de mucha utilidad, ya que solo agotaría la memoria disponible o colgaría para siempre. Pero estos son ejemplos perfectamente válidos de secuencias.
Para entender las secuencias de C # y F #, debes mirar las listas en Haskell, no las listas en Esquema.
En caso de que pienses que lo infinito es una pista falsa, ¿qué tal si lees 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 una cantidad de bytes que se envían por el socket, esto no será una secuencia infinita. Y sin embargo escribir Clon para eso 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 ahora tendrían que trabajar desde un sistema de búfer que compartieron. Es posible, pero en la práctica no es necesario, no es así como este tipo de secuencias están diseñadas para ser utilizadas. Los trata puramente "funcionalmente", valores similares, aplicándoles filtros recursivamente, en lugar de "imperativamente" recordando una ubicación dentro de la secuencia. Es un poco más limpio que la manipulación de car / cdr de bajo nivel.
Otra pregunta:
Me pregunto, ¿cuál es el nivel más bajo? " primitivo (s) " Necesitaría tal que cualquier cosa que quiera hacer con un IEnumerable en mi intérprete de Scheme podría ser implementado en el esquema en lugar que como una incorporada.
La respuesta corta creo que sería buscar en Abelson y Sussman y, en particular, la pieza sobre las corrientes . IEnumerable es un flujo, 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.
Otros consejos
Como solución alternativa, podría crear fácilmente un método de extensión para IEnumerator que hizo su clonación. Simplemente cree una lista desde el enumerador y use los elementos como miembros.
Sin embargo, perdería las capacidades de transmisión de un enumerador, ya que es nuevo " clone " causaría que el primer enumerador evalúe por completo.
Si puede dejar ir al enumerador original, es decir. Si no lo usas más, puedes implementar un " clon " función que toma el enumerador original y lo utiliza como fuente para uno o más enumeradores.
En otras palabras, podrías 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 enumerador original y una lista enlazada para realizar un seguimiento de los valores enumerados.
Esto permitiría:
- Secuencias infinitas, siempre que los dos enumeradores avancen (la lista enlazada se escribirá de tal manera que una vez que los dos enumeradores hayan pasado un punto específico, se pueden colocar en GC)
- La enumeración perezosa, el primero de los dos enumeradores que necesitan un valor que aún no se ha recuperado del enumerador original, lo obtendría y lo almacenaría en la lista vinculada antes de proporcionarlo
El problema aquí es, por supuesto, que aún requeriría mucha memoria si uno de los enumeradores se mueve muy por delante del 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 clases con el código a continuación, así como un proyecto de prueba de unidad separado.
Repositorio: http://vkarlsen.serveftp.com:81/svnStackOverflow/SO847655
El nombre de usuario y la contraseña son 'invitados', 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();
}
}
Esto utiliza la reflexión para crear una nueva instancia y luego establece los valores en la nueva instancia. También encontré que este capítulo de C # en profundidad es muy útil. detalles de la implementación del bloque Iterator: máquinas de estado generadas automáticamente
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 usó en la siguiente pregunta ¿Es posible clonar una instancia de IEnumerable, guardando una copia del estado de iteración?
¿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ía y devolvería un nuevo enumerador sin evaluar completamente el original.
Edit: Sí, lo he leído mal. Paul tiene razón, esto solo funcionaría con IEnumerable.
Esto podría ayudar. Necesita algo de código para llamar a Dispose () en 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();
}
El propósito de " clonable " los enumeradores son principalmente para poder guardar la posición de iteración y poder volver a ella más tarde. Eso significa que el contenedor iterado debe proporcionar una interfaz más rica que solo IEnumerable . En realidad, es algo entre IEnumerable y IList . Al trabajar con IList , puede usar un índice de enteros como enumerador o crear una clase de envoltura simple e inmutable, que contenga una referencia a la lista y la posición actual.
Si su contenedor no admite el acceso aleatorio y solo se puede iterar hacia adelante (como la lista enlazada unidireccional), al menos debe proporcionar la capacidad de obtener el siguiente elemento, con una referencia al anterior o a alguna iteración de " estado " que puedes tener en tu iterador. Entonces, la interfaz puede verse así:
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 se puede avanzar " ;, solo podemos pedirle a nuestro contenedor iterable que nos brinde un nuevo iterador que apunte a la siguiente posición. La ventaja de esto es que puede almacenar los iteradores en cualquier lugar todo el tiempo que necesite, por ejemplo, tener una pila de iteradores y volver a la posición guardada previamente 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 recorrer desde la posición dada hasta el final del contenedor utilizando las 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 una parte del propio iterador, 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 mueve de la implementación del contenedor al iterador implementación. Tenga en cuenta que el iterador sigue siendo inmutable . No puede " moverlo hacia adelante " ;, solo puede obtener otro, apuntando al siguiente elemento.
Ya existe una forma de crear un nuevo enumerador, de la misma manera que creó el primero: IEnumerable.GetEnumerator. No estoy seguro de por qué necesitas otro mecanismo para hacer lo mismo.
Y en el espíritu de Principio DRY , tengo curiosidad por saber por qué querría que la responsabilidad de crear nuevas instancias de IEnumerator se duplique tanto en su enumerable como en sus clases de enumerador. Estaría obligando al enumerador a mantener un estado adicional más allá de lo que se requiere.
Por ejemplo, imagine un enumerador para una lista enlazada. Para la implementación básica de IEnumerable, esa clase solo necesitaría mantener una referencia al nodo actual. Pero para respaldar a su Clon, también debería mantener una referencia al encabezado de la lista, algo que de otra manera no tiene uso para *. ¿Por qué agregaría ese estado adicional al enumerador, cuando solo puede ir a la fuente (el Enumerable) y obtener otro enumerador?
¿Y por qué duplicaría el número de rutas de código que necesita probar? Cada vez que creas una nueva forma de fabricar un objeto, agregas complejidad.
* También necesitaría el puntero de cabeza si implementó Reset, pero de acuerdo con los documentos , el reinicio solo está ahí para la interoperabilidad COM, y usted es libre de lanzar una excepción NotSupportedException.
