Twórz partie w linq

Czy ktoś może zasugerować sposób tworzenia partii o określonym rozmiarze w linq?

Idealnie chciałbym móc wykonywać operacje na fragmentach o określonej konfigurowalnej ilości.

Nie musisz pisać żadnego kodu. Użyj metody MoreLINQ Batch, która grupuje sekwencję źródłową w zasobniki o rozmiarach (MoreLINQ jest dostępny jako pakiet NuGet, który można zainstalować):

int size = 10;
var batches = sequence.Batch(size);

Który jest realizowany jako:

public static IEnumerable<IEnumerable<TSource>> Batch<TSource>(
                  this IEnumerable<TSource> source, int size)
{
    TSource[] bucket = null;
    var count = 0;

    foreach (var item in source)
    {
        if (bucket == null)
            bucket = new TSource[size];

        bucket[count++] = item;
        if (count != size)
            continue;

        yield return bucket;

        bucket = null;
        count = 0;
    }

    if (bucket != null && count > 0)
        yield return bucket.Take(count).ToArray();
}

public static class MyExtensions
{
    public static IEnumerable<IEnumerable<T>> Batch<T>(this IEnumerable<T> items,
                                                       int maxItems)
    {
        return items.Select((item, inx) => new { item, inx })
                    .GroupBy(x => x.inx / maxItems)
                    .Select(g => g.Select(x => x.item));
    }
}

a użycie byłoby następujące:

List<int> list = new List<int>() { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

foreach(var batch in list.Batch(3))
{
    Console.WriteLine(String.Join(",",batch));
}

WYNIK:

0,1,2
3,4,5
6,7,8
9

Jeśli zaczynasz od sequencezdefiniowanego jako an IEnumerable<T>i wiesz, że można go bezpiecznie wyliczyć wiele razy (np. Ponieważ jest to tablica lub lista), możesz po prostu użyć tego prostego wzorca do przetwarzania elementów w partiach:

while (sequence.Any())
{
    var batch = sequence.Take(10);
    sequence = sequence.Skip(10);

    // do whatever you need to do with each batch here
}

Wszystkie powyższe działają strasznie przy dużych partiach lub małej ilości pamięci. Musiałem napisać własny, który będzie pipeline (nie zauważaj nigdzie gromadzenia się przedmiotów):

public static class BatchLinq {
    public static IEnumerable<IEnumerable<T>> Batch<T>(this IEnumerable<T> source, int size) {
        if (size <= 0)
            throw new ArgumentOutOfRangeException("size", "Must be greater than zero.");

        using (IEnumerator<T> enumerator = source.GetEnumerator())
            while (enumerator.MoveNext())
                yield return TakeIEnumerator(enumerator, size);
    }

    private static IEnumerable<T> TakeIEnumerator<T>(IEnumerator<T> source, int size) {
        int i = 0;
        do
            yield return source.Current;
        while (++i < size && source.MoveNext());
    }
}

Edycja: Znanym problemem związanym z tym podejściem jest to, że każda partia musi zostać w pełni wyliczona i wyliczona przed przejściem do następnej partii. Na przykład to nie działa:

//Select first item of every 100 items
Batch(list, 100).Select(b => b.First())

Jest to w pełni leniwa, niskobudżetowa, jednofunkcyjna implementacja usługi Batch, która nie wykonuje żadnej akumulacji. Na podstawie (i rozwiązuje problemy) rozwiązania Nicka Whaleya z pomocą EricRoller.

Iteracja pochodzi bezpośrednio z bazowego IEnumerable, więc elementy muszą być wyliczane w ścisłej kolejności i dostępne nie więcej niż raz. Jeśli niektóre elementy nie są zużywane w pętli wewnętrznej, są odrzucane (a próba ponownego dostępu do nich za pomocą zapisanego iteratora spowoduje wyświetlenie InvalidOperationException: Enumeration already finished.).

Możesz przetestować pełną próbkę w .NET Fiddle .

public static class BatchLinq
{
    public static IEnumerable<IEnumerable<T>> Batch<T>(this IEnumerable<T> source, int size)
    {
        if (size <= 0)
            throw new ArgumentOutOfRangeException("size", "Must be greater than zero.");
        using (var enumerator = source.GetEnumerator())
            while (enumerator.MoveNext())
            {
                int i = 0;
                // Batch is a local function closing over `i` and `enumerator` that
                // executes the inner batch enumeration
                IEnumerable<T> Batch()
                {
                    do yield return enumerator.Current;
                    while (++i < size && enumerator.MoveNext());
                }

                yield return Batch();
                while (++i < size && enumerator.MoveNext()); // discard skipped items
            }
    }
}

Zastanawiam się, dlaczego nikt nigdy nie opublikował starej szkoły rozwiązania pętli for. Tutaj jest jeden:

List<int> source = Enumerable.Range(1,23).ToList();
int batchsize = 10;
for (int i = 0; i < source.Count; i+= batchsize)
{
    var batch = source.Skip(i).Take(batchsize);
}

Ta prostota jest możliwa, ponieważ metoda Take:

... wylicza sourcei zwraca elementy, dopóki countelementy nie zostaną zwrócone lub sourcenie zawierają więcej elementów. Jeśli countprzekroczy liczbę elementów w source, sourcezwracane są wszystkie elementy

Zrzeczenie się:

Korzystanie z opcji Skip and Take w pętli oznacza, że ​​wyliczalne będą wyliczane wiele razy. Jest to niebezpieczne, jeśli wyliczalne jest odroczone. Może to spowodować wielokrotne wykonanie zapytania do bazy danych, żądania internetowego lub odczytu pliku. Ten przykład wyraźnie dotyczy użycia listy, która nie jest odroczona, więc stanowi mniejszy problem. Jest to nadal powolne rozwiązanie, ponieważ skip wylicza kolekcję za każdym razem, gdy jest wywoływana.

Można to również rozwiązać za pomocą tej GetRangemetody, ale wymaga to dodatkowych obliczeń, aby wyodrębnić ewentualną pozostałą partię:

for (int i = 0; i < source.Count; i += batchsize)
{
    int remaining = source.Count - i;
    var batch = remaining > batchsize  ? source.GetRange(i, batchsize) : source.GetRange(i, remaining);
}

Oto trzeci sposób rozwiązania tego problemu, który działa z 2 pętlami. Dzięki temu kolekcja zostanie wyliczona tylko 1 raz !:

int batchsize = 10;
List<int> batch = new List<int>(batchsize);

for (int i = 0; i < source.Count; i += batchsize)
{
    // calculated the remaining items to avoid an OutOfRangeException
    batchsize = source.Count - i > batchsize ? batchsize : source.Count - i;
    for (int j = i; j < i + batchsize; j++)
    {
        batch.Add(source[j]);
    }           
    batch.Clear();
}

To samo podejście co MoreLINQ, ale używa List zamiast Array. Nie robiłem testów porównawczych, ale czytelność ma dla niektórych większe znaczenie:

    public static IEnumerable<IEnumerable<T>> Batch<T>(this IEnumerable<T> source, int size)
    {
        List<T> batch = new List<T>();

        foreach (var item in source)
        {
            batch.Add(item);

            if (batch.Count >= size)
            {
                yield return batch;
                batch.Clear();
            }
        }

        if (batch.Count > 0)
        {
            yield return batch;
        }
    }

Oto próba ulepszenia leniwych implementacji Nicka Whaleya ( link ) i infogulch ( link ) Batch. Ten jest surowy. Możesz wyliczyć partie w odpowiedniej kolejności lub otrzymasz wyjątek.

public static IEnumerable<IEnumerable<TSource>> Batch<TSource>(
    this IEnumerable<TSource> source, int size)
{
    if (size <= 0) throw new ArgumentOutOfRangeException(nameof(size));
    using (var enumerator = source.GetEnumerator())
    {
        int i = 0;
        while (enumerator.MoveNext())
        {
            if (i % size != 0) throw new InvalidOperationException(
                "The enumeration is out of order.");
            i++;
            yield return GetBatch();
        }
        IEnumerable<TSource> GetBatch()
        {
            while (true)
            {
                yield return enumerator.Current;
                if (i % size == 0 || !enumerator.MoveNext()) break;
                i++;
            }
        }
    }
}

A oto leniwa Batchimplementacja dla źródeł typu IList<T>. Ten nie nakłada żadnych ograniczeń na wyliczenie. Partie można wyliczyć częściowo, w dowolnej kolejności i więcej niż raz. Jednak nadal obowiązuje ograniczenie dotyczące nie modyfikowania kolekcji podczas wyliczania. Osiąga się to, wykonując fikcyjne wywołanie enumerator.MoveNext()przed uzyskaniem dowolnego fragmentu lub elementu. Wadą jest to, że moduł wyliczający pozostaje niewykorzystany, ponieważ nie wiadomo, kiedy wyliczenie się zakończy.

public static IEnumerable<IEnumerable<TSource>> Batch<TSource>(
    this IList<TSource> source, int size)
{
    if (size <= 0) throw new ArgumentOutOfRangeException(nameof(size));
    var enumerator = source.GetEnumerator();
    for (int i = 0; i < source.Count; i += size)
    {
        enumerator.MoveNext();
        yield return GetChunk(i, Math.Min(i + size, source.Count));
    }
    IEnumerable<TSource> GetChunk(int from, int toExclusive)
    {
        for (int j = from; j < toExclusive; j++)
        {
            enumerator.MoveNext();
            yield return source[j];
        }
    }
}

Dołączam do tego bardzo późno, ale znalazłem coś bardziej interesującego.

Więc możemy użyć tutaj Skipi Takedla lepszej wydajności.

public static class MyExtensions
    {
        public static IEnumerable<IEnumerable<T>> Batch<T>(this IEnumerable<T> items, int maxItems)
        {
            return items.Select((item, index) => new { item, index })
                        .GroupBy(x => x.index / maxItems)
                        .Select(g => g.Select(x => x.item));
        }

        public static IEnumerable<T> Batch2<T>(this IEnumerable<T> items, int skip, int take)
        {
            return items.Skip(skip).Take(take);
        }

    }

Następnie sprawdziłem ze 100000 rekordami. Tylko zapętlenie zajmuje więcej czasu w przypadkuBatch

Kod aplikacji konsolowej.

static void Main(string[] args)
{
    List<string> Ids = GetData("First");
    List<string> Ids2 = GetData("tsriF");

    Stopwatch FirstWatch = new Stopwatch();
    FirstWatch.Start();
    foreach (var batch in Ids2.Batch(5000))
    {
        // Console.WriteLine("Batch Ouput:= " + string.Join(",", batch));
    }
    FirstWatch.Stop();
    Console.WriteLine("Done Processing time taken:= "+ FirstWatch.Elapsed.ToString());


    Stopwatch Second = new Stopwatch();

    Second.Start();
    int Length = Ids2.Count;
    int StartIndex = 0;
    int BatchSize = 5000;
    while (Length > 0)
    {
        var SecBatch = Ids2.Batch2(StartIndex, BatchSize);
        // Console.WriteLine("Second Batch Ouput:= " + string.Join(",", SecBatch));
        Length = Length - BatchSize;
        StartIndex += BatchSize;
    }

    Second.Stop();
    Console.WriteLine("Done Processing time taken Second:= " + Second.Elapsed.ToString());
    Console.ReadKey();
}

static List<string> GetData(string name)
{
    List<string> Data = new List<string>();
    for (int i = 0; i < 100000; i++)
    {
        Data.Add(string.Format("{0} {1}", name, i.ToString()));
    }

    return Data;
}

Czas zajęty jest taki.

Pierwsza - 00: 00: 00.0708, 00: 00: 00.0660

Drugi (Take and Skip One) - 00: 00: 00.0008, 00: 00: 00.0008

Tak więc z funkcjonalnym kapeluszem wydaje się to trywialne ... ale w C # są pewne istotne wady.

prawdopodobnie zobaczysz to jako rozwinięcie IEnumerable (wygoogluj to i prawdopodobnie skończysz w niektórych dokumentach Haskell, ale mogą być jakieś rzeczy F # używające rozwijania, jeśli znasz F #, mruż oczy na dokumentach Haskell i sprawi, że sens).

Unfold jest powiązany z fold ("agregacja"), z wyjątkiem tego, że zamiast iteracji przez dane wejściowe IEnumerable, iteruje przez struktury danych wyjściowych (jest to podobna relacja między IEnumerable i IObservable, w rzeczywistości myślę, że IObservable implementuje "rozwijanie" o nazwie generuj. ..)

w każdym razie najpierw potrzebujesz metody rozwijania, myślę, że to działa (niestety ostatecznie wysadzi stos dla dużych "list" ... możesz to bezpiecznie napisać w F # używając yield! zamiast concat);

    static IEnumerable<T> Unfold<T, U>(Func<U, IEnumerable<Tuple<U, T>>> f, U seed)
    {
        var maybeNewSeedAndElement = f(seed);

        return maybeNewSeedAndElement.SelectMany(x => new[] { x.Item2 }.Concat(Unfold(f, x.Item1)));
    }

jest to trochę tępe, ponieważ C # nie implementuje niektórych rzeczy, które langauges funkcjonalne przyjmują za pewnik ... ale w zasadzie pobiera ziarno, a następnie generuje odpowiedź "Może" dla następnego elementu w IEnumerable i następnego ziarna (Może nie istnieje w C #, więc użyliśmy IEnumerable, aby go sfałszować) i konkatenujemy resztę odpowiedzi (nie mogę ręczyć za złożoność „O (n?)”).

Kiedy już to zrobisz;

    static IEnumerable<IEnumerable<T>> Batch<T>(IEnumerable<T> xs, int n)
    {
        return Unfold(ys =>
            {
                var head = ys.Take(n);
                var tail = ys.Skip(n);
                return head.Take(1).Select(_ => Tuple.Create(tail, head));
            },
            xs);
    }

wszystko wygląda całkiem czysto… bierzesz „n” elementów jako „następny” element w IEnumerable, a „ogon” to reszta nieprzetworzonej listy.

jeśli nie ma nic w głowie ... to koniec ... zwracasz „Nothing” (ale udaje pustego IEnumerable>) ... w przeciwnym razie zwracasz element head i tail do przetworzenia.

prawdopodobnie możesz to zrobić za pomocą IObservable, prawdopodobnie istnieje już metoda podobna do "Batch" i prawdopodobnie możesz jej użyć.

Jeśli ryzyko przepełnienia stosu powoduje obawy (prawdopodobnie powinno), to powinieneś zaimplementować w F # (i prawdopodobnie jest już jakaś biblioteka F # (FSharpX?)).

(Zrobiłem tylko podstawowe testy tego, więc mogą tam być dziwne błędy).

Napisałem niestandardową implementację IEnumerable, która działa bez linq i gwarantuje pojedyncze wyliczenie danych. Osiąga to również wszystko bez konieczności tworzenia list zapasowych lub tablic, które powodują eksplozje pamięci w dużych zestawach danych.

Oto kilka podstawowych testów:

    [Fact]
    public void ShouldPartition()
    {
        var ints = new List<int> {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        var data = ints.PartitionByMaxGroupSize(3);
        data.Count().Should().Be(4);

        data.Skip(0).First().Count().Should().Be(3);
        data.Skip(0).First().ToList()[0].Should().Be(0);
        data.Skip(0).First().ToList()[1].Should().Be(1);
        data.Skip(0).First().ToList()[2].Should().Be(2);

        data.Skip(1).First().Count().Should().Be(3);
        data.Skip(1).First().ToList()[0].Should().Be(3);
        data.Skip(1).First().ToList()[1].Should().Be(4);
        data.Skip(1).First().ToList()[2].Should().Be(5);

        data.Skip(2).First().Count().Should().Be(3);
        data.Skip(2).First().ToList()[0].Should().Be(6);
        data.Skip(2).First().ToList()[1].Should().Be(7);
        data.Skip(2).First().ToList()[2].Should().Be(8);

        data.Skip(3).First().Count().Should().Be(1);
        data.Skip(3).First().ToList()[0].Should().Be(9);
    }

Metoda rozszerzenia do partycjonowania danych.

/// <summary>
/// A set of extension methods for <see cref="IEnumerable{T}"/>. 
/// </summary>
public static class EnumerableExtender
{
    /// <summary>
    /// Splits an enumerable into chucks, by a maximum group size.
    /// </summary>
    /// <param name="source">The source to split</param>
    /// <param name="maxSize">The maximum number of items per group.</param>
    /// <typeparam name="T">The type of item to split</typeparam>
    /// <returns>A list of lists of the original items.</returns>
    public static IEnumerable<IEnumerable<T>> PartitionByMaxGroupSize<T>(this IEnumerable<T> source, int maxSize)
    {
        return new SplittingEnumerable<T>(source, maxSize);
    }
}

To jest klasa implementująca

    using System.Collections;
    using System.Collections.Generic;

    internal class SplittingEnumerable<T> : IEnumerable<IEnumerable<T>>
    {
        private readonly IEnumerable<T> backing;
        private readonly int maxSize;
        private bool hasCurrent;
        private T lastItem;

        public SplittingEnumerable(IEnumerable<T> backing, int maxSize)
        {
            this.backing = backing;
            this.maxSize = maxSize;
        }

        public IEnumerator<IEnumerable<T>> GetEnumerator()
        {
            return new Enumerator(this, this.backing.GetEnumerator());
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }

        private class Enumerator : IEnumerator<IEnumerable<T>>
        {
            private readonly SplittingEnumerable<T> parent;
            private readonly IEnumerator<T> backingEnumerator;
            private NextEnumerable current;

            public Enumerator(SplittingEnumerable<T> parent, IEnumerator<T> backingEnumerator)
            {
                this.parent = parent;
                this.backingEnumerator = backingEnumerator;
                this.parent.hasCurrent = this.backingEnumerator.MoveNext();
                if (this.parent.hasCurrent)
                {
                    this.parent.lastItem = this.backingEnumerator.Current;
                }
            }

            public bool MoveNext()
            {
                if (this.current == null)
                {
                    this.current = new NextEnumerable(this.parent, this.backingEnumerator);
                    return true;
                }
                else
                {
                    if (!this.current.IsComplete)
                    {
                        using (var enumerator = this.current.GetEnumerator())
                        {
                            while (enumerator.MoveNext())
                            {
                            }
                        }
                    }
                }

                if (!this.parent.hasCurrent)
                {
                    return false;
                }

                this.current = new NextEnumerable(this.parent, this.backingEnumerator);
                return true;
            }

            public void Reset()
            {
                throw new System.NotImplementedException();
            }

            public IEnumerable<T> Current
            {
                get { return this.current; }
            }

            object IEnumerator.Current
            {
                get { return this.Current; }
            }

            public void Dispose()
            {
            }
        }

        private class NextEnumerable : IEnumerable<T>
        {
            private readonly SplittingEnumerable<T> splitter;
            private readonly IEnumerator<T> backingEnumerator;
            private int currentSize;

            public NextEnumerable(SplittingEnumerable<T> splitter, IEnumerator<T> backingEnumerator)
            {
                this.splitter = splitter;
                this.backingEnumerator = backingEnumerator;
            }

            public bool IsComplete { get; private set; }

            public IEnumerator<T> GetEnumerator()
            {
                return new NextEnumerator(this.splitter, this, this.backingEnumerator);
            }

            IEnumerator IEnumerable.GetEnumerator()
            {
                return this.GetEnumerator();
            }

            private class NextEnumerator : IEnumerator<T>
            {
                private readonly SplittingEnumerable<T> splitter;
                private readonly NextEnumerable parent;
                private readonly IEnumerator<T> enumerator;
                private T currentItem;

                public NextEnumerator(SplittingEnumerable<T> splitter, NextEnumerable parent, IEnumerator<T> enumerator)
                {
                    this.splitter = splitter;
                    this.parent = parent;
                    this.enumerator = enumerator;
                }

                public bool MoveNext()
                {
                    this.parent.currentSize += 1;
                    this.currentItem = this.splitter.lastItem;
                    var hasCcurent = this.splitter.hasCurrent;

                    this.parent.IsComplete = this.parent.currentSize > this.splitter.maxSize;

                    if (this.parent.IsComplete)
                    {
                        return false;
                    }

                    if (hasCcurent)
                    {
                        var result = this.enumerator.MoveNext();

                        this.splitter.lastItem = this.enumerator.Current;
                        this.splitter.hasCurrent = result;
                    }

                    return hasCcurent;
                }

                public void Reset()
                {
                    throw new System.NotImplementedException();
                }

                public T Current
                {
                    get { return this.currentItem; }
                }

                object IEnumerator.Current
                {
                    get { return this.Current; }
                }

                public void Dispose()
                {
                }
            }
        }
    }

Wiem, że wszyscy używali skomplikowanych systemów do tej pracy i naprawdę nie rozumiem dlaczego. Take and skip pozwoli na wszystkie te operacje przy użyciu wspólnego wyboru z Func<TSource,Int32,TResult>funkcją transformacji. Lubić:

public IEnumerable<IEnumerable<T>> Buffer<T>(IEnumerable<T> source, int size)=>
    source.Select((item, index) => source.Skip(size * index).Take(size)).TakeWhile(bucket => bucket.Any());

Po prostu kolejna implementacja jednej linii. Działa nawet z pustą listą, w tym przypadku otrzymasz kolekcję partii o zerowym rozmiarze.

var aList = Enumerable.Range(1, 100).ToList(); //a given list
var size = 9; //the wanted batch size
//number of batches are: (aList.Count() + size - 1) / size;

var batches = Enumerable.Range(0, (aList.Count() + size - 1) / size).Select(i => aList.GetRange( i * size, Math.Min(size, aList.Count() - i * size)));

Assert.True(batches.Count() == 12);
Assert.AreEqual(batches.ToList().ElementAt(0), new List<int>() { 1, 2, 3, 4, 5, 6, 7, 8, 9 });
Assert.AreEqual(batches.ToList().ElementAt(1), new List<int>() { 10, 11, 12, 13, 14, 15, 16, 17, 18 });
Assert.AreEqual(batches.ToList().ElementAt(11), new List<int>() { 100 });

Innym sposobem jest użycie operatora Rx Buffer

//using System.Linq;
//using System.Reactive.Linq;
//using System.Reactive.Threading.Tasks;

var observableBatches = anAnumerable.ToObservable().Buffer(size);

var batches = aList.ToObservable().Buffer(size).ToList().ToTask().GetAwaiter().GetResult();

    static IEnumerable<IEnumerable<T>> TakeBatch<T>(IEnumerable<T> ts,int batchSize)
    {
        return from @group in ts.Select((x, i) => new { x, i }).ToLookup(xi => xi.i / batchSize)
               select @group.Select(xi => xi.x);
    }