问题不太可能是您展示的循环：
设 n 为分布的大小，I 为 getNextSample 调用次数。我们有 I = sum_i(C_i)，其中 C_i 是在集合大小为 i 时 getNextSample 的调用次数。要找到 E[C_i]，观察到 C_i 是具有 λ = 1 - i / n 的 泊松过程 的到达间隔时间，因此具有 指数分布 λ。因此，E[C_i] = 1/λ = 因此 E[C_i] = 1 / (1 - i / n) <= 1 / (1 - m / n)。因此，E[I] < m / (1 - m / n)。
即，抽取一个大小为m = n/2的集合将平均只需要不到2m = n次调用getNextSample。如果这很“慢”且“缓慢”，那可能是因为getNextSample很慢。这实际上并不奇怪，因为分布以不适当的方式传递给方法（因为方法必须必然遍历整个分布以找到随机元素）。
如果m < 0.8n，则以下应该更快速。
class Distribution<T> {
private double[] cummulativeWeight;
private T[] item;
private double totalWeight;
Distribution(Map<T, Double> probabilityMap) {
int i = 0;
cummulativeWeight = new double[probabilityMap.size()];
item = (T[]) new Object[probabilityMap.size()];
for (Map.Entry<T, Double> entry : probabilityMap.entrySet()) {
item[i] = entry.getKey();
totalWeight += entry.getValue();
cummulativeWeight[i] = totalWeight;
i++;
}
}
T randomItem() {
double weight = Math.random() * totalWeight;
int index = Arrays.binarySearch(cummulativeWeight, weight);
if (index < 0) {
index = -index - 1;
}
return item[index];
}
Set<T> randomSubset(int size) {
Set<T> set = new HashSet<>();
while(set.size() < size) {
set.add(randomItem());
}
return set;
}
}
public class Test {
public static void main(String[] args) {
int max = 1_000_000;
HashMap<Integer, Double> probabilities = new HashMap<>();
for (int i = 0; i < max; i++) {
probabilities.put(i, (double) i);
}
Distribution<Integer> d = new Distribution<>(probabilities);
Set<Integer> set = d.randomSubset(max / 2);
}
}
预期运行时间为 O(m / (1 - m / n) * log n)。在我的电脑上，对于一个大小为 1,000,000 的集合的子集大小为 500,000，计算大约需要 3 秒钟。
正如我们所看到的，当 m 接近 n 时，预期运行时间趋近于无穷大。如果这是一个问题（即 m > 0.9n），则以下更复杂的方法应该效果更好：
Set<T> randomSubset(int size) {
Set<T> set = new HashSet<>();
while(set.size() < size) {
T randomItem = randomItem();
remove(randomItem);
set.add(randomItem);
}
return set;
}
为了高效地实现 remove，需要使用不同的分布表示，例如二叉树，每个节点存储其根节点下子树的总权重。
但这相当复杂，因此如果 m 明显小于 n，则不建议采用该方法。
