我需要从一个列表，即满足一定的条件选择一个随机元素。 这种方法我一直使用的作品，但我敢肯定，是不是每一个高效。 什么是最有效的方式做到这一点？
下面的代码是一个while（true）循环里面，这样显然不是非常有效的洗牌在每个迭代上的列表中。
Foo randomPick = null;
Collections.shuffle(myList);
for (Foo f : myList) {
if (f.property) {
randomPick = f;
break;
}
}
提前致谢！
最有效的解决方案将部分取决于你要多久挑选随机元素，你是否要选择不同的随机元素，以及多大比例的元素符合标准
有几个选项：
ArrayList :( （请注意，这我已经大多假设ArrayList复杂性。获得一个特定的指数在LinkedList是O（n），例如，但随后去除很便宜。）
Use a lazy shuffle: it calculates and yields the shuffled elements only as they are needed.
A C# implementation, but easily converted to Java: Is using Random and OrderBy a good shuffle algorithm?
相反洗牌，为什么不选择一个随机指数整数，然后测试其性能？
public Foo picker() {
while (true) { // TODO: realistically, you need to deal with exit conditions
int randIdx = myRand.nextInt();
Foo randomPick = myList.get(randIdx % randIdx);
if (randomPick.property)
return randomPick;
}
}
请注意 ，这确实认为这个列表的一个不平凡的数量确实有真正的财产，而这些特性发生变化。
如果两个假设将被证伪，你要选择一个子集，然后随机选择其中的一个。
既然你正在做一个洗牌，你基本上接触的每个元素至少一次，所以你已经有至少N的一大Ø如果你选择一个随机指数，然后在该位置测试元素，那么你会得到你想你已经触及N个元素之前的变量，有保障，从而保证改善。 如果你有元素的20％分布，那么你会希望每5随机指标给你满足您的条件的元素。 虽然这不是一个保证，这是一个probabliltiy。 绝对最坏的情况下，你会选择未满足条件的元素的所有80％，那么下一个会是你的随机元素。 你最大的执行将仅限于将将被.8N + 1，仍优于N.，平均你的大O开销会像5-10的常数。 在执行作为N增加的条款WAAAAY更好。
只要选择一个随机指数;
Random r = new Random();
while (true)
{
...
Foo element = null;
while (element == null)
{
Foo f = myList.get(r.nextInt(myList.size());
if (f.property) element = f;
}
...
}
我建议做一个临时的过滤列表出来的myList ，每一个项目满足您的条件。 然后在每次迭代，你可以将它洗，并挑选了顶部的项目，或者使用随机指数选择一个随机的项目。
你可以使用一个线性同余随机数发生器 ，其循环一次通过列表的指标，再加上可能多了一些能够选择合适的参数，然后检查由该序列索引的值，丢弃它太大了，并且采摘指标你找到的第一个元素。 如果你发现没有，当随机顺序开始重复，你可以停下来。
对于这个工作需要的米至少为列表一样大。 为了能够选择了的模数m必须包含8倍或一些素> = 3℃的正方形应该被随机地选择，以便它是互质为m。 还搭载初始值随机。
随机洗牌数组不止一次是愚蠢的。
随机播放一次。 那么，对于一个随机值的每个请求，为了返回一个值，直到你耗尽你的清单。
为O（n）：
Random r = new Random();
int seen = 0;
Foo randomPick = null;
for (Foo foo : myList) {
if (foo.property && r.nextInt(++seen) == 0) {
randomPick = foo;
}
}
List<Foo> matchingItems = new ArrayList<Foo>();
for(Foo f : myList) {
if (f.property) matchingItems.add(f);
}
Random randomGenerator = new Random();
int index = randomGenerator.nextInt(matchingItems.size());
Foo randomFoo = matchingItems.get(index);
请检查该链接
http://www.javamex.com/tutorials/random_numbers/random_sample.shtml
public static <T> T[] pickSample(T[] population, int nSamplesNeeded, Random r) {
T[] ret = (T[]) Array.newInstance(population.getClass().getComponentType(),
nSamplesNeeded);
int nPicked = 0, i = 0, nLeft = population.length;
while (nSamplesNeeded > 0) {
int rand = r.nextInt(nLeft);
if (rand < nSamplesNeeded) {
ret[nPicked++] = population[i];
nSamplesNeeded--;
}
nLeft--;
i++;
}
return ret;
}
