【C#】コレクションから要素を重複せずランダムに、しかも高速に抽出する。


# ■まずはさておきソースコード

指定した要素数を、指定した数のブロックに分割するBlockクラスと、
それを利用してコレクションにランダム（なインデックス）でアクセスする為のRandomizerクラスです。

```c#:Block.cs（一部抜粋・コメント削除）

	public class Block
	{
		public int Begin { get; private set; }
		public int End   { get; private set; }
		public int Count { get { return End - Begin + 1; } }

		public Block(int begin, int end)
		{
			this.Begin = Math.Min( begin, end );
			this.End   = Math.Max( begin, end );
		}

		public static List<Block> As( int size, int n )
		{
			List<Block> blocks = new List<Block>();
			
			decimal seeksize = (decimal)size / (decimal)n;

			decimal index = 0m;
			
			int tail = size - 1;
			int last = n - 1;

			for ( int i = 0; i < n; i++ )
			{
				int begin = (int)Math.Ceiling(index);

				index += seeksize;
				
				int end 
					= i == last
					? tail
					: (int)Math.Ceiling( index ) - 1;

				Block block = new Block(begin, end);
				blocks.Add( block );
			}


			return blocks;
		}
	}
```

```c#:Randomizer.cs（一部抜粋・コメント削除）

	public class Randomizer<T>
	{
		private readonly IEnumerable<T> source;
		private readonly Random r;

		#region ctor
		public Randomizer( IEnumerable<T> source, int? seed = null )
		{
			this.source = source;
			this.r = null == seed
				? new Random()
				: new Random( seed.Value );
		}
		#endregion

		public IEnumerable<T> Randomize( int count, OrderOptions order = OrderOptions.KeepOrigin )
		{
			IEnumerable<T> random = this.Core( count );

			switch ( order )
			{
				case OrderOptions.Random:
					return random.OrderBy( x => Guid.NewGuid() );

				default:
					return random;
			}
		}


		private IEnumerable<T> Core( int count )
		{
			if ( count <= 0 )
			{
				return Enumerable.Empty<T>();
			}

			int size = this.source.Count();
			if ( size <= count )
			{
				return this.source;
			}

			int half = size / 2;
			if ( half < count )
			{
				return Skip( size, size - count );
			}
			else
			{
				return Take( size, count );
			}
		}

		private IEnumerable<T> Take( int size, int count )
		{
			var blocks = Block.As( size, count );
			foreach ( Block block in blocks )
			{
				int dx = r.Next( 0, block.Count );
				int index = block.Begin + dx;

				yield return this.source.ElementAt( index );
			}
		}

		private IEnumerable<T> Skip( int size, int count )
		{
			var blocks = Block.As( size, count );
			foreach ( Block block in blocks )
			{
				int dx = r.Next( 0, block.Count );
				int skip = block.Begin + dx;

				foreach ( int index in block.AsIndexes() )
				{
					if ( index == skip ) continue;

					yield return this.source.ElementAt( index );
				}
			}
		}
	}
```


# ■説明／解説

## これは何をするもの？

簡単に言うと、コレクションからランダムで指定した数の要素を抜き出して来るものです。

## なんでこんなもの作ったの？

あるシステム開発で、**「クライアントから送られてきたデータファイル（結構多い）から、適当に一部抽出してテストデータとして使いたい」**と言う要件が出て来ので。
*（他にも「大量のデータの中からランダムで少数抜き出したい」みたいな話は、頻繁ではないくせに「忘れた時にやって来る」くらいの絶妙な頻度で発生する、、、と思う）*

簡単に要件をまとめるとこんな感じ。

- 母体となるコレクションから、任意の数の要素をランダムに取り出したい。
- 重複して同じ要素を取り出してはいけない。
- 可能であれば、元の並び順を維持してランダムに取り出したい。


## 普通にランダム抽出ロジックを実装するとどうなる？

「コレクションからランダムに任意の個数の要素を取得する（但し、重複して取り出してはいけない）」と言う要件があった場合、多分みんな以下のようなコードを書くと思う。

1. 要素をランダムに並び替える。
2. 先頭から指定された個数の要素を取り出す。

特に制約がない場合、多分こんなコードを書く事になると思う。

```c#:ランダムに10個取り出すサンプルコード
	var random10 = sequens.AsEnumerable()
		.OrderBy( x => Guid.NewGuid() )
		.Take( 10 );
```

普通こう実装しますよね。
誰だってそーする、僕だってそーする。

### このロジックのメリット：

- コードがシンプルで解り易い。
- LINQで書けるので汎用性が高い。


### このロジックのデメリット：

- 取り出す個数が多かろうが少なかろうが、母体全量を並べ替える必要がある。*（処理が無駄）*
- GUIDとか本質的に無関係なやつが目立つ。*（好みの問題）*
- 元の並び順が維持されない。

「元の並び順を維持する」という要件は珍しいと思いますが、これを要求されるとかなり難しい話になってしまいます。
特に、元の並び順が **データ内の何かでソートされている訳ではない** とか **元の並びに戻すのが難しい** と言う場合はキツいです。
そもそも、「ランダムに並び替える→抜き出す→元の順番に並び替える」と **並び替えを二度もやるのはバカっぽくてイケてない** です。


## Randomizerを使うと何が嬉しいの？

### Randomizerのメリット：

- 要素全体の並び替えを行わないので、高速に動作する。*（特に、母数が多いが抽出するのが少ない場合に有利）*
- 元の要素の並び順を維持してランダムに抽出出来る。
- オプション指定*（OrderOptions.Random）*で、ランダム抽出後に改めてランダムに並び替える事も出来る。

### Randomizerのデメリット：

- ランダムではあるが、ある程度の規則性が発生してしまう。*（詳細後述）*

### Randomizerの規則性について：

この実装は以下のようなアルゴリズムで擬似的なランダム抽出を行っています。

1.　まず要素全体を指定された個数（抽出したい数）のブロックに等分割する。
2.　各ブロックから一つだけ要素を取り出す。
3.　取り出した要素を返す。*（yield return 列挙）*

この処理によって、擬似的にランダム抽出を行っている為、どうしても **等分割する事による規則性** が発生してしまいます。

例えば、1～10の10個の要素からランダムに2個抜き出す場合。
このアルゴリズムを使うと「1～5の中から一つ」と「6～10の中から一つ」という規則性が発生します。
つまり、ランダムに抜き出した結果からは「1と2」とか「6と10」という組み合わせが得られないと言う事になります。

ただ、逆に言うとこの特性は **乱数が偏る事を防げる（ある一定の均等さで分布してくれる）** というメリットとも言えますね。



# ■ソリューション一式

**vs-git クローンURL：**
https://ellnore-git.visualstudio.com/_git/RandomizeUtility

**GitHubリポジトリURL：**
https://github.com/sugaryo/CS-RandomizeUtility


**動作検証画面（実装サンプル）：**
![RandomizeUtilTestForm.png](https://qiita-image-store.s3.amazonaws.com/0/170347/37984a2d-edb9-d2cb-310c-fa5e7c73bc91.png)




*※まぁ本当の事言うと、別にこれそんなに必要性が高かったワケじゃなくて、ただロジックが面白そうだからコーディングしたいなって思ったから勢いで作っただけなんですけどね。*