从一个顺序集合中获取一个随机元素。

Question

我使用一个API与集合交互，它返回一个java.util.Iterator，这意味着我可以遍历它，但无法直接/随机访问元素。

现在我的问题是：我想从集合中获取一个随机元素。我该怎么办？我猜我可以构建一个允许直接访问的新集合，但那不会占用一些内存吗？我也可以遍历整个集合，并为每个元素“roll a dice”，以查看是否应该取该元素并退出迭代或继续。但是我需要知道集合的大小，而我无法从Iterator获得这个信息。

预先感谢。

- Sven

---

集合通常不应该是实现Iterator接口的类。 - thejh

你的集合是 java.util.Collection 吗？ - thejh

内存消耗不应该太大。新的集合只保存指向实际数据的指针，因此新集合对象的大小!=集合的大小。 - Jonathan B

在病态情况下，集合可能包含许多重复的元素或null，这可能会使得集合的ArrayList相对较大。 - Tom Hawtin - tackline

@thejh 这是我笨拙的写作，感谢您提醒。我已更新了问题。 - Sven

Answer 1

有一种方法可以在集合中一次遍历就完成，而且不会使用过多的额外内存（只需要一个元素的大小和一个浮点数）。伪代码如下：

• 遍历集合。
• 对于每个项目，生成一个随机浮点数。
• 如果该浮点数是到目前为止最低（或最高）的一个，将当前集合中的项目存储在临时变量中。（同时存储新的最低随机值。）
• 一旦到达集合的末尾，您就有了一个随机项目存储在临时变量中。

显然，这种方法的缺点是每次调用都需要遍历整个集合，但是在面对您所面临的限制时，您没有太多选择。

更新：我终于想起来这类问题的名称了。这被称为蓄水池抽样算法。

- Bill the Lizard

---

与我的解决方案基本相同（除了我不使用浮点数（顺便说一下，整数会更好））。 - Tom Hawtin - tackline

@Bill the Lizard，使用int类型可以为给定位数提供更大的值范围。不必处理所有那些IEEE规范。 - Tom Hawtin - tackline

@Tom：哦，原来是这样。我还以为你会给我介绍一些关于“Random”类的奥秘，让我大开眼界呢。 :) - Bill the Lizard

我所说的更高，实际上是更低 :-) （或更高，就像您的答案所建议的那样） - Dean Povey

如果你阅读答案链接的维基百科页面，你会看到在迭代过程中，你必须降低每个答案被选为最终选择的概率。否则就会在迭代顺序的末尾产生偏差。 - vladimir e.

Answer 2

在迭代时，您知道迭代了多少个对象，因此您知道当前元素是随机选择的概率。因此，您只需要保持计数和当前随机选择的项。

public static <T> T selectRandom(final Iterator<T> iter, final Random random) {
    if (!iter.hasNext()) {
        throw new IllegalArgumentException();
    }
    if (random == null) {
        throw new NullPointerException();
    }
    T selected = iter.next();
    int count = 1;
    while (iter.hasNext()) {
        final T current = iter.next();
        ++count;
        if (random.nextInt(count) == 0) {
            selected = current;
        }
    }
    return selected;
}

（Stack Overflow免责声明：未编译，当然也未经测试。）

请参阅Java Puzzlers中关于Collections.shuffle的部分。

- Tom Hawtin - tackline

---

我不知道这是如何随机的：每次迭代，random.nextInt(count) == 0 的概率都会越来越低。 - Denis Tulskiy

@tulskly 是的，当你到达第十个元素时，它被选中的概率就是1/10。 - Tom Hawtin - tackline

@thejh 第一个元素在代码中是一个特殊情况。（虽然可以在循环内完成，但那会是糟糕的代码。） - Tom Hawtin - tackline

你可能需要再思考一下。对于每个下一个元素，都有先前选择的项目被替换的可能性。结果是公平的。 - Tom Hawtin - tackline

好的，谢谢你的提示，我会看一下的。有点困惑，因为一个集合没有任何起始或最后的元素。 - voho

Answer 3

如果没有更多信息被知道或保证，唯一安全的解决方案是您所描述的方式：从迭代器创建一个列表并选择一个随机元素。

如果底层集合的大小始终相同，则可以通过平均减少一半的工作量 - 只需在随机迭代次数后使用Iterator.next()获得的元素即可。

顺便说一句：您真的在使用实现了java.util.Iterator的集合吗？

- MRalwasser

Answer 4

这取决于需求，如果集合的大小不是很大，那么这样做就可以了，否则您应该迭代并使用您提到的骰子方法。

List<Object> list = Arrays.asList(yourCollection.toArray(new Object[0]));
result = list.get(new Random().nextInt(list.size()));

- Bence Olah

Answer 5

用这个来生成加权测试数据。虽然不是很高效，但很容易使用。

class ProbabilitySet<E> {

    Set<Option<E>> options =  new HashSet<Option<E>>(); 

    class Option<E> {
        E object;
        double min;
        double max;

        private Option(E object, double prob) {
            this.object = object;
            min = totalProb;
            max = totalProb + prob;
        }

        @Override
        public String toString() {
            return "Option [object=" + object + ", min=" + min + ", max=" + max + "]";
        }
    }

    double totalProb = 0;
    Random rnd = new Random();

    public void add(E object, double probability){
        Option<E> tuple = new Option<E>(object, probability);
        options.add(tuple);
        totalProb += probability;
    }

    public E getRandomElement(){

        double no = rnd.nextDouble() * totalProb;
        for (Option<E> tuple : options) {
            if (no >= tuple.min && no < tuple.max){
                return tuple.object;
            }
        }


        return null;  // if this happens sumfink is wrong.

    }

    @Override
    public String toString() {
        return "ProbabilitySet [options=" + options + ", totalProb=" + totalProb + "]";
    }

}

注意：概率参数将与总数相关，而不是1.0。

用法：

public static void main(String[] args) {
    ProbabilitySet<String> stati = new ProbabilitySet<String>();
    stati.add("TIMEOUT", 0.2);
    stati.add("FAILED", 0.2);
    stati.add("SUCCESSFUL", 1.0);

    for (int i = 0; i < 100; i++) {
        System.out.println(stati.getRandomElement());
    }

}

- Jablub

Answer 6

如果你真的没有任何随机访问，并且你有一个非常大的列表，所以你不能复制它，那么你可以采取以下措施：

int n = 2
iterator i = ...
Random rand = new Random();
Object candidate = i.next();
while (i.hasNext()) {
    if (rand.nextInt(n)) {
        candidate = i.next();
    } else {
        i.next();
    }
    n++;
}
return candidate;

这将保留列表中的一个随机元素，但需要遍历整个列表。如果您想要一个真正均匀分布的值，那么您别无选择。

或者，如果项目数量很少，或者如果您想要一个未知大小的列表的随机排列（换句话说，您想以随机顺序访问列表的所有元素），那么我建议将所有引用复制到新列表中（这不会占用大量内存，除非您有数百万个项目，因为您只存储引用）。然后使用随机整数使用get方法或使用标准java.util.Collections shuffle方法对列表进行排列。

- Dean Povey

---

和我的解决方案非常相似。 - Tom Hawtin - tackline

是的。我在打字的时候，你添加了它 :-)。 - Dean Povey