Pourquoi IEnumerator ne peut-il pas être cloné?
https://stackoverflow.com/questions/807991
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
En implémentant un interpréteur Scheme de base en C #, le problème suivant a été découvert à ma grande horreur:
IEnumerator n'a pas de méthode de clonage! (ou plus précisément, IEnumerable ne peut pas me fournir d’énumérateur "clonable").
Ce que je voudrais:
interface IEnumerator<T>
{
bool MoveNext();
T Current { get; }
void Reset();
// NEW!
IEnumerator<T> Clone();
}
Je ne peux pas proposer d'implémentation d'IEnumerable qui ne serait pas en mesure de fournir un IEnumerator clonable (vecteurs, listes chaînées, etc.), tous seraient en mesure de fournir une implémentation triviale de IEnumerator's Clone () comme spécifié ci-dessus. Ce serait plus facile que de fournir une méthode Reset () de toute façon!).
L'absence de la méthode Clone signifie qu'aucun idiome fonctionnel / récursif d'énumération sur une séquence ne fonctionnera.
Cela signifie également que je ne peux pas "de manière transparente". faire en sorte que IEnumerable se comporte comme des "listes" Lisp (pour lequel vous utilisez car / cdr pour énumérer récursivement). c’est-à-dire la seule implémentation de " (cdr some IEnumerable ) " serait terriblement inefficace.
Quelqu'un peut-il suggérer un exemple réaliste et utile d'objet IEnumerable qui ne serait pas en mesure de fournir un "Clone ()" efficace? méthode? Est-ce qu'il y aurait un problème avec le "rendement"? construire?
Quelqu'un peut-il suggérer une solution de contournement?
La solution
La logique est inexorable! IEnumerable ne prend pas en charge Clone et vous avez besoin de Clone . Par conséquent, vous ne devriez pas utiliser IEnumerable .
Ou plus exactement, vous ne devriez pas l'utiliser comme base fondamentale pour travailler sur un interpréteur Scheme. Pourquoi ne pas créer une liste chaînée immuable et triviale?
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;
}
}
Notez que la méthode ToEnumerable vous offre une utilisation pratique dans le mode standard C #.
Pour répondre à votre question:
Quelqu'un peut-il suggérer une approche réaliste, utile, exemple d'un IEnumerable objet qui ne serait pas capable de fournissez un " Clone () & efficace; méthode? Est-ce qu'il y aurait un problème avec le " rendement " construire?
Un IEnumerable peut aller n'importe où dans le monde pour ses données. Voici un exemple qui lit les lignes de la console:
IEnumerable<string> GetConsoleLines()
{
for (; ;)
yield return Console.ReadLine();
}
Cela pose deux problèmes: premièrement, une fonction Clone ne serait pas particulièrement simple à écrire (et Réinitialiser n'aurait aucun sens). Deuxièmement, la séquence est infinie - ce qui est parfaitement admissible. Les séquences sont paresseuses.
Autre exemple:
IEnumerable<int> GetIntegers()
{
for (int n = 0; ; n++)
yield return n;
}
Pour ces deux exemples, la "solution de contournement" vous avez accepté ne serait pas très utile, car cela épuiserait la mémoire disponible ou raccrocherait pour toujours. Mais ce sont des exemples de séquences parfaitement valables.
Pour comprendre les séquences C # et F #, vous devez consulter les listes dans Haskell et non les listes dans Scheme.
Si vous pensez que l'infini est un fil rouge, pourquoi ne pas lire les octets d'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 un certain nombre d'octets sont envoyés dans le socket, il ne s'agira pas d'une séquence infinie. Et pourtant, écrire pour Clone serait très difficile. Comment le compilateur générerait-il l'implémentation IEnumerable pour le faire automatiquement?
Dès qu’un clone a été créé, les deux instances doivent désormais fonctionner à partir d’un système de tampons qu’elles partagent. C'est possible, mais en pratique, ce n'est pas nécessaire - ce n'est pas ainsi que ces types de séquences sont conçus. Vous les traitez de manière purement "fonctionnellement", comme des valeurs, en leur appliquant des filtres de manière récursive, plutôt que "impérativement". se rappeler un emplacement dans la séquence. C'est un peu plus propre qu'une manipulation voiture / cdr à bas niveau.
Autre question:
Je me demande quel est le niveau le plus bas "primitive (s)" J'aurais besoin de tel que tout ce que je pourrais vouloir faire avec un IEnumerable dans mon interpréteur Scheme pourrait être mis en œuvre dans le régime plutôt que comme un intégré.
La réponse courte, à mon avis, serait de regarder dans Abelson et Sussman et en particulier la pièce sur les flux . IEnumerable est un flux, pas une liste. Et ils décrivent comment vous avez besoin de versions spéciales de map, filter, accumuler, etc. pour travailler avec eux. Ils abordent également l’idée d’unifier les listes et les flux dans la section 4.2.
Autres conseils
Comme solution de contournement, vous pouvez facilement créer une méthode d'extension pour IEnumerator qui effectue votre clonage. Créez simplement une liste à partir de l'énumérateur et utilisez les éléments en tant que membres.
Vous perdriez cependant les capacités de diffusion d'un énumérateur - puisque vous êtes un nouveau "clone". provoquerait une évaluation complète du premier énumérateur.
Si vous pouvez laisser l’énumérateur initial disparaître, c.-à-d. ne l'utilisez plus, vous pouvez implémenter un " clone " fonction qui prend l'énumérateur d'origine et l'utilise comme source pour un ou plusieurs énumérateurs.
En d'autres termes, vous pouvez construire quelque chose comme ceci:
IEnumerable<String> original = GetOriginalEnumerable();
IEnumerator<String>[] newOnes = original.GetEnumerator().AlmostClone(2);
^- extension method
produce 2
new enumerators
Ils pourraient partager en interne l'énumérateur d'origine et une liste chaînée pour suivre les valeurs énumérées.
Cela permettrait:
- Séquences infinies, tant que les deux énumérateurs progressent (la liste liée est écrite de manière à ce que, une fois que les deux énumérateurs ont passé un point spécifique, ceux-ci peuvent être modifiés par GC)
- Énumération différée, premier des deux énumérateurs nécessitant une valeur qui n'a pas encore été extraite de l'énumérateur d'origine, il l'obtiendrait et la stockerait dans la liste liée avant de la renvoyer
Le problème, c’est bien sûr qu’il faudrait tout de même beaucoup de mémoire si l’un des enquêteurs avait une longueur d’avance sur l'autre.
Voici le code source. Si vous utilisez Subversion, vous pouvez télécharger le fichier de solution Visual Studio 2008 avec une bibliothèque de classes avec le code ci-dessous, ainsi qu’un projet de test unitaire séparé.
Référentiel: http://vkarlsen.serveftp.com:81/svnStackOverflow/SO847655
Le nom d'utilisateur et le mot de passe sont 'guest', sans les guillemets.
Notez que ce code n'est pas compatible avec les threads.
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();
}
}
Ceci utilise la réflexion pour créer une nouvelle instance, puis définit les valeurs sur la nouvelle instance. J'ai également trouvé ce chapitre de C # in Depth très utile. Détails d'implémentation de bloc Iterator: machines d'état générées automatiquement
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;
}
}
Cette réponse a également été utilisée pour la question suivante Est-il possible de cloner une instance IEnumerable en enregistrant une copie de l'état d'itération?
Pourquoi pas comme méthode d'extension:
public static IEnumerator<T> Clone(this IEnumerator<T> original)
{
foreach(var v in original)
yield return v;
}
Ceci créerait et renverrait un nouvel énumérateur sans évaluer complètement l'original.
Edit: Oui, j'ai mal lu. Paul a raison, cela ne fonctionnerait qu'avec IEnumerable.
Cela pourrait aider. Il a besoin d’un peu de code pour appeler Dispose () sur le 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();
}
Le but de "clonable" les agents recenseurs sont principalement capables d’enregistrer la position d’itération et de pouvoir y revenir ultérieurement. Cela signifie que le conteneur itéré doit fournir une interface plus riche que simplement IEnumerable . C'est en fait quelque chose entre IEnumerable et IList . En utilisant IList , vous pouvez simplement utiliser un index entier comme énumérateur ou créer une simple classe de wrapping immuable, contenant une référence à la liste et à la position actuelle.
Si votre conteneur ne prend pas en charge l'accès aléatoire et qu'il ne peut être itéré que vers l'avant (comme une liste chaînée unidirectionnelle), il doit au moins permettre de passer à l'élément suivant, en faisant référence au précédent ou à une certaine "itération". état " que vous pouvez tenir dans votre itérateur. Ainsi, l'interface peut ressembler à ceci:
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; }
}
Notez que l'itérateur est immuable , il ne peut pas être "avancé", nous pouvons uniquement demander à notre conteneur itératif de nous fournir un nouvel itérateur indiquant la position suivante. L'avantage de cela est que vous pouvez stocker des itérateurs n'importe où, aussi longtemps que vous en avez besoin, par exemple une pile d'itérateurs et revenir à la position précédemment enregistrée lorsque vous en avez besoin. Vous pouvez enregistrer la position actuelle pour une utilisation ultérieure en affectant une variable, comme vous le feriez avec un index entier.
La propriété AllRest peut être utile si vous devez effectuer une itération de la position donnée à la fin du conteneur à l'aide de fonctions d'itération de langage standard, telles que foraech ou LinQ. Cela ne changera pas la position de l'itérateur (rappelez-vous, notre itérateur est immuable). L’implémentation peut à plusieurs reprises GetNext et yleid renvoyer .
La méthode GetNext peut en réalité faire partie de l'itérateur lui-même, comme ceci:
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; }
}
C'est à peu près la même chose. La logique de détermination du prochain état est simplement déplacée de l'implémentation du conteneur vers l'itérateur la mise en oeuvre. Notez que l'itérateur est toujours immuable . Vous ne pouvez pas "avancer", vous pouvez seulement en obtenir un autre, en pointant sur l'élément suivant.
Il existe déjà un moyen de créer un nouvel énumérateur - de la même manière que vous avez créé le premier: IEnumerable.GetEnumerator. Je ne sais pas pourquoi vous avez besoin d'un autre mécanisme pour faire la même chose.
Et dans l’esprit du Principe du DRY , je suis curieux de savoir pourquoi vous voudriez que la responsabilité de la création de nouvelles instances IEnumerator soit dupliquée à la fois dans vos classes énumérateur et énumérateur. Vous obligeriez l'énumérateur à conserver un état supplémentaire au-delà de ce qui est requis.
Par exemple, imaginez un énumérateur pour une liste chaînée. Pour l'implémentation de base d'IEnumerable, cette classe n'aurait besoin que de conserver une référence au nœud actuel. Toutefois, pour prendre en charge votre clone, il devrait également conserver une référence au début de la liste - un élément pour lequel il n’est pas utile autrement *. Pourquoi voudriez-vous ajouter cet état supplémentaire à l’énumérateur, alors que vous pouvez simplement aller à la source (le IEnumerable) et obtenir un autre énumérateur?
Et pourquoi voudriez-vous doubler le nombre de chemins de code que vous devez tester? Chaque fois que vous créez une nouvelle manière de fabriquer un objet, vous ajoutez de la complexité.
* Vous aurez également besoin du pointeur principal si vous implémentez la réinitialisation, mais en fonction de la documentation , la réinitialisation n’est là que pour l’interopérabilité COM et vous êtes libre de déclencher une exception NotSupportedException.
