AliasMethod Module

Source.Forks · Algorithm Module

AliasMethod

Weighted Random Selection

대규모 가중치 데이터셋에서 확률 기반 항목을 O(1) 시간에 선택. Vose's Algorithm으로 사전 계산된 Alias Table을 통해 런타임 성능 병목을 완전히 제거합니다.

O(1) select O(n) build ScriptableObject Vose's Algorithm

⚡

상수 시간 선택

데이터 크기 n에 무관하게 O(1)로 일정

◈

최소 메모리

두 배열만으로 전체 가중치 정보를 표현

◉

에셋 직렬화

ScriptableObject로 에디터에서 관리 가능

수학적 배경

각 항목의 가중치를 w_i 라 할 때, 선택 확률은 아래와 같이 정의됩니다. 평균 확률 1/n 을 기준으로 가중치가 높은 항목의 여분을 낮은 항목의 빈 공간에 채워 모든 Bin 높이를 균일하게 맞춥니다. P(X=i) = w i / Σ(w j) 선택 시 랜덤 인덱스 결정 후 p < probability[i] 비교만으로 결과가 확정되므로 추가 루프가 없습니다.

핵심 구성 요소

struct AliasTable

계산된 확률 테이블과 에일리어스 인덱스를 보관하는 핵심 자료구조.

float[] probabilities — 인덱스 본인 선택 확률

int[] aliases — 대체 항목 인덱스

int Sample(float r) — O(1) 샘플링

static class AliasTableBuilder

Vose's Alias Method로 O(n) 시간에 테이블을 빌드하는 빌더.

AliasTable Build(List<float>)

가중치 정규화 Small / Large 스택 부동소수점 안전

ScriptableObject AliasTableAsset

미리 계산된 테이블을 유니티 에셋으로 저장·로드. 인스펙터에서 즉시 확인 가능.

직렬화 인스펙터 미리보기 런타임 로드

구현 예시

C# AliasTable.cs · AliasTableBuilder.cs

public struct AliasTable
{
    public float[] probabilities;
    public int[]   aliases;

    public int Sample(float rawRandom)
    {
        int   column = (int)(rawRandom * probabilities.Length);
        float p      = (rawRandom * probabilities.Length) - column;
        return p < probabilities[column] ? column : aliases[column];
    }
}

public static class AliasTableBuilder
{
    public static AliasTable Build(List<float> weights)
    {
        int   n   = weights.Count;
        float sum = 0;
        foreach (var w in weights) sum += w;

        float[] prob          = new float[n];
        int[]   alias         = new int[n];
        float[] scaledWeights = new float[n];
        Stack<int> small = new Stack<int>();
        Stack<int> large = new Stack<int>();

        for (int i = 0; i < n; i++)
        {
            scaledWeights[i] = weights[i] * n / sum;
            if (scaledWeights[i] < 1.0f) small.Push(i);
            else                          large.Push(i);
        }

        while (small.Count > 0 && large.Count > 0)
        {
            int s = small.Pop();
            int l = large.Pop();
            prob[s]  = scaledWeights[s];
            alias[s] = l;
            scaledWeights[l] = scaledWeights[l] + scaledWeights[s] - 1.0f;
            if (scaledWeights[l] < 1.0f) small.Push(l);
            else                          large.Push(l);
        }

        while (large.Count > 0) prob[large.Pop()] = 1.0f;
        while (small.Count > 0) prob[small.Pop()] = 1.0f;

        return new AliasTable { probabilities = prob, aliases = alias };
    }
}

활용 사례

⚔드롭 테이블 · 전리품 생성

🗺절차적 지형 · 타일 배치

🧠AI 행동 패턴 선택

💎가챠 · 확률 기반 보상