Por que não pode IEnumerator é ser clonado?
https://stackoverflow.com/questions/807991
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Na implementação de um interpretador BASIC Esquema em C # eu descobri, para meu horror, o seguinte problema:
IEnumerator não tem um método clone! (Ou mais precisamente, IEnumerable não pode fornecer-me com um recenseador "cloneable").
O que eu gostaria:
interface IEnumerator<T>
{
bool MoveNext();
T Current { get; }
void Reset();
// NEW!
IEnumerator<T> Clone();
}
Eu não pode vir até com uma implementação de IEnumerable que não seria capaz de fornecer um IEnumerator eficiente Cloneable (vetores, ligados listas, etc, tudo seria capaz de fornecer uma implementação trivial de Clone de IEnumerator (), conforme especificado acima .. . que seria mais fácil do que fornecer um método reset () de qualquer maneira!).
A ausência dos meios Clone método que qualquer expressão funcional / recursiva de enumerar sobre uma sequência não irá funcionar.
Isso também significa que não pode "perfeitamente" fazer se comportam de IEnumerable como "listas" Lisp (para o qual você usa carro / cdr para enumerar de forma recursiva). ou seja, a única Aplicação do "(cdr algum IEnumerable )" seria terrivelmente ineficiente.
alguém pode sugerir um realista, útil, exemplo de um objeto IEnumerable que não seria capaz de fornecer uma "Clone) (" método eficiente? Será que haveria um problema com a construção "rendimento"?
Alguém pode sugerir uma solução alternativa?
Solução
A lógica é inexorável! IEnumerable não suporta Clone, e você precisa Clone, para que você não deve estar usando IEnumerable.
Ou, mais precisamente, você não deve usá-lo como a base fundamental para o trabalho em um interpretador Scheme. Por que não fazer uma lista ligada imutável trivial vez?
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;
}
}
Note que o método ToEnumerable lhe dá uso conveniente no C # forma padrão.
Para responder à sua pergunta:
Alguém pode sugerir um realista, útil, exemplo de um IEnumerable objeto que não seria capaz de fornecer uma "Clone) (" método eficiente? Será que haveria um problema com a construção "rendimento"?
Um IEnumerable pode ir em qualquer lugar do mundo para seus dados. Aqui está um exemplo que lê linhas do console:
IEnumerable<string> GetConsoleLines()
{
for (; ;)
yield return Console.ReadLine();
}
Há dois problemas com isso: em primeiro lugar, uma função Clone não seria particularmente simples para escrever (e Reset seria sem sentido). Em segundo lugar, a sequência é infinita - o que é perfeitamente permissível. Sequências são preguiçosos.
Outro exemplo:
IEnumerable<int> GetIntegers()
{
for (int n = 0; ; n++)
yield return n;
}
Para estes dois exemplos, a "Solução" você aceitou não seria muito uso, pois seria apenas esgotar a memória disponível ou pendurar-se para sempre. Mas estes são exemplos perfeitamente válidas de sequências.
Para entender as sequências C # e F #, você precisa olhar para as listas em Haskell, e não listas em Scheme.
No caso de você acha que o material infinito é um arenque vermelho, que tal ler os bytes de um 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 houver algum número de bytes a ser enviado à tomada, esta não será uma sequência infinita. E, no entanto escrever Clone pois seria muito difícil. Como é que o compilador gerar a implementação IEnumerable para fazê-lo automaticamente?
Assim que havia um clone criado, ambas as instâncias teria agora a trabalhar a partir de um sistema tampão que compartilhavam. É possível, mas na prática não é necessária - não é assim que esses tipos de seqüências são projetados para ser usado. Você tratá-los puramente "funcional", como valores, aplicar filtros a elas de forma recursiva, em vez de "imperativa" recordação de um local dentro da seqüência. É um pouco mais limpo do que de baixo nível car / manipulação cdr.
Outras pergunta:
Eu me pergunto, qual é o nível mais baixo "Primitivo (s)" Eu precisaria de tal forma que qualquer coisa que eu poderia querer fazer com um IEnumerable no meu intérprete Scheme poderia ser implementada no esquema vez não como um builtin.
A resposta curta Eu acho que seria a de olhar em Abelson e Sussman e, em particular a parte sobre córregos . IEnumerable é um fluxo, não uma lista. E eles descrevem como você precisa versões especiais do mapa, filtro, se acumulam, etc, para trabalhar com eles. Eles também entrar na ideia de unificar as listas e córregos na secção 4.2.
Outras dicas
Como alternativa, você pode facilmente fazer um método de extensão para IEnumerator que fez a sua clonagem. Basta criar uma lista a partir do recenseador, e usar os elementos como membros.
Você iria perder as capacidades de streaming de um recenseador, embora -. Desde que você está nova "clone" faria com que o primeiro enumerador para avaliar completamente
Se você pode deixar o go recenseador original, ou seja. não usá-lo mais, você pode implementar uma função de "clone" que leva o recenseador original, e usa-lo como fonte para um ou mais entrevistadores.
Em outras palavras, você poderia construir algo como isto:
IEnumerable<String> original = GetOriginalEnumerable();
IEnumerator<String>[] newOnes = original.GetEnumerator().AlmostClone(2);
^- extension method
produce 2
new enumerators
Estes poderiam compartilhar internamente o enumerador original, e uma lista ligada, para acompanhar os valores enumerados.
Isto permitiria:
- sequências infinitas, desde que ambos os recenseadores progredir para a frente (a lista ligada seria escrito de tal forma que, uma vez ambos os entrevistadores passaram um ponto específico, estes podem ser GC'ed)
- preguiçoso enumeração, o primeiro dos dois entrevistadores que precisam de um valor que não tenha sido recuperado do recenseador original, mas, seria obtê-lo e armazená-lo na lista ligada antes de ceder-lo
O problema aqui é claro que ele ainda exigiria um monte de memória se um dos recenseadores mover muito à frente do outro.
Aqui está o código fonte. Se você usa o Subversion, você pode baixar o arquivo de solução Visual Studio 2008 com uma biblioteca de classe com o código a seguir, bem como um porject teste de unidade separada.
Repository: http://vkarlsen.serveftp.com:81/svnStackOverflow/SO847655
Nome de usuário e senha é tanto 'convidado', sem as aspas.
Note que este código não é thread-safe, em tudo.
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();
}
}
Este usa a reflexão para criar uma nova instância e, em seguida, define os valores na nova instância. Eu também encontrei este capítulo do C # em profundidade para ser muito útil. Iterator bloco detalhes de implementação: máquinas de estado geradas 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;
}
}
Esta resposta também foi usado sobre a seguinte questão é possível clonar uma instância IEnumerable, salvando uma cópia do estado iteração?
Por que não este como um método de extensão:
public static IEnumerator<T> Clone(this IEnumerator<T> original)
{
foreach(var v in original)
yield return v;
}
Este seria basicamente criar e retornar um novo enumerador sem avaliar totalmente o original.
Edit: Sim, eu descaracterizou. Paul está correto, este seria apenas o trabalho com IEnumerable.
Isto pode ajudar. Ele precisa de algum código para chamar o Dispose () no 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();
}
O objetivo da recenseadores "clonable" é principalmente para poder salvar posição iteração e ser capaz de retornar mais tarde. Isso significa que, o recipiente iterado deve fornecer interface mais rica do que apenas IEnumerable. É realmente algo entre IEnumerable e IList. Trabalhando com IList você pode apenas usar um inteiro índice como recenseador, ou criar uma classe de embrulho imutável simples, mantendo uma referência à lista e posição atual.
Se o recipiente não suporta acesso aleatório e só pode ser repetido para a frente (como unidirecional lista vinculada), ele deve pelo menos fornecer capacidade de obter próximo elemento, tendo uma referência ao anterior ou a algum "estado iteração "que você pode segurar em sua iterador. Assim, a interface pode ficar assim:
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; }
}
Note que o iterador é imutável , não pode ser "movido para a frente", só podemos pedir ao nosso recipiente iterable para nos dar um novo apontar iterador para a posição seguinte. O benefício disso é que você pode armazenar iterators em qualquer lugar, desde que você precisa, por exemplo, tem uma pilha de iteradores e retorno à posição salva anteriormente quando você precisar. Você pode salvar a posição atual para uso posterior, atribuindo a uma variável, assim como você faria com um índice inteiro.
A propriedade AllRest pode ser útil se você precisar iterar a partir da posição dada ao final do recipiente utilizando recursos de linguagem de iteração padrão, como foraech ou LinQ. Não vai mudar a posição do iterador (lembre-se, o nosso iterador é imutável). A implementação pode repetidamente GetNext e yleid return.
O método GetNext pode realmente ser uma parte do iterador em si, assim:
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; }
}
Este é praticamente o mesmo. A lógica de determinar o próximo estado é movido apenas a partir da implementação recipiente para o iterador implementação. Note-se que o iterador ainda é imutável . Você não pode "movê-lo para a frente", você só pode obter um outro, apontando para o próximo elemento.
Já existe uma maneira de criar um novo enumerador - da mesma forma que criou a primeira: IEnumerable.GetEnumerator. Eu não sei por que você precisa de outro mecanismo para fazer a mesma coisa.
E no espírito da DRY , estou curioso para saber por que você iria querer a responsabilidade de criar novas instâncias IEnumerator para ser duplicada em ambas as suas classes enumeráveis ??e seu enumerador. Você estaria forçando o enumerador para manter o estado adicional além do que é necessário.
Por exemplo, imagine um enumerador para uma lista ligada. Para a implementação básica de IEnumerable, essa classe só precisa manter uma referência para o nó atual. Mas, para apoiar o seu Clone, ele também precisa manter uma referência à cabeça da lista - algo que de outra forma não tem nenhum uso para *. Por que você adicionar esse estado extra ao recenseador, quando você pode simplesmente ir para a fonte (o IEnumerable) e começar outro enumerador?
E por que você dobrar o número de caminhos de código que você precisa para teste? Cada vez que fizer uma nova maneira de fabricar um objeto, você está adicionando complexidade.
* Você também precisa do ponteiro cabeça se você implementou Reset, mas acordo com os docs , reset é só lá para interoperabilidade, e você está livre para lançar um NotSupportedException.
