我须要一个从集合N中随机选择M个子元素的算法。 固然最好的办法是将集合打乱顺序,而后从中选择前M个元素便可。 Java中现成的API可使用:java
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<arr.length; i++) { it.next(); it.set(arr[i]); } } }
有点意思的swap函数安全
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<M<=N)个元素的办法是, (1) 随机选择索引K(0<=K<N), i=0, 空子集 (2) 取有效元素N(k-i),N(k+i) 加入未满子集M (3) i+=1, 重复(2) 直到子集M已满 (4) 终止
这样取出来的元素虽然和原始集顺序有必定的关系,可是每一个元素在子集里出现的几率至关,知足结果要求。 最后生成的算法以下:dom
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; }
此算法知足以下特色:函数
另外,stackoverflow上也有一些参考连接:性能