자바에서 무작위 선택

자바에서 무작위 선택

---

세트에서 임의의 아이템을 선택하고 싶지만 아이템을 선택할 확률은 관련 무게에 비례해야합니다

입력 예 :

item                weight
----                ------
sword of misery         10
shield of happy          5
potion of dying          6
triple-edged sword       1

따라서 4 개라면 가능성이 있습니다.

이 경우 사용자는 삼 날검보다 불행의 검을 얻을 확률이 10 배 더 있습니다.

Java에서 선택 기반 선택을 어디에서 선택합니까?

---

NavigableMap을 사용합니다.

public class RandomCollection<E> {
    private final NavigableMap<Double, E> map = new TreeMap<Double, E>();
    private final Random random;
    private double total = 0;

    public RandomCollection() {
        this(new Random());
    }

    public RandomCollection(Random random) {
        this.random = random;
    }

    public RandomCollection<E> add(double weight, E result) {
        if (weight <= 0) return this;
        total += weight;
        map.put(total, result);
        return this;
    }

    public E next() {
        double value = random.nextDouble() * total;
        return map.higherEntry(value).getValue();
    }
}

확률이 각각 40 %, 35 %, 25 % 인 개, 고양이, 말의 동물 목록이 가정 해 보겠습니다.

RandomCollection<String> rc = new RandomCollection<>()
                              .add(40, "dog").add(35, "cat").add(25, "horse");

for (int i = 0; i < 10; i++) {
    System.out.println(rc.next());
} 

---

요청 된 기능은 단순한 기능에 지나지 많은 종류의 문제에 대한 프레임 워크를 사용할 수 없습니다. 다음과 같이하십시오.

interface Item {
    double getWeight();
}

class RandomItemChooser {
    public Item chooseOnWeight(List<Item> items) {
        double completeWeight = 0.0;
        for (Item item : items)
            completeWeight += item.getWeight();
        double r = Math.random() * completeWeight;
        double countWeight = 0.0;
        for (Item item : items) {
            countWeight += item.getWeight();
            if (countWeight >= r)
                return item;
        }
        throw new RuntimeException("Should never be shown.");
    }
}

---

이제 Apache Commons : EnumeratedDistribution 에 이에 대한 클래스가 있습니다.

Item selectedItem = new EnumeratedDistribution(itemWeights).sample();

어디 itemWeights인 List<Pair<Item,Double>>(아르네의 대답에 항목 인터페이스를 가정)과 같은 :

List<Pair<Item,Double>> itemWeights = Collections.newArrayList();
for (Item i : itemSet) {
    itemWeights.add(new Pair(i, i.getWeight()));
}

또는 Java 8에서

itemSet.stream().map(i -> new Pair(i, i.getWeight())).collect(toList());

참고 : Pair여기에있을 필요가 org.apache.commons.math3.util.Pair없습니다 org.apache.commons.lang3.tuple.Pair.

---

사용 방법

(게임에서와 같이) 여러 번 굴려야하는 방법을 많이 사용합니다.

아래 코드는 실제로 호출 방식의 다소 긴 구현입니다. 그러나 초기화 초기화 부분 때문입니다. 요소 검색은 매우 빠릅니다 ( next및 applyAsInt반복되지 않는 메서드 참조 ).

용법

Set<Item> items = ... ;
ToDoubleFunction<Item> weighter = ... ;

Random random = new Random();

RandomSelector<T> selector = RandomSelector.weighted(items, weighter);
Item drop = selector.next(random);

이행

이 구현 :

• Java 8을 사용합니다 .
• 한 빠르게 가능한 설계되었습니다 (적어도 마이크로 벤치마킹을 사용하여 시도했습니다).
• 로부터 스레드 완전히 안전합니다 (
  Random최대 성능을 위해 각 스레드에 하나씩 유지하고 ThreadLocalRandom? 사용 ).
• O (n) 또는 O (log (n))에서 순진한 구현이 실행되는 인터넷이나 StackOverflow에서 주로 찾는 것과 달리 O (1)의 요소를 가져옵니다 .
• 을 가중치 항목 와 독립적으로 유지하므로 항목 에 다른 컨텍스트에서 다양한 가중치를 할당 할 수 있습니다.

어쨌든 여기에 코드가 있습니다. ( 이 수업의 최신 버전을 유지하고 있습니다.)

import static java.util.Objects.requireNonNull;

import java.util.*;
import java.util.function.*;

public final class RandomSelector<T> {

  public static <T> RandomSelector<T> weighted(Set<T> elements, ToDoubleFunction<? super T> weighter)
      throws IllegalArgumentException {
    requireNonNull(elements, "elements must not be null");
    requireNonNull(weighter, "weighter must not be null");
    if (elements.isEmpty()) { throw new IllegalArgumentException("elements must not be empty"); }

    // Array is faster than anything. Use that.
    int size = elements.size();
    T[] elementArray = elements.toArray((T[]) new Object[size]);

    double totalWeight = 0d;
    double[] discreteProbabilities = new double[size];

    // Retrieve the probabilities
    for (int i = 0; i < size; i++) {
      double weight = weighter.applyAsDouble(elementArray[i]);
      if (weight < 0.0d) { throw new IllegalArgumentException("weighter may not return a negative number"); }
      discreteProbabilities[i] = weight;
      totalWeight += weight;
    }
    if (totalWeight == 0.0d) { throw new IllegalArgumentException("the total weight of elements must be greater than 0"); }

    // Normalize the probabilities
    for (int i = 0; i < size; i++) {
      discreteProbabilities[i] /= totalWeight;
    }
    return new RandomSelector<>(elementArray, new RandomWeightedSelection(discreteProbabilities));
  }

  private final T[] elements;
  private final ToIntFunction<Random> selection;

  private RandomSelector(T[] elements, ToIntFunction<Random> selection) {
    this.elements = elements;
    this.selection = selection;
  }

  public T next(Random random) {
    return elements[selection.applyAsInt(random)];
  }

  private static class RandomWeightedSelection implements ToIntFunction<Random> {
    // Alias method implementation O(1)
    // using Vose's algorithm to initialize O(n)

    private final double[] probabilities;
    private final int[] alias;

    RandomWeightedSelection(double[] probabilities) {
      int size = probabilities.length;

      double average = 1.0d / size;
      int[] small = new int[size];
      int smallSize = 0;
      int[] large = new int[size];
      int largeSize = 0;

      // Describe a column as either small (below average) or large (above average).
      for (int i = 0; i < size; i++) {
        if (probabilities[i] < average) {
          small[smallSize++] = i;
        } else {
          large[largeSize++] = i;
        }
      }

      // For each column, saturate a small probability to average with a large probability.
      while (largeSize != 0 && smallSize != 0) {
        int less = small[--smallSize];
        int more = large[--largeSize];
        probabilities[less] = probabilities[less] * size;
        alias[less] = more;
        probabilities[more] += probabilities[less] - average;
        if (probabilities[more] < average) {
          small[smallSize++] = more;
        } else {
          large[largeSize++] = more;
        }
      }

      // Flush unused columns.
      while (smallSize != 0) {
        probabilities[small[--smallSize]] = 1.0d;
      }
      while (largeSize != 0) {
        probabilities[large[--largeSize]] = 1.0d;
      }
    }

    @Override public int applyAsInt(Random random) {
      // Call random once to decide which column will be used.
      int column = random.nextInt(probabilities.length);

      // Call random a second time to decide which will be used: the column or the alias.
      if (random.nextDouble() < probabilities[column]) {
        return column;
      } else {
        return alias[column];
      }
    }
  }
}

---

public class RandomCollection<E> {
  private final NavigableMap<Double, E> map = new TreeMap<Double, E>();
  private double total = 0;

  public void add(double weight, E result) {
    if (weight <= 0 || map.containsValue(result))
      return;
    total += weight;
    map.put(total, result);
  }

  public E next() {
    double value = ThreadLocalRandom.current().nextDouble() * total;
    return map.ceilingEntry(value).getValue();
  }
}

---

선택한 후 요소를 제거해야하는 경우 다른 솔루션을 사용할 수 있습니다. 모든 요소를 ​​'LinkedList'에 추가합니다. 각 요소는 다음만큼 추가 된 다음 JavaDocCollections.shuffle() 에 따라 사용합니다.

기본 임의성 소스를 사용하여 지정된 목록을 무작위로 순열합니다. 모든 순열은 거의 동일한 가능성으로 발생합니다.

마지막으로 pop()또는 사용하여 요소를 가져오고 제거합니다.removeFirst()

Map<String, Integer> map = new HashMap<String, Integer>() {{
    put("Five", 5);
    put("Four", 4);
    put("Three", 3);
    put("Two", 2);
    put("One", 1);
}};

LinkedList<String> list = new LinkedList<>();

for (Map.Entry<String, Integer> entry : map.entrySet()) {
    for (int i = 0; i < entry.getValue(); i++) {
        list.add(entry.getKey());
    }
}

Collections.shuffle(list);

int size = list.size();
for (int i = 0; i < size; i++) {
    System.out.println(list.pop());
}

---

139

무작위로 항목을 선택하는 간단한 알고리즘이 있으며 항목에는 개별 가중치가 있습니다.

1. 모든 가중치의 합을 계산

2. 0 이상이고 가중치의 합보다 작은 임의의 숫자를 선택하십시오.

3. 한 번에 하나씩 항목을 살펴보고 난수가 해당 항목의 무게보다 작은 항목을 얻을 때까지 임의의 숫자에서 가중치를 뺍니다.

참고 URL : https://stackoverflow.com/questions/6409652/random-weighted-selection-in-java