シーケンスを n 個毎に分割する

(2017/06/28 9:31:13 created.)

(2017/06/28 11:30:35 modified.)

実務で必要になったのでやってみた内容です。要求仕様はいたってシンプルで、平坦に並んでいるシーケンスを n 個毎に区切ってグルーピングすることが目的です。

例えば { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } を 3 個毎に分割して、{ { 0, 1, 2 }, { 3, 4, 5 }, { 6, 7, 8 }, { 9 } } という 4 つの要素に分割したシーケンスにします。最後の { 9 } については { 9, 0, 0 } というように既定値で詰めたりとかいろいろあるかもしれませんが、ここではある分だけの要素をそのままにしておくようにします。

で、結局 stackoverflow にお世話になりました。
ところが、方法がいくつも書いてあって、しかも ToArray() したら不具合のあるものもあって結局どれを使えばいいの？ってなったので、自分で処理時間を評価してみました。

まず時間計測用のクラスを用意します。ここでは tocsworld | C# での処理時間計測いろいろを参考にして、Win32 API を使用する方法を採用しました。

TimeCount.cs

```
namespace ConsoleApplication2
```
```
{
```

    using System.Runtime.InteropServices;

```
 
```
```
    internal class TimeCount
```
```
    {
```
```
        [DllImport("kernel32.dll")]
```

        private static extern bool QueryPerformanceCounter(ref long lpPerformanceCount);

```
 
```
```
        [DllImport("kernel32.dll")]
```

        private static extern bool QueryPerformanceFrequency(ref long lpFrequency);

```
 
```
```
        private long _startCounter;
```
```
 
```
```
        public void Start()
```
```
        {
```

            QueryPerformanceCounter(ref this._startCounter);

```
        }
```
```
 
```
```
        public void Reset()
```
```
        {
```

            QueryPerformanceCounter(ref this._startCounter);

```
        }
```
```
 
```

        public double ElapsedMilliseconds

```
        {
```
```
            get
```
```
            {
```
```
                long stopCounter = 0;
```

                QueryPerformanceCounter(ref stopCounter);

```
                long frequency = 0;
```

                QueryPerformanceFrequency(ref frequency);

                return frequency != 0 ? (double)(stopCounter - this._startCounter) * 1000.0 / frequency : 0;

```
            }
```
```
        }
```
```
    }
```
```
}
```

そして、今回比較するメソッドは次の 3 つです。

Extensions.cs

```
namespace ConsoleApplication2
```
```
{
```
```
    using System;
```
```
    using System.Collections.Generic;
```
```
    using System.Linq;
```
```
 
```
```
    public static class Extensions
```
```
    {
```

        public static IEnumerable<IEnumerable<T>> Chunk1<T>(this IEnumerable<T> source, int size)

```
        {
```

            if (source == null) throw new ArgumentException("source");

            if (size < 1) throw new ArgumentException("size");

```
 
```

            return source.Select((x, i) => new { Index = i, Value = x })

                         .GroupBy(x => x.Index / size, (key, result) => result.Select(r => r.Value));

```
        }
```
```
 
```

        public static IEnumerable<IEnumerable<T>> Chunk2<T>(this IEnumerable<T> source, int size)

```
        {
```

            if (source == null) throw new ArgumentException("self");

            if (size < 1) throw new ArgumentException("size");

```
 
```
```
            while (source.Any())
```
```
            {
```

                yield return source.Take(size);

                source = source.Skip(size);

```
            }
```
```
        }
```
```
 
```

        public static IEnumerable<IEnumerable<T>> Chunk3<T>(this IEnumerable<T> source, int size)

```
        {
```

            if (source == null) throw new ArgumentException("self");

            if (size < 1) throw new ArgumentException("size");

```
 
```

            using (var enumerator = source.GetEnumerator())

```
            {
```

                var list = new List<T>(size);

                while (enumerator.MoveNext())

```
                {
```

                    list.Add(enumerator.Current);

                    if (list.Count >= size)

```
                    {
```

                        yield return list;

                        list = new List<T>();

```
                    }
```
```
                }
```
```
 
```
```
                // 残りの部分
```
```
                if (list.Any())
```
```
                {
```
```
                    yield return list;
```
```
                }
```
```
            }
```
```
        }
```
```
    }
```
```
}
```

Chunk1<T>() 拡張メソッドは GroupBy() 拡張メソッドを利用したスマートな方法です。Select() 拡張メソッドで 2 回射影をおこなってはいますが、処理時間のオーダーとしては O(n) になっています。GroupBy() 拡張メソッドもハッシュ値による処理をおこなっているため、それほど遅くはならないという予測です。

Chunk2<T>() 拡張メソッドは Take() 拡張メソッドと Skip() 拡張メソッドの組み合わせで、非常に直感的なコードになっています。しかし、一度のループの中で 2 回全要素を走査しているため、処理時間のオーダーは O(n^2) となります。

Chunk3<T>() 拡張メソッドは Linq をあきらめて泥臭くした方法です。IEnumerator<T> を使って先頭要素から順番に指定個数分を List<T> に入れていく方法です。こちらの処理時間のオーダーは O(n) となります。

というわけで、もう結果は見えているような気がしますが、念のため比較をしてみます。

Program.cs

```
namespace ConsoleApplication2
```
```
{
```
```
    using System;
```
```
    using System.Collections.Generic;
```
```
    using System.Linq;
```
```
 
```
```
    class Program
```
```
    {
```
```
        static void Main(string[] args)
```
```
        {
```

            var func = new Action<IEnumerable<int>>(sequence =>

```
            {
```

                Console.WriteLine("length = {0} ------------------", sequence.Count());

```
 
```
```
                var size = 13;
```
```
                double elapsed;
```

                var counter = new TimeCount();

```
 
```
```
                counter.Start();
```

                var chunk1 = sequence.Chunk1(size).ToArray();

                elapsed = counter.ElapsedMilliseconds;

                Console.WriteLine("Chunk1 : {0, 10:f3}[ms] : {1} : {2}", elapsed, string.Join(" ", chunk1.First().Select(x => x.ToString())), string.Join(" ", chunk1.Last().Select(x => x.ToString())));

```
 
```
```
                counter.Reset();
```

                var chunk2 = sequence.Chunk2(size).ToArray();

                elapsed = counter.ElapsedMilliseconds;

                Console.WriteLine("Chunk2 : {0, 10:f3}[ms] : {1} : {2}", elapsed, string.Join(" ", chunk2.First().Select(x => x.ToString())), string.Join(" ", chunk2.Last().Select(x => x.ToString())));

```
 
```
```
                counter.Reset();
```

                var chunk3 = sequence.Chunk3(size).ToArray();

                elapsed = counter.ElapsedMilliseconds;

                Console.WriteLine("Chunk3 : {0, 10:f3}[ms] : {1} : {2}", elapsed, string.Join(" ", chunk3.First().Select(x => x.ToString())), string.Join(" ", chunk3.Last().Select(x => x.ToString())));

```
 
```
```
                Console.WriteLine("");
```
```
            });
```
```
 
```
```
            var rnd = new Random();
```
```
            do
```
```
            {
```
```
                Console.Clear();
```
```
 
```

                var source = Enumerable.Range(0, 10000).Select(x => rnd.Next(0, 101)).ToArray();

                func(source.Take(1000).ToArray());

                func(source.Take(2000).ToArray());

                func(source.Take(3000).ToArray());

                func(source.Take(4000).ToArray());

                func(source.Take(5000).ToArray());

```
                func(source);
```

            } while (Console.ReadKey().Key != ConsoleKey.Escape);

```
        }
```
```
    }
```
```
}
```

func 変数で 3 つの拡張メソッドを実行するメソッドを準備して、色々な長さのシーケンスを処理させます。実行結果はこちら。

予想通り Chunk3<T>() 拡張メソッドが一番速い結果となりました。Chunk2<T>() 拡張メソッドは遅いとは思っていましたが、予想を超えてはるかに遅い…。控えめに言って使い物になりませんね。

以上、シーケンスを n 個毎に分割する方法でした。Linq は油断すると処理が遅くなるので要注意。

<< 古い記事へ
ListBox などのアイテムを...

新しい記事へ >>
円周率の小数点以下に現れる数値