1

我想要一个集合，并且它的元素具有与之关联的概率，所以当我从集合中随机选择一个元素时，分布遵循与元素关联的概率。我想在一个非常小的 Java 应用程序中使用它，该应用程序存储了我想看的电影列表，这样我就可以让它向我推荐一部随机电影（否则我总是要花几个小时来挑选一部电影）。对于每部电影，我想关联向我推荐电影的次数，这将与从列表中选择电影以进行下一个建议的概率成反比。

是否有一种数据结构允许从其中随机选取元素且分布不均匀？

如果不是，那么编写这种数据结构的最有效方法是什么？我当然可以始终构建一个数组，将列表中的每个元素经常放入数组中，以便数组中值的分布与我希望它们具有的概率相匹配，并从该数组中选择一个随机元素；但是对于大型电影来说，这将是非常低效的。我的另一个想法是封装元素和所有元素的概率总和（所以第一个元素将被封装为（first，p（first）），第二个元素被封装为（second，p（second）+ p（首先））等等），然后选择一个介于 0 和 1 之间的随机数，并在这些封装元素的排序列表上进行二进制搜索。这听起来合理吗？

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

4

3 回答 3

5

不确定我是否正确理解了这个问题。我会用一个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();

我将把人口和概率的重新排列留给你。

于 2013-02-16T22:48:30.547 回答
3

有一种很酷的方法称为“别名方法”，它可以在 O(1) 中进行选择。在这里得到了很好的解释： http ://pandasthumb.org/archives/2012/08/lab-notes-the-a.html

于 2013-05-03T12:36:59.577 回答
2

我会简单地定义：

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;
}
于 2013-02-16T22:58:46.057 回答