Warum kann nicht IEnumerator die geklont werden?
https://stackoverflow.com/questions/807991
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
In einem Grund Scheme-Interpreter in C # Umsetzung entdeckte ich zu meinem Entsetzen, das folgende Problem:
IEnumerator keinen Klon-Methode! (Oder genauer gesagt, IEnumerable kann mich nicht bieten mit einem „klonbar“ enumerator).
Was ich möchte:
interface IEnumerator<T>
{
bool MoveNext();
T Current { get; }
void Reset();
// NEW!
IEnumerator<T> Clone();
}
Ich kann nicht mit einer Implementierung von IEnumerable kommen, die nicht in der Lage wäre, eine effizient klonbar IEnumerator (Vektoren, verkettete Listen zu liefern usw. alle eine triviale Implementierung der IEnumerator Clone () wie oben angegeben zu schaffen wäre in der Lage .. ., es wäre einfacher, als ohnehin ein Reset () Methode bietet!).
Das Fehlen der Clone-Methode bedeutet, dass jedes funktionelles / rekursive Idiom eine Folge von Aufzählen über nicht funktionieren.
Es bedeutet auch, kann ich nicht „nahtlos“ wie Lisp „Listen“ IEnumerable des behave machen (für die Sie Auto / cdr verwenden rekursiv aufzulisten). das heißt, die nur UMSETZUNG von "(cdr einige IEnumerable )" würde kläglich ineffizient sein.
Kann mir jemand eine realistische, nützlich, beispielsweise eines IEnumerable Objekt vorschlagen, die nicht in der Lage wäre, eine effiziente „Clone ()“ Verfahren zur Verfügung zu stellen? Ist es, dass es ein Problem mit der „Ausbeute“ würde konstruieren?
Kann jemand eine Abhilfe vorschlagen?
Lösung
Die Logik ist unerbittlich! IEnumerable nicht Clone unterstützen, und Sie müssen Clone, so dass Sie nicht mit IEnumerable sein sollte.
oder genauer gesagt, Sie sollten es nicht als grundlegende Basis für die Arbeit an einem Scheme-Interpreter werden. Warum nicht eine triviale unveränderlich verknüpfte Liste machen statt?
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;
}
}
Beachten Sie, dass die ToEnumerable Methode Sie die bequeme Nutzung in der Standard-C # nachgibt.
Um Ihre Frage zu beantworten:
Kann mir jemand eine realistische vorschlagen, nützlich, beispielsweise ein IEnumerable Objekt, das wäre nicht in der Lage sein bieten eine effiziente „Clone ()“ Methode? Ist es, dass es ein Problem sein würde mit die "Ausbeute" konstruieren?
Ein IEnumerable kann überall in der Welt für seine Daten gehen. Hier ist ein Beispiel, die Linien von der Konsole lautet:
IEnumerable<string> GetConsoleLines()
{
for (; ;)
yield return Console.ReadLine();
}
Es gibt zwei Probleme: Erstens würde eine Clone Funktion nicht besonders einfach sein, zu schreiben (und Reset wäre sinnlos). Zweitens ist die Folge unendlich - was durchaus zulässig ist. Sequenzen sind faul.
Ein weiteres Beispiel:
IEnumerable<int> GetIntegers()
{
for (int n = 0; ; n++)
yield return n;
}
Sowohl für diesen Beispielen wird die „Abhilfe“ Sie haben akzeptiert würde viel Einsatz nicht, weil es nur den verfügbaren Speicher für immer erschöpfen würde oder aufzuhängen. Aber diese sind absolut gültige Beispiele für Sequenzen.
C # und F # Sequenzen zu verstehen, müssen Sie auf Listen in Haskell suchen, keine Listen in Schema.
Falls Sie denken, Sie die unendlichen Sachen ein roter Hering sind, wie etwa das Bytes von einem Socket zu lesen:
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];
}
}
Wenn es eine bestimmte Anzahl von Bytes ist, die Buchse herabgesandt wird, wird dies nicht eine unendliche Folge sein. Und doch Clone schriftlich wäre es sehr schwierig sein. Wie würde die Compiler die IEnumerable Implementierung generiert automatisch zu tun?
Sobald ein Klon erstellt wurde, würden beide Instanzen müssen jetzt von einem Puffersystem arbeiten, die sie geteilt. Es ist möglich, aber in der Praxis ist es nicht benötigt wird - das ist nicht, wie diese Arten von Sequenzen genutzt werden sollen. Sie behandeln sie rein „funktional“, wie Werte, Filter, um sie rekursiv, sondern als „zwingend“ Erinnerung an einen Ort innerhalb der Sequenz anwenden. Es ist ein wenig sauberer als Low-Level-car / cdr Manipulation.
Weitere Frage:
Ich frage mich, was ist das niedrigste Niveau „Primitive (n)“ Ich würde benötigen, so dass alles, was ich kann mit einem tun will IEnumerable in meinem Scheme-Interpreter werden könnte eher in Schema implementiert als als builtin.
Die kurze Antwort, die ich denke, wäre in Abelson und Sussman und insbesondere der Teil über Ströme . IEnumerable ist ein Strom, keine Liste. Und sie beschreiben, wie Sie spezielle Versionen der Karte benötigen, Filter, akkumulieren usw. mit ihnen zu arbeiten. Sie erhalten auch auf die Idee der Vereinheitlichung Listen und Bäche in Abschnitt 4.2.
Andere Tipps
Als Abhilfe können Sie könnte leicht eine Erweiterungsmethode für IEnumerator machen, die Ihr Klonen tat. Erstellen Sie einfach eine Liste aus dem enumerator und verwenden Sie die Elemente als Mitglieder.
Sie würden die Streaming-Fähigkeiten eines Aufzählungs verlieren, obwohl - da Sie neue „Klon“ sind die erste enumerator würde dazu führen, vollständig zu bewerten
.Wenn Sie die ursprüngliche enumerator loslassen, dh. es nicht mehr verwenden Sie, können Sie einen „Klon“ Funktion implementieren, die die ursprüngliche enumerator nimmt, und verwendet sie als Quelle für einen oder mehrere Enumeratoren.
Mit anderen Worten, Sie so etwas wie diese bauen kann:
IEnumerable<String> original = GetOriginalEnumerable();
IEnumerator<String>[] newOnes = original.GetEnumerator().AlmostClone(2);
^- extension method
produce 2
new enumerators
Diese könnten die ursprüngliche enumerator intern teilen, und eine verknüpfte Liste, den Überblick über die aufgezählten Werte zu halten.
Dies würde erlauben:
- unendliche Folgen, solange beide Aufzählungen nach vorn Fortschritt (die verknüpfte Liste so geschrieben werden würde, dass, wenn beide Aufzählungen einen bestimmten Punkt passiert haben, können diejenigen GC'ed werden)
- Faule Aufzählung, die erste der beiden Aufzählungen, die einen Wert benötigen, die von der ursprünglichen enumerator abgerufen wurde noch nicht, es wäre es zu erhalten und speichern sie in der verknüpften Liste, bevor es Nachgeben
Problem hier ist natürlich, dass es noch viel Speicher benötigen würde, wenn einer der Enumeratoren weit vor den anderen zu bewegen.
Hier ist der Quellcode. Wenn Sie Subversion verwenden, können Sie die Visual Studio 2008-Lösung Datei mit einer Klassenbibliothek mit dem folgenden Code herunterladen, sowie eine separate Einheit Test porject.
Repository: http://vkarlsen.serveftp.com:81/svnStackOverflow/SO847655
Benutzername und Passwort ist sowohl ‚Gast‘, ohne Anführungszeichen.
Beachten Sie, dass dieser Code nicht Thread-sicher, überhaupt nicht.
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();
}
}
Dies nutzt Reflexion eine neue Instanz zu erstellen und legt dann die Werte auf die neue Instanz. Ich fand auch dieses Kapitel von C # in Depth sehr nützlich zu sein. Iteratorblock Implementierungsdetails: automatisch generierte Zustandsmaschinen
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;
}
}
Diese Antwort wurde auch über die folgende Frage: Ist es möglich, eine IEnumerable Instanz zu klonen, eine Kopie der Iteration Zustand zu speichern?
Warum dies nicht als eine Erweiterung Methode:
public static IEnumerator<T> Clone(this IEnumerator<T> original)
{
foreach(var v in original)
yield return v;
}
Dies würde im Grunde erstellen und einen neuen Enumerator zurück, ohne das Original vollständig zu bewerten.
Edit: Ja, ich falsch verstanden. Paul korrekt ist, wäre dies nur mit IEnumerable arbeiten.
Dies könnte helfen. Es braucht einige Codes die Dispose () auf dem IEnumerator zu nennen:
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();
}
Der Zweck der „clonable“ Aufzählungen ist in erster Linie spart Iteration Position zu können und in der Lage, um es später zurückzukehren. Das heißt, muss der iterierten Behälter reicher Schnittstelle bietet als nur IEnumerable. Es ist tatsächlich etwas zwischen IEnumerable und IList. mit IList arbeiten, können Sie nur Integer-Index als Enumerator verwenden, oder eine einfache unveränderliche Wickel Klasse erstellen, einen Verweis auf die Liste und die aktuelle Position zu halten.
Wenn Ihr Behälter nicht zufällig Zugriff nicht unterstützt und kann nur vorwärts durchlaufen werden (wie unidirektionale verkettete Liste), muss sie zumindest vor, Fähigkeit nächstes Element zu erhalten, mit einem Verweise auf den vorherigen oder zu einem „Iteration Zustand "dass Sie in Ihrem Iterator zu halten. So kann die Schnittstelle wie folgt aussehen:
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; }
}
Beachten Sie, dass der Iterator ist unveränderlich , kann es nicht sein „vorwärts bewegt“, wir können nur unser iterable Container fragen Sie uns einen neuen Iterator zur nächsten Position zeigen zu geben. Der Vorteil davon ist, dass Sie Iteratoren überall speichern können, so lange, wie Sie benötigen, zum Beispiel einen Stapel von Iteratoren haben und zuvor gespeicherte Position zurück, wenn Sie benötigen. Sie können durch die Zuordnung zu einer Variablen aktuelle Position für die spätere Verwendung speichern, wie Sie mit einem ganzzahligen Index tun würden.
Die AllRest Eigenschaft kann nützlich sein, wenn Sie von der angegebenen Position bis zum Ende des Behälters unter Verwendung von Standardsprache Iteration Features, wie foraech oder LinQ laufen müssen. Es wird nicht die Iterator Position (denken Sie daran, unser Iterator unveränderlich ist) ändern. Die Implementierung kann wiederholt GetNext und yleid return.
Die GetNext Methode kann tatsächlich ein Teil von Iterator selbst, wie folgt aus:
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; }
}
Das ist so ziemlich das gleiche. Die Logik des nächsten Zustandsbestimmungs nur von dem Behälter zu der Umsetzung Iterator bewegt Implementierung. Beachten Sie, dass der Iterator ist noch unveränderlich . Sie können nicht „es vorwärts bewegen“, können Sie nur noch einen bekommen, auf das nächste Element zeigt.
Es ist schon eine Möglichkeit, eine neue enumerator zu schaffen - die gleiche Art und Weise erstellt, um Sie die ersten: IEnumerable.GetEnumerator. Ich bin mir nicht sicher, warum Sie einen anderen Mechanismus müssen die gleiche Sache zu tun.
Und im Geist des DRY-Prinzip , ich bin neugierig, warum Sie die Verantwortung für die Schaffung neuer IEnumerator Instanzen wollen würde, sowohl in Ihrer enumerable und Ihre enumerator Klassen dupliziert werden. Sie würden die enumerator werden zwingen über zusätzlichen Zustand zu halten, was erforderlich ist.
Zum Beispiel vorstellen, einen Enumerator für eine verkettete Liste. Für die grundlegende Implementierung von IEnumerable, würde diese Klasse nur einen Verweis auf den aktuellen Knoten halten müssen. Aber Ihr Klon zu unterstützen, wäre es auch einen Verweis auf den Kopf der Liste halten müssen - etwas, das es hat sonst keine Verwendung für *. Warum würden Sie, dass zusätzliche Zustand in den enumerator hinzufügen, wenn Sie nur an die Quelle gehen kann (die IEnumerable) und ein anderes Aufzählungs bekommen?
Und warum sollten Sie verdoppeln die Anzahl der Codepfade Sie testen müssen? Jedes Mal, wenn Sie eine neue Art und Weise machen, ein Objekt herzustellen, das Sie hinzufügen Komplexität.
* Sie würde auch den Kopfzeiger benötigen, wenn Sie Zurücksetzen implementiert, aber nach dem docs , Reset ist nur dort für COM-Interop, und Sie sind frei, eine NotSupportedException zu werfen.
