c# - Buffering una consulta LINQ

.net ienumerable

Question

EDICIÓN FINAL :

He elegido la respuesta de Timothy pero si desea una implementación más sencilla que aproveche la declaración de rendimiento de C # verifique la respuesta de Eamon : https://stackoverflow.com/a/19825659/145757

Por defecto, las consultas LINQ se transmiten de forma perezosa .

ToArray / ToList proporciona un búfer completo, pero primero están ansiosos y, en segundo lugar, puede llevar bastante tiempo completar con una secuencia infinita.

¿Hay alguna manera de tener una combinación de ambos comportamientos: los valores de transmisión y almacenamiento en búfer sobre la marcha a medida que se generan, para que la siguiente consulta no active la generación de los elementos que ya se han consultado?

Aquí hay un caso de uso básico:

static IEnumerable<int> Numbers
{
    get
    {
        int i = -1;

        while (true)
        {
            Console.WriteLine("Generating {0}.", i + 1);
            yield return ++i;
        }
    }
}

static void Main(string[] args)
{
    IEnumerable<int> evenNumbers = Numbers.Where(i => i % 2 == 0);

    foreach (int n in evenNumbers)
    {
        Console.WriteLine("Reading {0}.", n);
        if (n == 10) break;
    }

    Console.WriteLine("==========");

    foreach (int n in evenNumbers)
    {
        Console.WriteLine("Reading {0}.", n);
        if (n == 10) break;
    }
}

Aquí está la salida:

Generating 0.
Reading 0.
Generating 1.
Generating 2.
Reading 2.
Generating 3.
Generating 4.
Reading 4.
Generating 5.
Generating 6.
Reading 6.
Generating 7.
Generating 8.
Reading 8.
Generating 9.
Generating 10.
Reading 10.
==========
Generating 0.
Reading 0.
Generating 1.
Generating 2.
Reading 2.
Generating 3.
Generating 4.
Reading 4.
Generating 5.
Generating 6.
Reading 6.
Generating 7.
Generating 8.
Reading 8.
Generating 9.
Generating 10.
Reading 10.

El código de generación se dispara 22 veces.

Me gustaría que se activara 11 veces, la primera vez que se enumera el enumerable.

Entonces la segunda iteración se beneficiaría de los valores ya generados.

Sería algo como:

IEnumerable<int> evenNumbers = Numbers.Where(i => i % 2 == 0).Buffer();

Para aquellos familiarizados con Rx es un comportamiento similar a un ReplaySubject .

Answer 1

Método de extensión IEnumerable<T>.Buffer()

public static EnumerableExtensions
{
    public static BufferEnumerable<T> Buffer(this IEnumerable<T> source)
    {
        return new BufferEnumerable<T>(source);
    }
}

public class BufferEnumerable<T> : IEnumerable<T>, IDisposable
{
    IEnumerator<T> source;
    List<T> buffer;
    public BufferEnumerable(IEnumerable<T> source)
    {
        this.source = source.GetEnumerator();
        this.buffer = new List<T>();
    }
    public IEnumerator<T> GetEnumerator()
    {
        return new BufferEnumerator<T>(source, buffer);
    }
    public void Dispose()
    {
        source.Dispose()
    }
}

public class BufferEnumerator<T> : IEnumerator<T>
{
    IEnumerator<T> source;
    List<T> buffer;
    int i = -1;
    public BufferEnumerator(IEnumerator<T> source, List<T> buffer)
    {
        this.source = source;
        this.buffer = buffer;
    }
    public T Current
    {
        get { return buffer[i]; }
    }
    public bool MoveNext()
    {
        i++;
        if (i < buffer.Count)
            return true;
        if (!source.MoveNext())
            return false;
        buffer.Add(source.Current);
        return true;
    }
    public void Reset()
    {
        i = -1;
    }
    public void Dispose()
    {
    }
}

Uso

using (var evenNumbers = Numbers.Where(i => i % 2 == 0).Buffer())
{
    ...
}

Comentarios

El punto clave aquí es que la IEnumerable<T> source dada como entrada al método Buffer solo tiene GetEnumerator llamado una vez, independientemente de cuántas veces se enumere el resultado de Buffer . Todos los enumeradores para el resultado de Buffer comparten el mismo enumerador de origen y la lista interna.

Answer 2

Aquí hay una implementación ''funcional'' incompleta pero compacta (no se han definido nuevos tipos).

El error es que no permite enumeración simultánea.

Descripción original: la primera función debería haber sido una lambda anónima dentro de la segunda, pero C # no permite el yield en las lambdas anónimas :

// put these in some extensions class

private static IEnumerable<T> EnumerateAndCache<T>(IEnumerator<T> enumerator, List<T> cache)
{
    while (enumerator.MoveNext())
    {
        var current = enumerator.Current;
        cache.Add(current);
        yield return current;
    }
}
public static IEnumerable<T> ToCachedEnumerable<T>(this IEnumerable<T> enumerable)
{
    var enumerator = enumerable.GetEnumerator();
    var cache = new List<T>();
    return cache.Concat(EnumerateAndCache(enumerator, cache));
}

Uso:

var enumerable = Numbers.ToCachedEnumerable();

Answer 3

Espero que esta respuesta combine la brevedad y claridad de la respuesta de Sinelaw y el apoyo a múltiples enumeraciones de la respuesta de Timothy :

public static IEnumerable<T> Cached<T>(this IEnumerable<T> enumerable) {
    return CachedImpl(enumerable.GetEnumerator(), new List<T>());
}

static IEnumerable<T> CachedImpl<T>(IEnumerator<T> source, List<T> buffer) {
    int pos=0;
    while(true) {
        if(pos == buffer.Count) 
            if (source.MoveNext()) 
                buffer.Add(source.Current); 
            else 
                yield break;
        yield return buffer[pos++];
    }
}

Las ideas clave son usar la sintaxis de yield return para hacer una implementación enumerable corta, pero aún necesita una máquina de estado para decidir si puede obtener el siguiente elemento del búfer, o si necesita verificar el enumerador subyacente.

Limitaciones: esto no hace ningún intento de ser seguro para subprocesos, ni elimina el enumerador subyacente (lo que, en general, es bastante difícil de hacer, ya que el enumerador no almacenado en caché subyacente debe permanecer sin estar dispuesto mientras se pueda usar cualquier enumerador en caché).

Answer 4

Por lo que sé, no hay una forma integrada de hacerlo, lo cual, ahora que lo mencionas, es un poco sorprendente (supongo que, dada la frecuencia con la que uno querría usar esta opción, probablemente no valía la pena). el esfuerzo necesario para analizar el código para asegurarse de que el generador proporcione exactamente la misma secuencia cada vez).

Sin embargo, puede implementarlo usted mismo. La forma más fácil sería en el sitio de la llamada, como

var evenNumbers = Numbers.Where(i => i % 2 == 0).
var startOfList = evenNumbers.Take(10).ToList();

// use startOfList instead of evenNumbers in the loop.

De manera más general y precisa, puede hacerlo en el generador: cree un List<int> cache y cada vez que genere un número nuevo, agréguelo al cache antes de yield return . Luego, cuando vuelvas a pasar, primero entrega todos los números en caché. P.ej

List<int> cachedEvenNumbers = new List<int>();
IEnumerable<int> EvenNumbers
{
  get
  {
    int i = -1;

    foreach(int cached in cachedEvenNumbers)
    {
      i = cached;
      yield return cached;
    }

    // Note: this while loop now starts from the last cached value
    while (true) 
    {
        Console.WriteLine("Generating {0}.", i + 1);
        yield return ++i;
    }
  }
}

Supongo que si piensas en esto lo suficiente, podrías llegar a una implementación general de un método de extensión IEnumerable<T>.Buffered() . De nuevo, el requisito es que la enumeración no cambie entre llamadas y la pregunta es si vale la pena.

Answer 5

Puede usar el tipo Microsoft.FSharp.Collections.LazyList<> del paquete de energía F # (sí, de C # sin F # instalado, ¡no hay problema!) Para esto. Está en el paquete FSPowerPack.Core.Community .

En particular, desea llamar a LazyListModule.ofSeq(...) que devuelve un LazyList<T> que implementa IEnumerable<T> y es perezoso y en caché.

En tu caso, el uso es solo una cuestión de ...

var evenNumbers = LazyListModule.ofSeq(Numbers.Where(i => i % 2 == 0));
var cachedEvenNumbers = LazyListModule.ofSeq(evenNumbers);

Aunque personalmente prefiero var en todos estos casos, tenga en cuenta que esto significa que el tipo de tiempo de compilación será más específico que solo IEnumerable<> - no es probable que esto sea un inconveniente. Otra ventaja de los tipos F # sin interfaz es que exponen algunas operaciones eficientes que no puede realizar de manera eficiente con IEnumerables simples, como LazyListModule.skip .

No estoy seguro de si LazyList es seguro para subprocesos, pero sospecho que lo es.

Otra alternativa señalada en los comentarios a continuación (si tiene instalado F #) es SeqModule.Cache (espacio de nombres Microsoft.FSharp.Collections , estará en el ensamblado GACed FSharp.Core.dll) que tiene el mismo comportamiento efectivo. Al igual que otros enumerables de .NET, Seq.cache no tiene un operador de cola (o salto) que puede encadenar eficientemente.

Seguro para subprocesos: a diferencia de otras soluciones a esta pregunta, Seq.cache es seguro para subprocesos en el sentido de que puede tener múltiples enumeradores ejecutándose en paralelo (cada enumerador no es seguro para subprocesos).

Rendimiento Hice un rápido punto de referencia, y la LazyList tiene al menos 4 veces más de sobrecarga que la variante SeqModule.Cache , que tiene al menos tres veces más de sobrecarga que las respuestas de implementación personalizada. Entonces, mientras que las variantes de F # funcionan, no son tan rápidas. Tenga en cuenta que 3-12 veces más lento aún no es muy lento en comparación con un enumerable que hace (por ejemplo) E / S o cualquier cálculo no trivial, por lo que probablemente esto no importe la mayor parte del tiempo, pero es bueno mantenerse mente.

TL; DR Si necesita un enumerable en caché eficiente y seguro para subprocesos, simplemente use SeqModule.Cache .

Answer 6

Sobre la base de la respuesta de Eamon anterior , aquí hay otra solución funcional (no hay nuevos tipos) que también funciona con la evaluación simultánea. Esto demuestra que un patrón general (iteración con estado compartido) subyace a este problema.

Primero definimos un método de ayuda muy general, que nos permite simular la función que falta de los iteradores anónimos en C # :

public static IEnumerable<T> Generate<T>(Func<Func<Tuple<T>>> generator)
{
    var tryGetNext = generator();
    while (true)
    {
        var result = tryGetNext();
        if (null == result)
        {
            yield break;
        }
        yield return result.Item1;
    }
}

Generar es como un agregador con estado. Acepta una función que devuelve el estado inicial y una función generadora que habría sido anónima con yield return en ella, si se permitiera en C #. El estado devuelto por initialize está destinado a ser por enumeración, mientras que el llamante puede mantener un estado más global (compartido entre todas las enumeraciones) para generar, por ejemplo, en las variables de cierre, como se muestra a continuación.

Ahora podemos usar esto para el problema "Enumerable en búfer":

public static IEnumerable<T> Cached<T>(IEnumerable<T> enumerable)
{
    var cache = new List<T>();
    var enumerator = enumerable.GetEnumerator();

    return Generate<T>(() =>
    {
        int pos = -1;
        return () => {
            pos += 1;
            if (pos < cache.Count())
            {
                return new Tuple<T>(cache[pos]);
            }
            if (enumerator.MoveNext())
            {
                cache.Add(enumerator.Current);
                return new Tuple<T>(enumerator.Current);
            }
            return null;
        };
    });
}

Answer 7

Gracias a Eamon Nerbonne y sinelaw por sus respuestas, ¡solo un par de retoques! En primer lugar, para liberar el enumerador cuando se completa. En segundo lugar, proteger el enumerador subyacente con un bloqueo para que el enumerable pueda usarse de forma segura en varios subprocesos.

// This is just the same as @sinelaw''s Generator but I didn''t like the name
public static IEnumerable<T> AnonymousIterator<T>(Func<Func<Tuple<T>>> generator)
{
    var tryGetNext = generator();
    while (true)
    {
        var result = tryGetNext();
        if (null == result)
        {
            yield break;
        }
        yield return result.Item1;
    }
}

// Cached/Buffered/Replay behaviour
public static IEnumerable<T> Buffer<T>(this IEnumerable<T> self)
{
    // Rows are stored here when they''ve been fetched once
    var cache = new List<T>();

    // This counter is thread-safe in that it is incremented after the item has been added to the list,
    // hence it will never give a false positive. It may give a false negative, but that falls through
    // to the code which takes the lock so it''s ok.
    var count = 0;

    // The enumerator is retained until it completes, then it is discarded.
    var enumerator = self.GetEnumerator();

    // This lock protects the enumerator only. The enumerable could be used on multiple threads
    // and the enumerator would then be shared among them, but enumerators are inherently not
    // thread-safe so a) we must protect that with a lock and b) we don''t need to try and be
    // thread-safe in our own enumerator
    var lockObject = new object();

    return AnonymousIterator<T>(() =>
    {
        int pos = -1;
        return () =>
        {
            pos += 1;
            if (pos < count)
            {
                return new Tuple<T>(cache[pos]);
            }
            // Only take the lock when we need to
            lock (lockObject)
            {
                // The counter could have been updated between the check above and this one,
                // so now we have the lock we must check again
                if (pos < count)
                {
                    return new Tuple<T>(cache[pos]);
                }

                // Enumerator is set to null when it has completed
                if (enumerator != null)
                {
                    if (enumerator.MoveNext())
                    {
                        cache.Add(enumerator.Current);
                        count += 1;
                        return new Tuple<T>(enumerator.Current);
                    }
                    else
                    {
                        enumerator = null;
                    }
                }
            }
        }
        return null;
    };
});

}