从非均匀分布的集合中选取随机元素？ [英] Pick random element from set with non-uniform distribution?

问题描述

我想要一个集合，并且其元素具有与它们相关联的概率，所以当我从集合中随机选择一个元素时，分布遵循与元素相关联的概率。我想在一个非常小的Java应用程序中使用，它存储我想要看的电影列表，所以我可以给我一个随机的电影（我总是需要几个小时选择一个电影）。每个电影我都想把电影的次数与我建议的次数相关联，这与电影从下一个建议列表中选出的概率成反比。

是否有一个数据结构可以随机采用不均匀分布的元素？

如果没有，最有效的写法方式是什么数据结构？我当然可以随时建立一个数组，将列表中的每一个元素都放到数组中，这样数组中的值的分布与我想要的可能性相匹配，并从该数组中选择一个随机元素;但是对于大型电影来说，这将是非常低效的。另一个想法是将元素和所有元素的概率之和封装在一起（因此第一个元素将被封装为（第一个，第（p）个），第二个为（第二个，第（p）个）第一））等等），然后选择0到1之间的随机数，并对这些封装元素的排序列表进行二进制搜索。这是否合理？

TL：DR（有点抽象）：如何在Java中有效地将不均匀的分布映射到集合的元素？ p>

解决方案

不知道我理解的问题是正确的。我将使用 TreeMap< Double，Movie> 。

示例：让我们说你有电影A（60％ ），电影B（30％）和电影C（10％）。

  TreeMap< Double，Movie> movies = new TreeMap<>（）; 
 movies.put（0.6，new Movie（Movie A））; 
 movies.put（0.9，new Movie（Movie B））; // 0.6 + 0.3 
 movies.put（1.0，new Movie（Movie C））; // 0.6 + 0.3 + 0.1 
双重概率= Math.random（）; //在0（含）和1.0（独占）之间
选择的电影= movies.higherEntry（概率）.getValue（）; 
  

我将离开人口并重新排列可能性。

I would like to have a set and have its elements have probabilities associated with them, so when I pick an element at random from the set, the distribution follows the probabilities associated with the elements. I would like to use that in a very small Java application that stores a list of movies I want to watch so I can have it suggest a random movie to me (I always take hours to pick a movie otherwise). With each movie I want to associate the number of times the movie was suggested to me, which will be inversely proportionate to the probability that the movie is picked from the list for the next suggestion.

Is there a data structure that allows picking elements from it at random with a non-uniform distribution?

If not, what's the most efficient way of writing such a data structure? I could of course always build an array, put every element of the list into the array often enough so the distribution of values in the array matches up the probabilities I want them to have, and pick a random element from that array; but for large sets of movies, that's gonna be terribly inefficient. Another idea I had was encapsulating the element and the sum of probabilities of all elements up to it (so the first element would be encapsulated as (first, p(first)), the second as (second, p(second) + p(first)) and so on), then pick a random number between 0 and 1 and do a binary search on a sorted list of those encapsulated elements. Does that sound sensible?

TL:DR (and somewhat abstract): how do I map a non-uniform distribution to the elements of a set efficiently in Java?

解决方案

Not sure I understood the question correct. I would use a TreeMap<Double, Movie>.

Example: lets say you have Movie A (60 %), Movie B (30 %) and Movie C (10 %).

TreeMap<Double, Movie> movies = new TreeMap<>();
movies.put(0.6, new Movie("Movie A"));
movies.put(0.9, new Movie("Movie B")); // 0.6 + 0.3
movies.put(1.0, new Movie("Movie C")); // 0.6 + 0.3 + 0.1
Double probability = Math.random(); // between 0 (inclusive) and 1.0 (exclusive)
Movie chosen = movies.higherEntry(probability).getValue();

I'll leave the population and rearranging of the probabilities up to you.

这篇关于从非均匀分布的集合中选取随机元素？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！