从满足特定条件的列表中选择随机元素的最快方法

Question

我需要从列表中选择一个满足某些条件的随机元素.我一直在使用的方法有效,但我确信并非一切都有效.最有效的方法是什么？

以下代码位于while(true)循环内,因此在每次迭代时显然不是非常有效地对列表进行洗牌.

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

提前致谢!

Answer 1

最有效的解决方案部分取决于您选择随机元素的频率,是否要选择不同的随机元素,以及哪些元素符合标准的比例

一些选择:

• 创建仅包含符合条件的元素的副本.然后,您可以将其移动并对其进行迭代以获得连续的不同随机元素,或者通过选择随机索引来选择任意随机元素.这显然是时间和空间上的O(n)设置,但此后有效.
• 将集合洗牌一次,然后按照您的操作迭代 - 但保留迭代器.或者,使用索引手动执行迭代.这将允许您获得不同的随机元素.这是O(n)再次设置.
• 继续从原始列表中挑选随机元素,直到找到符合条件的元素.如果你有一个只有少数"有效"项目的大型列表,这可能需要很长时间.这不需要设置,但你可能会通过反复测试相同的元素来"浪费"工作.
• 混合方法:继续从原始列表中挑选随机元素,但如果它们不符合标准则删除它们.不幸的是,从列表中间删除O(n)操作也是常见的情况ArrayList:(

(注意,我一直主要假设ArrayList复杂性.LinkedList例如,获取a中的特定索引是O(n),但是删除很便宜.)