⚡
Alias Method: как он устроен внутриВчерашний weighted random полезен, но важно понимать что по сложности он — O(n): чем больше предметов, тем дольше выборка.
Есть Alias Method, который даёт O(1) — время выборки не зависит от размера таблицы вообще.
За это платим однократной предподготовкой O(n) при старте и памятью.
Разберем пример. Допустим, три предмета с весами: Меч — 3, Зелье — 1, Топор — 2. Сумма = 6.
Шаг 1. Делим каждый вес на среднее (6 ÷ 3 = 2) — нормализованные высоты:
Меч → 1.5
Зелье → 0.5
Топор → 1.0
Шаг 2. Рисуем три столбика — каждый ровно высотой 1.0:
| | | |
| 1.0 | 1.0 | 1.0 |
Слот0 Слот1 Слот2
Шаг 3. Расставляем предметы. Меч (1.5) не влезает в один слот.
Зелье (0.5) занимает полслота — свободное место отдаём Мечу:
| М | М | |
| М | З | Т |
Слот0 Слот1 Слот2
Слот 0 → полностью Меч
Слот 1 → снизу Зелье (50%), сверху Меч (50%)
Слот 2 → полностью Топор
Шаг 4. Сохраняем для каждого слота: кто основной, кто запасной и граница.
Это и есть таблица алиасов.
───────────────────────────────────
Выборка — всегда два шага:
Слот: 0 1 2
Основной: Меч Зелье Топор
Запасной: — Меч —
Граница: 1.0 0.5 1.0
Шаг 1. Бросаем кубик — выбираем случайный слот.
i = Random.Range(0, 3) → выпало 1
Шаг 2. Бросаем монетку — сравниваем с границей слота.
r = Random.value → выпало 0.3
0.3 < 0.5 (граница слота 1) → берём основного → Зелье ✅
Тот же слот 1, но r = 0.7:
0.7 > 0.5 → берём запасного → Меч ✅
Слот 0 и 2: граница = 1.0 → любое число меньше 1.0 → всегда основной.
Вот почему O(1): не важно сколько предметов — всегда один Random.Range,
один Random.value, одно сравнение.
───────────────────────────────────
Теперь код. Строим таблицу алиасов один раз, потом только Sample():
public class AliasTable
{
private int[] _alias; // «запасной» предмет для каждого слота
private float[] _prob; // граница: ниже — основной, выше — запасной
// Вызывается один раз — O(n)
public AliasTable(int[] weights)
{
int n = weights.Length;
_alias = new int[n];
_prob = new float[n];
// Нормализуем веса: каждый вес → высота столбика (среднее = 1.0)
float sum = 0;
foreach (var w in weights) sum += w;
float[] p = new float[n];
for (int i = 0; i < n; i++) p[i] = weights[i] * n / sum;
// Делим предметы на «маленькие» (< 1.0) и «большие» (>= 1.0)
var small = new Queue<int>();
var large = new Queue<int>();
for (int i = 0; i < n; i++)
if (p[i] < 1f) small.Enqueue(i);
else large.Enqueue(i);
// Заполняем слоты: маленький берёт «запасного» из большого
while (small.Count > 0 && large.Count > 0)
{
int s = small.Dequeue();
int l = large.Dequeue();
_prob[s] = p[s]; // граница слота = высота маленького
_alias[s] = l; // запасной — большой предмет
// У большого забрали часть — уменьшаем его высоту
p[l] = (p[l] + p[s]) - 1f;
if (p[l] < 1f) small.Enqueue(l);
else large.Enqueue(l);
}
// Оставшиеся «большие» заполняют слот целиком
foreach (int i in large) _prob[i] = 1f;
foreach (int i in small) _prob[i] = 1f; // float-погрешность
}
// Вызывается каждый раз — O(1)
public int Sample()
{
int i = Random.Range(0, _prob.Length); // кубик: выбираем слот
float r = Random.value; // монетка: основной или запасной?
return r < _prob[i] ? i : _alias[i];
}
}
Использование:
// Один раз при старте
int[] weights = { 3, 1, 2 }; // Меч, Зелье, Топор
string[] items = { "Меч", "Зелье", "Топор" };
var table = new AliasTable(weights);
// Каждый раз при дропе
string dropped = items[table.Sample()];
Когда использовать: 50000+ предметов.
Для обычного лутбокса на 5–10 предметов — вчерашний метод проще.
#мат_геймдев #МатРазбор #рандом #оптимизация
