소프트 코딩 된 확률 솔루션

하드 코드 된 확률 솔루션에는 코드에서 확률을 설정해야한다는 단점이 있습니다. 런타임에는 확인할 수 없습니다. 유지하기도 어렵다.

다음은 동일한 알고리즘의 동적 버전입니다.

1. 실제 항목 쌍과 각 항목의 가중치 배열을 만듭니다.
2. 항목을 추가 할 때 항목의 가중치는 자체 가중치 와 배열에 이미있는 모든 항목의 가중치의 합이되어야합니다. 따라서 합계를 별도로 추적해야합니다. 특히 다음 단계에서 필요하기 때문입니다.
3. 객체를 검색하려면 0과 모든 항목의 가중치 합계 사이의 난수를 생성하십시오.
4. 난수보다 크거나 같은 가중치를 가진 항목을 찾을 때까지 배열을 처음부터 끝까지 반복하십시오.

다음은 게임에서 사용하는 모든 객체에 대해 인스턴스화 할 수있는 템플릿 클래스 형태 로 Java로 작성된 샘플 구현입니다 . 그런 다음 메소드를 사용하여 객체 .addEntry(object, relativeWeight)를 추가하고 이전에 추가 한 항목 중 하나를 선택할 수 있습니다.get()

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class WeightedRandomBag<T extends Object> {

    private class Entry {
        double accumulatedWeight;
        T object;
    }

    private List<Entry> entries = new ArrayList<>();
    private double accumulatedWeight;
    private Random rand = new Random();

    public void addEntry(T object, double weight) {
        accumulatedWeight += weight;
        Entry e = new Entry();
        e.object = object;
        e.accumulatedWeight = accumulatedWeight;
        entries.add(e);
    }

    public T getRandom() {
        double r = rand.nextDouble() * accumulatedWeight;

        for (Entry entry: entries) {
            if (entry.accumulatedWeight >= r) {
                return entry.object;
            }
        }
        return null; //should only happen when there are no entries
    }
}

용법:

WeightedRandomBag<String> itemDrops = new WeightedRandomBag<>();

// Setup - a real game would read this information from a configuration file or database
itemDrops.addEntry("10 Gold",  5.0);
itemDrops.addEntry("Sword",   20.0);
itemDrops.addEntry("Shield",  45.0);
itemDrops.addEntry("Armor",   20.0);
itemDrops.addEntry("Potion",  10.0);

// drawing random entries from it
for (int i = 0; i < 20; i++) {
    System.out.println(itemDrops.getRandom());
}

Unity, XNA 또는 MonoGame 프로젝트를 위해 C #으로 구현 된 동일한 클래스는 다음과 같습니다 .

using System;
using System.Collections.Generic;

class WeightedRandomBag<T>  {

    private struct Entry {
        public double accumulatedWeight;
        public T item;
    }

    private List<Entry> entries = new List<Entry>();
    private double accumulatedWeight;
    private Random rand = new Random();

    public void AddEntry(T item, double weight) {
        accumulatedWeight += weight;
        entries.Add(new Entry { item = item, accumulatedWeight = accumulatedWeight });
    }

    public T GetRandom() {
        double r = rand.NextDouble() * accumulatedWeight;

        foreach (Entry entry in entries) {
            if (entry.accumulatedWeight >= r) {
                return entry.item;
            }
        }
        return default(T); //should only happen when there are no entries
    }
}

그리고 여기 JavaScript가 있습니다 :

var WeightedRandomBag = function() {

    var entries = [];
    var accumulatedWeight = 0.0;

    this.addEntry = function(object, weight) {
        accumulatedWeight += weight;
        entries.push( { object: object, accumulatedWeight: accumulatedWeight });
    }

    this.getRandom = function() {
        var r = Math.random() * accumulatedWeight;
        return entries.find(function(entry) {
            return entry.accumulatedWeight >= r;
        }).object;
    }
}

찬성:

• 모든 무게 비율을 처리 할 수 ​​있습니다. 원하는 경우 세트에서 천문학적으로 확률이 작은 항목을 가질 수 있습니다. 가중치는 100을 더할 필요도 없습니다.
• 런타임에 아이템과 무게를 읽을 수 있습니다
• 배열의 항목 수에 비례하는 메모리 사용량

대조 :

• 제대로 작동하려면 더 많은 프로그래밍이 필요합니다
• 최악의 경우 전체 배열을 반복해야합니다 ( O(n)런타임 복잡성). 따라서 매우 큰 아이템 세트를 가지고 매우 자주 그리면 느려질 수 있습니다. 간단한 최적화는 가장 가능성이 높은 항목을 먼저 배치하여 알고리즘이 대부분의 경우 일찍 종료되도록하는 것입니다. 더 복잡한 최적화는 배열이 정렬되어 이분법 검색을 수행한다는 사실을 이용하는 것입니다. O(log n)시간 이 걸립니다 .
• 사용하기 전에 메모리에 목록을 작성해야합니다 (런타임에 항목을 쉽게 추가 할 수 있지만 항목 제거도 추가 할 수 있지만 제거 된 항목 뒤에 오는 모든 항목의 누적 가중치를 업데이트해야합니다. 다시 O(n)최악의 경우 런타임이 있습니다)

답변

         WeightedRandomizer 벤치 마크 | 나무 | 표
-------------------------------------------------- ---------------------------------
Add () x10000 + NextWithReplacement () x10 : | 4ms | 2ms
Add () x10000 + NextWithReplacement () x10000 : | 7ms | 4ms
Add () x10000 + NextWithReplacement () x100000 : | 35ms | 28ms
(Add () + NextWithReplacement ()) x10000 (인터리브 된) | 8ms | 5403ms
Add () x10000 + NextWithRemoval () x10000 : | 10ms | 5948ms

10 gold
sword
sword
sword
sword
shield
shield
shield
shield
shield
shield
shield
armor
armor
armor
armor
potion
potion

int rand = random(100); //Random number between 1 and 100 (inclusive)
if(rand <= 5) //5% chance
{
    print("You found 10 gold!");
}
else if(rand <= 25) //20% chance
{
    print("You found a sword!");
}
else if(rand <= 70) //45% chance
{
    print("You found a shield!");
}
else if(rand <= 90) //20% chance
{
    print("You found armor!");
}
else //10% chance
{
    print("You found a potion!");
}

var item = a.Select(x =>
{
    sum += x.prob;
    if (rand < sum)
        return x.item;
    else
        return null;
 }).FirstOrDefault());

for X in items’range loop
  If items (X).threshold < random() then
     Announce (items(X).name)
     Exit loop
  End if
End loop

on_normal_case([5,20,45,20,10],0)

item_array[on_normal_case([5,20,45,20,10],0)]

item_function(on_normal_case([5,20,45,20,10],0))

func on_normal_case(arrayy,transformm):
    var random_num=0
    var sum=0
    var summatut=0
    #func sumarrays_inarray(array):
    for i in range(arrayy.size()):
        sum=sum+arrayy[i]
#func no_fixu_random_num(here_range,start_from):
    random_num=randi()%sum+1
#Randomies be pressed down
#first start from zero
    if 0<=random_num and random_num<=arrayy[0]:
        #print(random_num)
        #print(array[0])
        return 0+ transformm
    summatut=summatut+arrayy[0]
    for i in range(arrayy.size()-1):
        #they must pluss together
        #if array[i]<=random_num and random_num<array[i+1]:
        if summatut<random_num and random_num<=summatut+arrayy[i+1]:
            #return i+1+transform
            #print(random_num)
            #print(summatut)
            return i+1+ transformm

        summatut=summatut+arrayy[i+1]
    pass