我需要从一个列表，即满足一定的条件选择一个随机元素。这种方法我一直在使用的作品，但我敢肯定，是不是每一个有效率。什么是最有效的方法来做到这一点？

I need to pick a random element from a list, that fulfills certain condition. The approach I've been using works, but I'm sure is not every efficient. What would be the most efficient way to do it?

下面code是一个，而（真）循环中，所以很明显不是很有效的洗牌在每个迭代的列表中。

The following code is inside a while (true) loop, so obviously is not very efficient to shuffle the list on every iteration.

Foo randomPick = null;
Collections.shuffle(myList);
for (Foo f : myList) {
    if (f.property) {
        randomPick = f;
        break;
    }
}

在此先感谢！

Thanks in advance!

推荐答案

最有效的解决方案将部分取决于你打算如何经常挑随机元素，你是否想选择的不同的的随机元素，和什么元素比例满足标准

The most efficient solution will partly depend on how often you're going to pick random elements, whether you want to pick different random elements, and what proportion of the elements meet the criterion

有几个选项：

创建只包含符合标准的元素的副本。然后，您可以打乱了，并遍历它连续不同的随机元素，还是只挑选任意随机元素通过拾取随机指标。这显然​​是O（n）的建立在时间和空间，但有效其后。 随机收集一次，然后遍历你正在做的 - 但保留迭代器。另外，手动使用索引进行迭代。这将让你得到不同的随机元素。这是O（n）重新设置。 请挑选从原来的列表中随机元素，直到你找到一个符合的标准。这有可能需要很长的时间，如果你有一个大名单，只有少数有效的项目，虽然。这不需要设置，但你可能最终会浪费工作通过反复测试相同的元素。 在一种混合的方法：保持从原来的列表中挑选随机元素，但删除的他们，如果他们不符合标准。不幸的是去除从列表的中间是O（n）操作过的的ArrayList 的常见情况：（ Create a copy containing only the elements meeting the criterion. You can then either shuffle that and iterate over it for successive distinct random elements, or just pick arbitrary random elements by picking a random index. This is obviously O(n) setup in both time and space, but efficient thereafter. Shuffle the collection once, then iterate over as you are doing - but keep the iterator. Alternatively, perform the iteration manually using the index. This will allow you to get distinct random elements. This is O(n) setup again. Keep picking random elements from the original list until you find one which meets the criteria. This has could take a very long time if you have a large list with only a few "valid" items though. This requires no setup, but you could end up "wasting" work by repeatedly testing the same elements. A hybrid approach: keep picking random elements from the original list, but remove them if they don't meet the criterion. Unfortunately removal from the middle of a list is O(n) operation too for the common case of ArrayList :(

（请注意，这我已经大多假设的ArrayList 的复杂性。获得在特定指数的LinkedList 为O（n），例如，但随后去除便宜。）

(Note that this I've been mostly assuming ArrayList complexity. Getting to a specific index in a LinkedList is O(n) for example, but then removal is cheap.)