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




random (5)

इस प्रश्न का उत्तर यहां दिया गया है:

जावा में, दिए गए एन आइटम, वजन वाले प्रत्येक के साथ, संग्रह से एक यादृच्छिक आइटम कैसे चुनता है जिसके साथ डब्ल्यू बराबर होता है?

मान लें कि प्रत्येक वजन 0.0 से 1.0 तक दोगुना है, और संग्रह में वजन 1 तक है। Item.getWeight () आइटम का वजन देता है।


  1. वस्तुओं को कुछ मनमाने ढंग से आदेश दें ... (i1, i2, ..., में) ... वजन w1, w2, ..., wn के साथ।
  2. 0 और 1 के बीच एक यादृच्छिक संख्या चुनें (पर्याप्त ग्रैन्युलरिटी के साथ, किसी भी यादृच्छिक समारोह और उपयुक्त स्केलिंग का उपयोग करके)। इस आर 0 को बुलाओ।
  3. चलो जे = 1
  4. आरजे प्राप्त करने के लिए अपने आर (जे -1) से wj घटाएं। अगर आरजे <= 0, तो आप आइटम ij का चयन करें। अन्यथा, वृद्धि जे और दोहराना।

मुझे लगता है कि मैंने इसे पहले ऐसा किया है ... लेकिन ऐसा करने के लिए शायद अधिक कुशल तरीके हैं।


TreeMap आपके लिए पहले से ही सभी काम करता है।

एक TreeMap बनाएँ। अपनी पसंद की विधि के आधार पर वजन बनाएं। अपने चलने वाले वजन काउंटर पर अंतिम तत्व का वजन जोड़ते समय 0.0 से शुरू होने वाले वजन जोड़ें।

यानी (स्कैला):

var count = 0.0  
for { object <- MyObjectList } { //Just any iterator over all objects 
  map.insert(count, object) 
  count += object.weight
}

फिर आपको केवल rand = new Random(); num = rand.nextDouble() * count उत्पन्न करना होगा rand = new Random(); num = rand.nextDouble() * count rand = new Random(); num = rand.nextDouble() * count मान्य संख्या प्राप्त करने के लिए rand = new Random(); num = rand.nextDouble() * count करें।

map.to(num).last  // Scala
map.floorKey(num) // Java

आपको यादृच्छिक भारित वस्तु देगा।

बाल्टी की छोटी मात्रा के लिए भी संभव है: 100,000 इंट की सरणी बनाएं और खेतों में वजन के आधार पर बाल्टी की संख्या वितरित करें। फिर आप 0 और 100,000-1 के बीच एक यादृच्छिक इंटीजर बनाते हैं और आपको तुरंत बाल्टी-संख्या वापस मिलती है।


एक शानदार तरीका एक घातीय वितरण का नमूना देना होगा http://en.wikipedia.org/wiki/Exponential_distribution जहां वजन वितरण (लैम्ब्डा) की दर होगी। अंत में, आप बस सबसे छोटा नमूना मूल्य का चयन करें।

जावा में ऐसा लगता है:

public static <E> E getWeightedRandom(Map<E, Double> weights, Random random) {
    E result = null;
    double bestValue = Double.MAX_VALUE;

    for (E element : weights.keySet()) {
        double value = -Math.log(random.nextDouble()) / weights.get(element);

        if (value < bestValue) {
            bestValue = value;
            result = element;
        }
    }

    return result;
}

मुझे यकीन नहीं है कि यह अन्य दृष्टिकोणों की तुलना में अधिक कुशल है, लेकिन यदि निष्पादन का समय मुद्दा नहीं है, तो यह एक अच्छी तरह से दिखने वाला समाधान है।

और यह जावा 8 और स्ट्रीम का उपयोग कर एक ही विचार है:

public static <E> E getWeightedRandomJava8(Stream<Entry<E, Double>> weights, Random random) {
    return weights
        .map(e -> new SimpleEntry<E,Double>(e.getKey(),-Math.log(random.nextDouble()) / e.getValue()))
        .min((e0,e1)-> e0.getValue().compareTo(e1.getValue()))
        .orElseThrow(IllegalArgumentException::new).getKey();
}

उदाहरण के लिए आप इनपुट वेट्स स्ट्रीम प्राप्त कर सकते हैं उदाहरण के लिए .entrySet().stream() साथ इसे परिवर्तित करके।


नीचे एक यादृच्छिकता है जो अनुपात में सटीकता को भी बनाए रखती है:

public class WeightedRandomizer
{
    private final Random randomizer;

    public WeightedRandomizer(Random randomizer)
    {
        this.randomizer = randomizer;
    }

    public IWeighable getRandomWeighable(List<IWeighable> weighables)
    {
        double totalWeight = 0.0;
        long totalSelections = 1;
        List<IWeighable> openWeighables = new ArrayList<>();

        for (IWeighable weighable : weighables)
        {
            totalWeight += weighable.getAllocation();
            totalSelections += weighable.getNumSelections();
        }

        for(IWeighable weighable : weighables)
        {
            double allocation = weighable.getAllocation() / totalWeight;
            long numSelections = weighable.getNumSelections();
            double proportion = (double) numSelections / (double) totalSelections;

            if(proportion < allocation)
            {
                openWeighables.add(weighable);
            }
        }

        IWeighable selection = openWeighables.get(this.randomizer.nextInt(openWeighables.size()));
        selection.setNumSelections(selection.getNumSelections() + 1);
        return selection;
    }
}

Item[] items = ...;

// Compute the total weight of all items together
double totalWeight = 0.0d;
for (Item i : items)
{
    totalWeight += i.getWeight();
}
// Now choose a random item
int randomIndex = -1;
double random = Math.random() * totalWeight;
for (int i = 0; i < items.length; ++i)
{
    random -= items[i].getWeight();
    if (random <= 0.0d)
    {
        randomIndex = i;
        break;
    }
}
Item myRandomItem = items[randomIndex];





random