Perché IEnumerator non può essere clonato?
https://stackoverflow.com/questions/807991
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Nell'implementare un interprete di Scheme di base in C # ho scoperto, con mio orrore, il seguente problema:
IEnumerator non ha un metodo clone! (o più precisamente, IEnumerable non può fornirmi un enumeratore "clonabile").
Cosa mi piacerebbe:
interface IEnumerator<T>
{
bool MoveNext();
T Current { get; }
void Reset();
// NEW!
IEnumerator<T> Clone();
}
Non riesco a trovare un'implementazione di IEnumerable che non sarebbe in grado di fornire un IEnumerator clonabile in modo efficiente (vettori, elenchi collegati, ecc. tutti sarebbero in grado di fornire un'implementazione banale di Clone () di IEnumerator come sopra specificato. sarebbe più semplice che fornire un metodo Reset () comunque!).
L'assenza del metodo Clone significa che qualsiasi linguaggio funzionale / ricorsivo di enumerazione su una sequenza non funzionerà.
Significa anche che non posso " senza soluzione di continuità " fare in modo che IEnumerable si comporti come Lisp " lists " (per il quale usi car / cdr per enumerare ricorsivamente). ovvero l'unica implementazione di " (cdr alcuni IEnumerable ) " sarebbe terribilmente inefficiente.
Qualcuno può suggerire un esempio realistico, utile, di un oggetto IEnumerable che non sarebbe in grado di fornire un efficiente " Clone () " metodo? È che ci sarebbe un problema con il "rendimento"? costruire?
Qualcuno può suggerire una soluzione alternativa?
Soluzione
La logica è inesorabile! IEnumerable non supporta Clone e hai bisogno di Clone , quindi non dovresti usare IEnumerable .
O più precisamente, non dovresti usarlo come base fondamentale per lavorare su un interprete Scheme. Perché non creare invece un banale elenco di link immutabili?
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;
}
}
Nota che il metodo ToEnumerable ti dà un comodo utilizzo nel modo standard C #.
Per rispondere alla tua domanda:
Qualcuno può suggerire un realistico, utile, esempio di IEnumerable oggetto che non sarebbe in grado di fornire un " Clone () " efficiente metodo? È che ci sarebbe un problema con il "rendimento" costruire?
Un IEnumerable può andare in qualsiasi parte del mondo per i suoi dati. Ecco un esempio che legge le righe dalla console:
IEnumerable<string> GetConsoleLines()
{
for (; ;)
yield return Console.ReadLine();
}
Esistono due problemi: in primo luogo, una funzione Clone non sarebbe particolarmente semplice da scrivere (e Ripristina non avrebbe senso). In secondo luogo, la sequenza è infinita, il che è perfettamente ammissibile. Le sequenze sono pigre.
Un altro esempio:
IEnumerable<int> GetIntegers()
{
for (int n = 0; ; n++)
yield return n;
}
Per entrambi questi esempi, la "soluzione alternativa" hai accettato non sarebbe molto utile, perché esaurirebbe solo la memoria disponibile o riattaccerebbe per sempre. Ma questi sono esempi perfettamente validi di sequenze.
Per comprendere le sequenze C # e F #, è necessario esaminare gli elenchi in Haskell, non gli elenchi in Scheme.
Nel caso in cui pensi che l'infinito sia un'aringa rossa, che ne dici di leggere i byte da 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];
}
}
Se c'è un numero di byte inviati nel socket, questa non sarà una sequenza infinita. Eppure scrivere Clone per questo sarebbe molto difficile. In che modo il compilatore genererebbe l'implementazione IEnumerable per farlo automaticamente?
Non appena è stato creato un clone, entrambe le istanze dovrebbero ora funzionare da un sistema buffer condiviso. È possibile, ma in pratica non è necessario: non è così che questi tipi di sequenze sono progettati per essere utilizzati. Li tratti in modo puramente "funzionalmente", come valori, applicando i filtri in modo ricorsivo, piuttosto che "imperativamente" ricordando una posizione all'interno della sequenza. È un po 'più pulito della manipolazione di auto / cdr di basso livello.
Ulteriore domanda:
Mi chiedo qual è il livello più basso & Quot; primitivo (s) " Ne avrei bisogno qualsiasi cosa potrei voler fare con un IEnumerable nel mio interprete Scheme potrebbe essere implementato in schema piuttosto che come incorporato.
La risposta breve che penso sarebbe quella di guardare in Abelson e Sussman e in particolare la parte sui flussi . IEnumerable è uno stream, non un elenco. Descrivono come sono necessarie versioni speciali di mappa, filtro, accumulo, ecc. Per lavorare con loro. Vengono anche presi in considerazione l'idea di unificare elenchi e flussi nella sezione 4.2.
Altri suggerimenti
Come soluzione alternativa, potresti facilmente creare un metodo di estensione per IEnumerator che ha fatto la tua clonazione. Basta creare un elenco dall'enumeratore e utilizzare gli elementi come membri.
Perderesti le capacità di streaming di un enumeratore, poiché sei nuovo " clone " farebbe valutare completamente il primo enumeratore.
Se puoi lasciare andare l'enumeratore originale, ad es. non utilizzarlo più, puoi implementare un " clone " funzione che accetta l'enumeratore originale e lo utilizza come origine per uno o più enumeratori.
In altre parole, potresti costruire qualcosa del genere:
IEnumerable<String> original = GetOriginalEnumerable();
IEnumerator<String>[] newOnes = original.GetEnumerator().AlmostClone(2);
^- extension method
produce 2
new enumerators
Questi potrebbero condividere internamente l'enumeratore originale e un elenco collegato, per tenere traccia dei valori enumerati.
Ciò consentirebbe:
- Sequenze infinite, a condizione che entrambi gli enumeratori procedano in avanti (l'elenco collegato verrà scritto in modo tale che una volta che entrambi gli enumeratori abbiano superato un punto specifico, questi possano essere classificati in GC)
- Lazy enumeration, il primo dei due enumeratori che necessitano di un valore che non è stato ancora recuperato dall'enumeratore originale, lo otterrebbe e lo memorizzerebbe nell'elenco collegato prima di produrlo
Il problema qui è ovviamente che richiederebbe ancora molta memoria se uno degli enumeratori si sposta molto più avanti dell'altro.
Ecco il codice sorgente. Se si utilizza Subversion, è possibile scaricare il file della soluzione di Visual Studio 2008 con una libreria di classi con il codice seguente, nonché un oggetto test unit separato.
Repository: http://vkarlsen.serveftp.com:81/svnStackOverflow/SO847655
Nome utente e password sono entrambi "guest", senza virgolette.
Nota che questo codice non è affatto thread-safe.
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();
}
}
Questo utilizza la riflessione per creare una nuova istanza e quindi imposta i valori sulla nuova istanza. Ho anche trovato molto utile questo capitolo di C # in Depth. Dettagli sull'implementazione del blocco di iteratori: macchine a stati generate automaticamente
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;
}
}
Questa risposta è stata utilizzata anche sulla seguente domanda È possibile clonare un'istanza IEnumerable, salvando una copia dello stato di iterazione?
Perché non come metodo di estensione:
public static IEnumerator<T> Clone(this IEnumerator<T> original)
{
foreach(var v in original)
yield return v;
}
Questo fondamentalmente creerebbe e restituire un nuovo enumeratore senza valutare completamente l'originale.
Modifica: Sì, ho letto male. Paul ha ragione, funzionerebbe solo con IEnumerable.
Questo potrebbe aiutare. Ha bisogno di un po 'di codice per chiamare Dispose () su 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();
}
Lo scopo di " clonabile " gli enumeratori devono principalmente essere in grado di salvare la posizione dell'iterazione ed essere in grado di ritornarci in un secondo momento. Ciò significa che il contenitore iterato deve fornire un'interfaccia più ricca rispetto a IEnumerable . In realtà è qualcosa tra IEnumerable e IList . Lavorando con IList puoi semplicemente usare l'indice intero come enumeratore o creare una semplice classe di wrapping immutabile, con un riferimento all'elenco e alla posizione corrente.
Se il tuo contenitore non supporta l'accesso casuale e può essere iterato solo in avanti (come un elenco di collegamenti unidirezionali), deve almeno fornire la possibilità di ottenere l'elemento successivo, avendo un riferimento a quello precedente o ad alcune "iterazioni stato " che puoi tenere nel tuo iteratore. Quindi, l'interfaccia può apparire così:
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; }
}
Nota che l'iteratore è immutabile , non può essere "spostato in avanti", possiamo solo chiedere al nostro contenitore iterabile di darci un nuovo iteratore che punta alla posizione successiva. Il vantaggio è che puoi memorizzare iteratori ovunque tu ne abbia bisogno, ad esempio avere una pila di iteratori e tornare alla posizione precedentemente salvata quando necessario. Puoi salvare la posizione corrente per un uso successivo assegnando a una variabile, proprio come faresti con un indice intero.
La proprietà AllRest può essere utile se è necessario eseguire l'iterazione dalla posizione specificata alla fine del contenitore utilizzando le funzionalità di iterazione del linguaggio standard, come foraech o LinQ. Non cambierà la posizione dell'iteratore (ricorda, il nostro iteratore è immutabile). L'implementazione può ripetutamente GetNext e yleid return .
Il metodo GetNext può effettivamente far parte dell'iteratore stesso, in questo modo:
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; }
}
Questo è praticamente lo stesso. La logica per determinare lo stato successivo viene appena spostata dall'implementazione del contenitore all'iteratore implementazione. Nota che l'iteratore è ancora immutabile . Non puoi " spostarlo in avanti " puoi ottenerne solo un altro, indicando l'elemento successivo.
Esiste già un modo per creare un nuovo enumeratore, allo stesso modo in cui è stato creato il primo: IEnumerable.GetEnumerator. Non sono sicuro del motivo per cui hai bisogno di un altro meccanismo per fare la stessa cosa.
E nello spirito del Principio DRY , sono curioso di sapere perché vorresti duplicare la responsabilità della creazione di nuove istanze di IEnumerator nelle classi enumerabile e enumeratore. Dovresti forzare l'enumeratore a mantenere uno stato aggiuntivo oltre a quanto richiesto.
Ad esempio, immagina un enumeratore per un elenco collegato. Per l'implementazione di base di IEnumerable, quella classe dovrebbe solo mantenere un riferimento al nodo corrente. Ma per supportare il tuo clone, dovrebbe anche tenere un riferimento al capo della lista - qualcosa per il quale altrimenti non serve *. Perché dovresti aggiungere quello stato extra all'enumeratore, quando puoi semplicemente andare all'origine (l'IEnumerable) e ottenere un altro enumeratore?
E perché dovresti raddoppiare il numero di percorsi di codice che devi testare? Ogni volta che crei un nuovo modo di fabbricare un oggetto, aggiungi complessità.
* Avresti anche bisogno del puntatore head se hai implementato Reset, ma secondo i documenti , Reset è lì solo per l'interoperabilità COM e sei libero di lanciare NotSupportedException.
