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

はじめに

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

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

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

使用するアルゴリズム

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

アルゴリズム	説明	ソース（GitHub）
Linear Scan	重みに沿って直線的に探索する最も単純なアルゴリズム。選択はO(n)。	実装コード
Binary Search	セットアップはO(n)だが、選択ごとに最大O(log(n))まで加速する。	実装コード
Alias Method	セットアップはO(n)だが、選択は驚異のO(1)。多くのアイテムを選択する際に効果的。	実装コード

計測方法

• 重みの配列の長さは[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』は気合を入れて作ったものなので使ってもらえると嬉しくなります。

参考

• A Faster Weighted Random Choice
• Walker's Alias Methodの箱の作り方のわかりやすい説明
• 重み付きランダムサンプリングアルゴリズム

検証用コード

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

    }
}