我想有一组和具有其元素具有与它们相关联的概率，所以当我挑选的元件在从所述一组随机的，则分布遵循与所述元件相关联的概率。 我想用在存储电影我想看这样的列表，一个非常小的Java应用程序，我可以把它提出一个随机的电影给我（我总是需要几个小时才能挑选影片以其他方式）。 每部电影我想时代的电影是向我建议，这将是成反比的是，影片从列表中挑选下一个建议的概率号关联。
是否有允许随机挑选从它的元素具有非均匀分布的数据结构？
如果没有，什么是写这样的数据结构的最有效的方法是什么？ 我当然可以随时创建数组，把列表的每一个元素放入数组往往足以使值的数组中的分配我希望他们有概率相匹配，并挑选从阵列中的随机元素; 但大集的电影，那会是非常低效的。 另一个想法我不得不被包封元件和所有元素起来的概率的给它的总和（从而第一元件将被封装为（第一，第（第一）），第二个为（第二，第（第二）+ P（第一））等），然后选择在0和1之间的随机数，并做那些包封元素的排序列表中的二进制搜索。 这是否健全合理的？
TL：DR（和有些抽象）：我怎么映射的非均匀分布的在Java中有效地设置的元素？
不知道我理解的问题是正确的。 我会用一个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
Double probability = Math.random(); // between 0 (inclusive) and 1.0 (exclusive)
Movie chosen = movies.higherEntry(probability).getValue();
我将离开概率的人口和重新安排给你。
有一个叫“别名法”酷法，允许在O（1）采摘。 Beutifully这里解释： http://pandasthumb.org/archives/2012/08/lab-notes-the-a.html
我会简单地定义：
class Movie {
int recommendations;
}
然后做
public Movie chooseMovie(ArrayList<Movie> movies) {
Random rand = new Random();
int sum = 0;
for(Movie movie : movies) {
sum += movie.recommendations;
}
int choice = rand.nextInt(sum);
int soFar = 0;
for(Movie movie : movies) {
soFar += movie.recommendations;
if(choice < soFar) {
return movie;
}
}
return null;
}
选择变量更可能落在电影的推荐范围之内，如果该范围较大。 它很慢，但在实践中的电影数量，可能是足够小，它为你工作的罚款。 如果你做了很多的查找，您可以缓存的总推荐统计和增量总和，类似你建议的方式。
public Movie chooseMovie(ArrayList<Movie> movies) {
Random rand = new Random();
double sum = 0;
for(Movie movie : movies) {
if(movie.recommendations > 0) {
sum += 1 / (double) (movie.recommendations);
}
}
int choice = rand.nextDouble() * sum;
double soFar = 0;
for(Movie movie : movies) {
if(movie.recommendations > 0) {
soFar += 1 / (double) (movie.recommendations);
if(choice < soFar) {
return movie;
}
}
}
return null;
}
