java - जावा में यादृच्छिक भारित चयन




random double (4)

मैं एक सेट से एक यादृच्छिक आइटम चुनना चाहता हूं, लेकिन किसी भी आइटम को चुनने का मौका संबंधित वजन के आनुपातिक होना चाहिए

उदाहरण इनपुट:

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

इसलिए, यदि मेरे पास 4 संभव वस्तुएं हैं, तो वजन के बिना किसी भी आइटम को प्राप्त करने का मौका 4 में 1 होगा।

इस मामले में, उपयोगकर्ता को तिहाई तलवार की तुलना में दुःख की तलवार पाने की संभावना 10 गुना अधिक होनी चाहिए।

मैं जावा में भारित यादृच्छिक चयन कैसे करूं?


उपनाम विधि का प्रयोग करें

यदि आप कई बार रोल (जैसे एक गेम में) रोल करने वाले हैं, तो आपको उपनाम विधि का उपयोग करना चाहिए।

नीचे दिया गया कोड वास्तव में इस तरह के उपनाम विधि के लंबे कार्यान्वयन है। लेकिन यह प्रारंभिक भाग के कारण है। तत्वों की पुनर्प्राप्ति बहुत तेज है ( next और लागू करें applyAsInt तरीकों को देखें जिन्हें वे लूप नहीं करते हैं)।

प्रयोग

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

Random random = new Random();

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

कार्यान्वयन

यह कार्यान्वयन:

  • जावा 8 का उपयोग करता है;
  • जितनी जल्दी संभव हो सके डिजाइन किया गया है (ठीक है, कम से कम, मैंने माइक्रो-बेंचमार्किंग का उपयोग करके ऐसा करने की कोशिश की);
  • पूरी तरह से थ्रेड-सुरक्षित है (अधिकतम प्रदर्शन के लिए प्रत्येक धागे में एक Random रखें, ThreadLocalRandom उपयोग करें?);
  • 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];
      }
    }
  }
}

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()));
}

या जावा 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 नहीं।


मैं एक 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());
} 

यदि आपको चुनने के बाद तत्वों को हटाने की आवश्यकता है तो आप एक और समाधान का उपयोग कर सकते हैं। सभी तत्वों को 'लिंक्डलिस्ट' में जोड़ें, प्रत्येक तत्व को वज़न जितनी बार जोड़ा जाना चाहिए, फिर Collections.shuffle() JavaDoc Collections.shuffle() उपयोग करें, जो JavaDoc अनुसार

यादृच्छिकता के डिफ़ॉल्ट स्रोत का उपयोग करके निर्दिष्ट सूची को यादृच्छिक रूप से अनुमति देता है। सभी क्रमपरिवर्तन लगभग समान संभावना के साथ होते हैं।

अंत में, 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());
}





double