ループを使わずに偏りランダムを行う方法

Question

ゲームのガチャ等では偏りランダムは欠かせないものとなっています。
私の場合以下のようなやり方で行っています。

Aの確率は80% Bの確率は19.5% Cの確率は0.5% の場合
➀ 各データの確率を分数のように通分し全て整数にします
B，Cが少数の確率がなのですべて１０倍します。
Aは800，Bは195，Cは5となります。
➁ ➀で求めた各データの値を分数のように約分します
この場合、各データの➀の値はすべて５の倍数なので、すべて５で割ります。
Aは160，Bは39，Cは1となります。
➂ ➁で求めた各データの値分を配列に代入します
Aは160なので配列にAを160個代入。Bは39個代入。Cは1個代入。
配列の中身は ['A', 'A', 'A', 'A', ... 'A', 'B', 'B', 'B', 'B', ... 'B', 'C'] のようになります。
➃ 偏りランダムを行います
配列[Math.floor(Math.random() * 配列.length)] で取得します。

// *** 偏り *** //
let table = {
	"A": 80.0,
	"B": 19.5,
	"C": 0.5
};

// *** 手順➀ *** //
while (true) {
	let ok = true;
	for (let key in table) {
		if (!Number.isInteger(table[key])) {
			ok = false;
			break;
		}
	}
	if (ok) {
		break;
	}
	for (let key in table) {
		table[key] *= 10;
	}
}

// *** 手順➁ *** //
function GCD(array) {
    function call(a, b) {
		return (b ? call(b, a % b) : a);
	}
    let ans = array[0];
    for (let i = 1; i < array.length; i++) {
        ans = call(ans, array[i]); 
    }
    return ans;
}
let div = GCD(Object.values(table));
for (let key in table) {
	table[key] /= div;
}

// *** 手順➂ *** //
let output = new Array();
for (let key in table) {
	let amount = table[key];
	for (let i = 0; i < amount; i++) {
		output.push(key);
	}
}

// *** テスト *** //
let items = {};
for (let i = 0; i < 1000; i++) {

	// *** 手順➃ *** //
	let key = output[Math.floor(Math.random() * output.length)];

	// *** カウント *** //
	if (!items.hasOwnProperty(key)) {
		items[key] = 0;
	}
	items[key]++;

}
console.log(items);

※ ここのページを参考にいろいろと改良しました。

問題点

このやり方では超低確率での偏りランダムを行う際、➂の手順で大量のデータを入れる必要があります。
環境によってはメモリ不足などのパフォーマンスに影響を及ぼします。
その為、著しく低い確率の偏りランダムを行うのは不向きです。
ループを使わずにパフォーマンスも安定している偏りランダムを行う方法についてご教授ください。
よろしくお願いします。

Comments

[m.ts10806]

まず自身がやったこと（コード）を提示し、それについての問題点を指摘してもらった方が良いかと思います。

[退会済みユーザー]

了解しました。

Answer 1

普通に考えれば、

function rabc(){
    const r = Math.random();
    if(r<0.8) return "A";
    if(r<0.8+0.195) return "B";
    return "C";
}

テーブルにすると、

function rabc(){
    const a = [0.8,"A",0.8+0.195,"B",1,"C"];
    const r = Math.random();
    for(let i=0; i<a.length; i+=2){
        if(r<a[i]) return a[i+1];
    }
}

Answer 2

例の場合は、配列にAを160個、Bを39個、Cを1個入れています。これがわかるのなら、わざわざ配列を見に行かずとも、配列の0159番がA、160198番がB、199番がCだとわかることになります。…であれば、配列に入ったデータなど不要ということになります。
データ数を減らすために②で「約分」をしているのでしょうが、データが不要ならば約分をする必要もなくなります。たとえ1億分の1の確率であろうとも、くじを1億本も用意する必要はありません。

Comments

[退会済みユーザー]

確かによく考えてみたら不要でした。深く考えすぎてしまいました(+_+)

Answer 3

方式	方法
くじ引き方式	200個の要素を持つ配列にA,B,Cを格納 -> Fisher–Yates shuffle
乱数方式	Math.floor(Math.random()*200) -> A,B,Cを数値範囲で対応させる

メモリを気にされていますが、200個の配列は大してメモリを消費しませんし、200回に1回くじを生成する処理が高負荷とは思いません。

Re: CantRunRiver さん

Comments

[退会済みユーザー]

> メモリを気にされていますが、200個の配列は大してメモリを消費しませんし、200回に1回くじを生成する処理が高負荷とは思いません。
200個はあくまで↓の説明をするための例です。
> ゲームのガチャ等では偏りランダムは欠かせないものとなっています。
> 私の場合以下のようなやり方で行っています。

問題点で挙げた話をしています
例えば、超低確率(0.00000001%)なら1億回の要素を追加することになります。
分かりずらくてすいませんm(._.)m