重み付きランダム選択アルゴリズムの速度計測【C#】

# はじめに

重み付きランダム選択アルゴリズムは、「アイテムのドロップ」や「ガチャ」など、それぞれのアイテムに選出確立が設定されている中から1つのアイテムを選り抜くためのものです。

その為に使用されるアルゴリズムは様々ですが、「結局、どの場面でどのアルゴリズムを使うのが最適なのか？」といったことが気になりました。

なので、この記事では様々なシチュエーションでそれぞれのアルゴリズムの速度を計測していきます。


# 使用するアルゴリズム

この記事では[『Choice』](https://github.com/mackysoft/Choice)という重み付きランダム選択用のライブラリを使い、そこに実装されている3つのアルゴリズムを使用します。

|アルゴリズム|説明|ソース（GitHub）|
|:--|:--|:--|
|Linear Scan|重みに沿って直線的に探索する最も単純なアルゴリズム。選択は`O(n)`。|[実装コード](https://github.com/mackysoft/Choice/blob/main/Assets/MackySoft/MackySoft.Choice/Runtime/WeightedSelectMethod/LinearWeightedSelectMethod.cs)|
|Binary Search|セットアップは`O(n)`だが、選択ごとに最大`O(log(n))`まで加速する。|[実装コード](https://github.com/mackysoft/Choice/blob/main/Assets/MackySoft/MackySoft.Choice/Runtime/WeightedSelectMethod/BinaryWeightedSelectMethod.cs)|
|Alias Method|セットアップは`O(n)`だが、選択は驚異の`O(1)`。多くのアイテムを選択する際に効果的。|[実装コード](https://github.com/mackysoft/Choice/blob/main/Assets/MackySoft/MackySoft.Choice/Runtime/WeightedSelectMethod/AliasWeightedSelectMethod.cs)|


# 計測方法

- 重みの配列の長さは`[1, 10, 100, 1000, 10000]`、選択回数は`[1, 10, 100, 1000, 10000]`。全部で25通りのパターンを試す。
- 計測結果には「セットアップ時間」と「アイテムの選択時間」を含める。

また、計測用コードは記事の最後に載せてあります。

# 計測結果

## 1 items
Linear Scan が最速。アイテム数が一桁の場合は Linear Scan を使っておけば良さそう。
なお、Alias Method はセットアップ処理が最適化されているので、反復が1回のみの時だけ速い。

|反復回数|1|10|100|1000|10000|
|:--|:--|:--|:--|:--|:--|
|Linear Scan|0.0104ms|**0.0055ms**|**0.0081ms**|**0.0393ms**|**0.3408ms**|
|Binary Search|0.0091ms|0.0083ms|0.0126ms|0.0659ms|0.5944ms|
|Alias Method|**0.0069ms**|0.0065ms|0.01ms|0.0459ms|0.4094ms|

|反復回数|1|10|100|1000|10000|
|:--|:--|:--|:--|:--|:--|
|Linear Scan|0.0155ms|**0.0064ms**|**0.0077ms**|**0.0381ms**|**0.353ms**|
|Binary Search|0.0077ms|0.008ms|0.0123ms|0.0659ms|0.5919ms|
|Alias Method|**0.0062ms**|0.0065ms|0.01ms|0.0462ms|0.41ms|

|反復回数|1|10|100|1000|10000|
|:--|:--|:--|:--|:--|:--|
|Linear Scan|0.009ms|**0.0053ms**|**0.0081ms**|**0.0378ms**|**0.3388ms**|
|Binary Search|0.0073ms|0.0079ms|0.0129ms|0.0653ms|0.5927ms|
|Alias Method|**0.0054ms**|0.0062ms|0.0104ms|0.0461ms|0.4194ms|


## 10 items

10アイテムはアイテムドロップの選択であり得る例。

最初は Linear Scan と Binary Search が拮抗（ Linear Scan がやや優勢か）しているが、100辺りで Alias Method の良さが出始める。

|反復回数|1|10|100|1000|10000|
|:--|:--|:--|:--|:--|:--|
|Linear Scan|0.0113ms|**0.0077ms**|0.0182ms|0.1219ms|1.19ms|
|Binary Search|**0.0109ms**|0.0114ms|0.0237ms|0.158ms|1.4975ms|
|Alias Method|0.0136ms|0.022ms|**0.0151ms**|**0.0601ms**|**0.5041ms**|

|反復回数|1|10|100|1000|10000|
|:--|:--|:--|:--|:--|:--|
|Linear Scan|0.012ms|**0.0072ms**|0.0174ms|0.1272ms|1.1738ms|
|Binary Search|**0.0095ms**|0.0099ms|0.023ms|0.16ms|1.5503ms|
|Alias Method|0.0141ms|0.0104ms|**0.0148ms**|**0.0618ms**|**0.5235ms**|

|反復回数|1|10|100|1000|10000|
|:--|:--|:--|:--|:--|:--|
|Linear Scan|**0.0095ms**|**0.009ms**|0.0179ms|0.1216ms|1.1503ms|
|Binary Search|0.0096ms|0.0103ms|0.0225ms|0.1572ms|1.4991ms|
|Alias Method|0.0129ms|0.0105ms|**0.015ms**|**0.0607ms**|**0.5176ms**|

## 100 items

10アイテムの時とほぼ同じような感じ。
だが、Linear Scan よりも Binary Search がやや優勢か。

|反復回数|1|10|100|1000|10000|
|:--|:--|:--|:--|:--|:--|
|Linear Scan|**0.0201ms**|0.024ms|0.0822ms|0.741ms|7.2211ms|
|Binary Search|0.0212ms|**0.0211ms**|0.0433ms|0.3118ms|2.6434ms|
|Alias Method|0.0717ms|0.0364ms|**0.0395ms**|**0.086ms**|**0.5462ms**|

|反復回数|1|10|100|1000|10000|
|:--|:--|:--|:--|:--|:--|
|Linear Scan|0.0231ms|0.0247ms|0.0855ms|0.7027ms|7.0025ms|
|Binary Search|**0.0224ms**|**0.0231ms**|0.0441ms|0.2776ms|2.6521ms|
|Alias Method|*0.039ms|0.0358ms|**0.0405ms**|**0.0861ms**|**0.5561ms**|

|反復回数|1|10|100|1000|10000|
|:--|:--|:--|:--|:--|:--|
|Linear Scan|**0.0194ms**|0.0232ms|0.0892ms|0.7582ms|7.1886ms|
|Binary Search|0.0206ms|**0.0218ms**|0.0447ms|0.2804ms|2.6375ms|
|Alias Method|0.0376ms|0.0381ms|**0.0413ms**|**0.0871ms**|**0.5728ms**|

## 1000 items

綺麗な線形。
1000辺りで Alias Method 優勢になってくる。

|反復回数|1|10|100|1000|10000|
|:--|:--|:--|:--|:--|:--|
|Linear Scan|**0.1147ms**|0.1672ms|0.7792ms|6.7539ms|66.8329ms|
|Binary Search|0.1205ms|**0.1183ms**|**0.1504ms**|0.4758ms|3.7755ms|
|Alias Method|0.2783ms|0.2722ms|0.2925ms|**0.3238ms**|**0.7824ms**|

|反復回数|1|10|100|1000|10000|
|:--|:--|:--|:--|:--|:--|
|Linear Scan|**0.1068ms**|0.1717ms|0.8331ms|6.8282ms|68.455ms|
|Binary Search|0.1217ms|**0.1173ms**|**0.1499ms**|0.5026ms|3.7627ms|
|Alias Method|0.2785ms|0.2889ms|0.2876ms|**0.3318ms**|**0.908ms**|

|反復回数|1|10|100|1000|10000|
|:--|:--|:--|:--|:--|:--|
|Linear Scan|**0.102ms**|0.1636ms|0.7271ms|6.743ms|66.4393ms|
|Binary Search|0.1241ms|**0.1208ms**|**0.1501ms**|0.5216ms|4.0165ms|
|Alias Method|0.2782ms|0.2755ms|0.2777ms|**0.3454ms**|**0.8068ms**|


## 10000 items

Binary Searchが優秀。


|反復回数|1|10|100|1000|10000|
|:--|:--|:--|:--|:--|:--|
|Linear Scan|**1.1885ms**|1.7971ms|8.0482ms|69.1749ms|664.8696ms|
|Binary Search|1.3329ms|**1.3181ms**|**1.3454ms**|**1.7735ms**|6.1215ms|
|Alias Method|2.8859ms|2.8719ms|2.8832ms|2.9779ms|**3.4764ms**|

|反復回数|1|10|100|1000|10000|
|:--|:--|:--|:--|:--|:--|
|Linear Scan|**1.1676ms**|1.6953ms|8.0905ms|70.1629ms|668.3197ms|
|Binary Search|1.3118ms|**1.3361ms**|**1.3407ms**|**1.786ms**|6.1105ms|
|Alias Method|2.8833ms|2.934ms|2.951ms|2.9845ms|**3.6259ms**|

|反復回数|1|10|100|1000|10000|
|:--|:--|:--|:--|:--|:--|
|Linear Scan|**1.3098ms**|1.9826ms|8.063ms|68.9301ms|666.9364ms|
|Binary Search|1.4456ms|**1.3787ms**|4.6233ms|**1.7861ms**|6.0783ms|
|Alias Method|2.9751ms|2.9144ms|**2.9236ms**|2.9851ms|**3.5149ms**|

## （おまけ）10000 items without setup

セットアップ時間を含まない場合の計測結果。
やっぱり Alias Method が一番速い。

|反復回数|1|10|100|1000|10000|
|:--|:--|:--|:--|:--|:--|
|Linear Scan|0.0207ms|0.7364ms|6.5433ms|67.3963ms|671.3184ms|
|Binary Search|0.0015ms|0.0055ms|0.0492ms|0.496ms|4.828ms|
|Alias Method|**0.0005ms**|**0.0011ms**|**0.0066ms**|**0.0579ms**|**0.5559ms**|

# まとめ

- Linear Scan は要素数が少ない場合に有効
- Binary Search は汎用性が高い
- Alias Methodはセットアップを除けば最速

アルゴリズム選定の参考になれば幸いです。

# おわりに

今回使った『Choice』は気合を入れて作ったものなので使ってもらえると嬉しくなります。

https://github.com/mackysoft/Choice

# 参考
- [A Faster Weighted Random Choice](https://blog.bruce-hill.com/a-faster-weighted-random-choice)
- [Walker's Alias Methodの箱の作り方のわかりやすい説明](https://qiita.com/kaityo256/items/1656597198cbfeb7328c)
- [重み付きランダムサンプリングアルゴリズム](https://qiita.com/kaityo256/items/64c12bb8c8946d7f03c6)

# 検証用コード

```WeightedSelectMethodSpeedTests.cs
using System.Linq;
using System.Collections.Generic;
using System.Diagnostics;
using NUnit.Framework;
using UnityEngine;

namespace MackySoft.Choice.Tests {
	public class WeightedSelectMethodSpeedTests {

		static readonly int[] k_Iterations = new int[] { 1, 10, 100, 1000, 10000 };

		[Test]
		public void CompareSpeedAllMethods ([Values(1,10,100,1000,10000)] int count) {
			// 重みの配列を[1, 10, 100, 1000, 10000]、いずれかの長さで用意。
			var source = ItemEnumerableGenerator.GenerateEnumerable(count).ToArray();

			// 選択に使用する[0.0f~1.0f]の値を用意する。
			float[] values = new float[k_Iterations.Max()];
			for (int i = 0;values.Length > i;i++) {
				values[i] = Random.value;
			}

			Stopwatch stopwatch = new Stopwatch();
			foreach (IWeightedSelectMethod method in AllWeightedSelectMethods()) {

				// [1, 10, 100, 1000, 10000]、5通りの反復回数を試みる。
				for (int i = 0;k_Iterations.Length > i;i++) {
					int iteration = k_Iterations[i];

					stopwatch.Start();

					// セットアップ
					var weightedSelector = source.ToWeightedSelector(x => x.item,x => x.weight,method);

					// WeightedSelectorからアイテムを選択する。
					for (int k = 0;iteration > k;k++) {
						weightedSelector.SelectItem(values[k]);
					}

					stopwatch.Stop();

					UnityEngine.Debug.Log($"{method.GetType()}: Count {count}, Iteration {iteration}, Speed {stopwatch.Elapsed.TotalMilliseconds}ms");
					stopwatch.Reset();
				}
			}

			Assert.Pass();
		}

		static IEnumerable<IWeightedSelectMethod> AllWeightedSelectMethods () {
			yield return WeightedSelectMethod.Linear;
			yield return WeightedSelectMethod.Binary;
			yield return WeightedSelectMethod.Alias;
		}

	}
}
```