我需要一个从集合n中随机选择m个子元素的算法。 当然最好的办法是将集合打乱顺序，然后从中选择前m个元素即可。 java中现成的api可以使用：
java.util.collections.shuffle(list)
此算法非常简单，循环n次，每次长度减少1，随机获取其中一个元素，然后交换其对称元素。
public static void shuffle(list list, random rnd) {
int size = list.size();
if (size < shuffle_threshold || list
instanceof randomaccess) {
for (
int i=size; i>1; i--)
swap(list, i-1, rnd.nextint(i));
}
else {
object arr[] = list.toarray();
// shuffle array
for (
int i=size; i>1; i--)
swap(arr, i-1, rnd.nextint(i));
// dump array back into list
listiterator it = list.listiterator();
for (
int i=0; i
it.next();
it.set(arr[i]);
}
}
}
public static void swap(list list, int i, int j) {
final list l = list;
l.set(i, l.set(j, l.get(i)));
}
其实我们的需求很简单，在基本不变的集合中，多次重复随机获取其子集，至于子集是否有序或者随机不重要的， 重要的是原集合中的每个元素都有相似的概率出现在子集合中。
考虑到性能以及并发访问（多线程）的需要，我想到了一个简单的算法：
给定n个元素集合，从中选择m(0
- 随机选择索引k(0<=k
- 取有效元素n(k-i),n(k i) 加入未满子集m
- i =1, 重复(2) 直到子集m已满
- 终止
这样取出来的元素虽然和原始集顺序有一定的关系，但是每个元素在子集里出现的概率相当，满足结果要求。 最后生成的算法如下：
public static list randomlist(list views, int max) {
final int size = views.size();
int index = randomutils.nextint(size);
//
list ret = new arraylist(max);
int low = index - 1, high = index;
while (max > 0 && (low >= 0 || high < size)) {
if (low >= 0 && max-- > 0) {
ret.add(views.get(low));
}
if (high < size && max-- > 0) {
ret.add(views.get(high));
}
low--;
high ;
}
return ret;
}
此算法满足如下特点：
- 足够快
- 线程安全（原始集合不变）
- 子元素出现概率相当（未经数学证明
另外，stackoverflow上也有一些参考链接：
- http://mcherm.com/permalinks/1/a-random-selection-algorithm
- http://stackoverflow.com/questions/4702036/take-n-random-elements-from-a-liste
[ 原文地址 ]
©2009-2014 imxylz
|求贤若渴