Buat batch di linq

Dapatkah seseorang menyarankan cara untuk membuat kumpulan dengan ukuran tertentu di LINQ?

Idealnya, saya ingin dapat melakukan operasi dalam beberapa bagian yang dapat dikonfigurasi.

Anda tidak perlu menulis kode apa pun. Gunakan metode MoreLINQ Batch, yang mengelompokkan urutan sumber ke dalam bucket berukuran (MoreLINQ tersedia sebagai paket NuGet yang dapat Anda instal):

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

Yang diimplementasikan sebagai:

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));
    }
}

dan penggunaannya adalah:

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));
}

KELUARAN:

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

Jika Anda memulai dengan sequencedidefinisikan sebagai IEnumerable<T>, dan Anda tahu bahwa itu dapat dengan aman disebutkan beberapa kali (misalnya karena ini adalah larik atau daftar), Anda dapat menggunakan pola sederhana ini untuk memproses elemen dalam kelompok:

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

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

Semua hal di atas bekerja sangat buruk dengan batch besar atau ruang memori rendah. Harus menulis sendiri yang akan pipeline (perhatikan tidak ada akumulasi item di mana pun):

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());
    }
}

Sunting: Masalah yang diketahui dengan pendekatan ini adalah bahwa setiap batch harus dihitung dan dicacah sepenuhnya sebelum pindah ke batch berikutnya. Misalnya ini tidak berhasil:

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

Ini adalah implementasi Batch yang sepenuhnya malas, overhead rendah, dan satu fungsi yang tidak melakukan akumulasi apa pun. Berdasarkan (dan memperbaiki masalah dalam) solusi Nick Whaley dengan bantuan dari EricRoller.

Iterasi berasal langsung dari IEnumerable yang mendasarinya, sehingga elemen harus dihitung dalam urutan yang ketat, dan diakses tidak lebih dari sekali. Jika beberapa elemen tidak dikonsumsi dalam loop dalam, mereka akan dibuang (dan mencoba mengaksesnya lagi melalui iterator yang disimpan akan dilempar InvalidOperationException: Enumeration already finished.).

Anda dapat menguji sampel lengkap di .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
            }
    }
}

Saya bertanya-tanya mengapa tidak ada yang pernah memposting solusi loop-for-sekolah lama. Ini salah satunya:

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);
}

Kesederhanaan ini dimungkinkan karena metode Take:

... menghitung sourcedan menghasilkan elemen sampai countelemen telah dihasilkan atau sourcetidak mengandung elemen lagi. Jika countmelebihi jumlah elemen source, semua elemen sourcedikembalikan

Penolakan:

Menggunakan Skip dan Take inside the loop berarti enumerable akan dihitung beberapa kali. Ini berbahaya jika pencacahan ditunda. Ini dapat mengakibatkan beberapa eksekusi kueri database, atau permintaan web, atau file dibaca. Contoh ini secara eksplisit untuk penggunaan List yang tidak ditangguhkan, jadi ini bukan masalah. Ini masih merupakan solusi yang lambat karena lewati akan menghitung koleksi setiap kali dipanggil.

Ini juga dapat diselesaikan dengan menggunakan GetRangemetode ini, tetapi memerlukan perhitungan ekstra untuk mengekstrak kemungkinan tumpukan sisa:

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);
}

Berikut adalah cara ketiga untuk menangani ini, yang bekerja dengan 2 loop. Ini memastikan bahwa koleksi dihitung hanya 1 kali !:

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();
}

Pendekatan yang sama seperti MoreLINQ, tetapi menggunakan List, bukan Array. Saya belum melakukan pembandingan, tetapi keterbacaan lebih penting bagi sebagian orang:

    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;
        }
    }

Berikut ini adalah upaya peningkatan implementasi malas Nick Whaley ( tautan ) dan infogulch ( tautan ) Batch. Yang ini ketat. Anda bisa menghitung batch dalam urutan yang benar, atau Anda mendapatkan pengecualian.

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++;
            }
        }
    }
}

Dan berikut adalah Batchimplementasi malas untuk sumber tipe IList<T>. Yang satu ini tidak membatasi pencacahan. Batch dapat dihitung sebagian, dalam urutan apapun, dan lebih dari satu kali. Namun, larangan untuk tidak mengubah koleksi selama pencacahan masih berlaku. Ini dicapai dengan membuat panggilan tiruan ke enumerator.MoveNext()sebelum menghasilkan potongan atau elemen apa pun. Kelemahannya adalah bahwa pencacah dibiarkan tidak tergesa-gesa, karena tidak diketahui kapan pencacahan akan selesai.

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];
        }
    }
}

Saya bergabung ini sangat terlambat tetapi saya menemukan sesuatu yang lebih menarik.

Jadi kita bisa gunakan di sini Skipdan Takeuntuk performa yang lebih baik.

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);
        }

    }

Selanjutnya saya memeriksa dengan 100000 catatan. Perulangan hanya membutuhkan lebih banyak waktu jika terjadiBatch

Kode aplikasi konsol.

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;
}

Waktu yang dibutuhkan Seperti ini.

Pertama - 00: 00: 00.0708, 00: 00: 00.0660

Kedua (Ambil dan Lewati Satu) - 00: 00: 00.0008, 00: 00: 00.0008

Jadi dengan topi fungsional, ini tampak sepele .... tetapi di C #, ada beberapa kerugian yang signifikan.

Anda mungkin akan melihat ini sebagai terbukanya IEnumerable (google itu dan Anda mungkin akan berakhir di beberapa dokumen Haskell, tapi mungkin ada beberapa F # hal yang menggunakan terungkap, jika Anda tahu F #, julingkan di dokumen Haskell dan itu akan membuat merasakan).

Unfold terkait dengan lipat ("agregat") kecuali daripada iterasi melalui input IEnumerable, iterasi melalui struktur data keluaran (hubungan yang mirip antara IEnumerable dan IObservable, sebenarnya saya pikir IObservable tidak menerapkan "terungkap" yang disebut menghasilkan. ..)

Lagi pula pertama-tama Anda memerlukan metode terungkap, saya pikir ini berfungsi (sayangnya pada akhirnya akan meledakkan tumpukan untuk "daftar" besar ... Anda dapat menulis ini dengan aman di F # menggunakan yield! daripada 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)));
    }

ini agak tumpul karena C # tidak menerapkan beberapa hal yang dianggap bahasa fungsional begitu saja ... tetapi pada dasarnya mengambil sebuah seed dan kemudian menghasilkan jawaban "Mungkin" dari elemen berikutnya di IEnumerable dan seed berikutnya (Maybe tidak ada di C #, jadi kami telah menggunakan IEnumerable untuk memalsukannya), dan menggabungkan sisa jawaban (saya tidak dapat menjamin kompleksitas "O (n?)" dari ini).

Setelah Anda selesai melakukannya;

    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);
    }

semuanya terlihat cukup bersih ... Anda mengambil elemen "n" sebagai elemen "berikutnya" di IEnumerable, dan "tail" adalah sisa dari daftar yang belum diproses.

jika tidak ada apa-apa di kepala ... Anda selesai ... Anda mengembalikan "Tidak ada" (tetapi dipalsukan sebagai IEnumerable> kosong) ... jika tidak, Anda mengembalikan elemen kepala dan ekor untuk diproses.

Anda mungkin dapat melakukan ini menggunakan IObservable, mungkin ada metode seperti "Batch" yang sudah ada, dan Anda mungkin dapat menggunakannya.

Jika risiko stack overflows mengkhawatirkan (mungkin seharusnya), maka Anda harus menerapkan di F # (dan mungkin sudah ada beberapa library F # (FSharpX?) Dengan ini).

(Saya hanya melakukan beberapa tes dasar untuk ini, jadi mungkin ada bug aneh di sana).

Saya menulis implementasi IEnumerable kustom yang bekerja tanpa LINQ dan menjamin pencacahan tunggal atas data. Itu juga menyelesaikan semua ini tanpa memerlukan daftar dukungan atau array yang menyebabkan ledakan memori atas kumpulan data yang besar.

Berikut beberapa tes dasar:

    [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);
    }

Metode Ekstensi untuk mempartisi data.

/// <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);
    }
}

Ini adalah kelas pelaksana

    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()
                {
                }
            }
        }
    }

Saya tahu semua orang menggunakan sistem kompleks untuk melakukan pekerjaan ini, dan saya benar-benar tidak mengerti mengapa. Ambil dan lewati akan memungkinkan semua operasi tersebut menggunakan pemilihan umum dengan Func<TSource,Int32,TResult>fungsi transformasi. Suka:

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());

Hanya implementasi satu baris. Ia bekerja bahkan dengan daftar kosong, dalam hal ini Anda mendapatkan koleksi batch ukuran nol.

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 });

Cara lain adalah dengan menggunakan operator 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);
    }