我需要一個(gè)從集合N中隨機(jī)選擇M個(gè)子元素的算法。 當(dāng)然最好的辦法是將集合打亂順序，然后從中選擇前M個(gè)元素即可。 Java中現(xiàn)成的API可以使用：
java.util.Collections.shuffle(List<?>)
此算法非常簡(jiǎn)單，循環(huán)N次，每次長度減少1，隨機(jī)獲取其中一個(gè)元素，然后交換其對(duì)稱元素。
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<arr.length; 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)));
}
其實(shí)我們的需求很簡(jiǎn)單，在基本不變的集合中，多次重復(fù)隨機(jī)獲取其子集，至于子集是否有序或者隨機(jī)不重要的， 重要的是原集合中的每個(gè)元素都有相似的概率出現(xiàn)在子集合中。
考慮到性能以及并發(fā)訪問（多線程）的需要，我想到了一個(gè)簡(jiǎn)單的算法：
給定N個(gè)元素集合，從中選擇M(0<M<=N)個(gè)元素的辦法是，
- 隨機(jī)選擇索引K(0<=K<N), i=0, 空子集
- 取有效元素N(k-i),N(k+i) 加入未滿子集M
- i+=1, 重復(fù)(2) 直到子集M已滿
- 終止
這樣取出來的元素雖然和原始集順序有一定的關(guān)系，但是每個(gè)元素在子集里出現(xiàn)的概率相當(dāng)，滿足結(jié)果要求。 最后生成的算法如下：
public static <T> List<T> randomList(List<T> views, int max) {
final int size = views.size();
int index = RandomUtils.nextInt(size);
//
List<T> ret = new ArrayList<T>(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;
}
此算法滿足如下特點(diǎn)：
- 足夠快
- 線程安全（原始集合不變）
- 子元素出現(xiàn)概率相當(dāng)（未經(jīng)數(shù)學(xué)證明
另外，stackoverflow上也有一些參考鏈接：
©2009-2014 IMXYLZ
|求賢若渴