xylz,imxylz

关注后端架构、中间件、分布式和并发编程

   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  111 随笔 :: 10 文章 :: 2679 评论 :: 0 Trackbacks
我需要一个从集合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<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. 终止
这样取出来的元素虽然和原始集顺序有一定的关系,但是每个元素在子集里出现的概率相当,满足结果要求。 最后生成的算法如下:
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;
}

此算法满足如下特点:
  1. 足够快
  2. 线程安全(原始集合不变)
  3. 子元素出现概率相当(未经数学证明

另外,stackoverflow上也有一些参考链接:

[ 原文地址 http://imxylz.com/blog/2013/08/14/select-a-random-sublist-from-list-in-java/ ]


©2009-2014 IMXYLZ |求贤若渴
posted on 2013-08-17 17:44 imxylz 阅读(3002) 评论(3)  编辑  收藏 所属分类: J2EE技术Java Concurrency

评论

# re: 随机选择集合的子元素集合 2013-08-22 16:43 hongliuliao
如果允许改变views的话,我一般这么用
views.remove(RandomUtils.nextInt(views.size()))
  回复  更多评论
  

# re: 随机选择集合的子元素集合 2014-06-15 23:58 梦在飞
真没看出来哪线程安全了。
  回复  更多评论
  

# re: 随机选择集合的子元素集合 2014-06-15 23:59 梦在飞
能删除吗?发错了,手机党伤不起。@梦在飞
  回复  更多评论
  


只有注册用户登录后才能发表评论。


网站导航:
 

©2009-2014 IMXYLZ