使用Streams API对Collection中的n个随机不同元素执行操作
我正在尝试使用Java 8中的Streams API从集合中检索n个唯一的随机元素以进行进一步处理,但是没有太多或任何运气。
更准确地说,我想要这样的东西:
Set subList = new HashSet(); Queue collection = new PriorityQueue(); collection.addAll(Arrays.asList(1,2,3,4,5,6,7,8,9)); Random random = new Random(); int n = 4; while (subList.size() v.doSomethingFancy());
我想尽可能高效地做到这一点。
可以这样做吗?
编辑:我的第二次尝试 – 虽然不是我的目标:
List sublist = new ArrayList(collection); Collections.shuffle(sublist); sublist.stream().limit(n).forEach(v -> v.doSomethingFancy());
编辑:第三次尝试(灵感来自Holger ),如果coll.size()很大且n很小,这将消除很多shuffle的开销:
int n = // unique element count List sublist = new ArrayList(collection); Random r = new Random(); for(int i = 0; i v.doSomethingFancy());
正如评论中的fge和另一个答案中的ZouZou所建议的那样 ,改组方法运作得相当好。 这是改组方法的一般化版本:
static List shuffleSelectN(Collection extends E> coll, int n) { assert n <= coll.size(); List list = new ArrayList<>(coll); Collections.shuffle(list); return list.subList(0, n); }
我会注意到,使用subList
比获取流然后调用limit(n)
更好,如其他一些答案所示,因为生成的流具有已知大小并且可以更有效地分割。
改组方法有几个缺点。 它需要复制出所有元素,然后需要对所有元素进行混洗。 如果元素的总数很大并且要选择的元素的数量很少,则这可能非常昂贵。
OP和其他几个答案建议的方法是随机选择元素,同时拒绝重复,直到选择了所需数量的唯一元素。 如果要选择的元素数量相对于总数较小,则效果很好,但随着要选择的数量增加,这会因为选择重复数据的可能性增加而减慢很多。
如果有一种方法可以在输入元素的空间上进行单次传递并精确选择想要的数字,并且随机选择均匀,那会不会很好? 事实certificate,就像往常一样,答案可以在Knuth中找到。 参见TAOCP Vol 2,sec 3.4.2, Random Sampling and Shuffling ,Algorithm S.
简而言之,算法是访问每个元素并根据访问的元素数量和所选元素的数量决定是否选择它。 在Knuth的表示法中,假设您有N个元素,并且您想随机选择其中的n个元素。 应该以概率选择下一个元素
(n – m)/(N – t)
其中t是到目前为止访问过的元素数, m是到目前为止选择的元素数。
显而易见的是,这将给出所选元素的均匀分布,但显然确实如此。 证据留给读者作为练习; 见本节练习3。
有了这个算法,通过循环收集并基于随机测试添加到结果列表,在“常规”Java中实现它非常简单。 OP询问使用流,所以这里有一个镜头。
算法S显然不适合Java流操作。 它完全按顺序描述,关于是否选择当前元素的决定取决于随机决策加上从所有先前决策得到的状态。 这可能会使它看起来具有内在的顺序性,但我以前错了。 我只想说,如何使这个算法并行运行并不是很明显。
但是,有一种方法可以将此算法应用于流。 我们需要的是一个有状态的谓词 。 该谓词将根据当前状态确定的概率返回随机结果,并且状态将根据此随机结果更新 – 是,变异。 这似乎很难并行运行,但至少在从并行流运行时很容易使线程安全:只需使其同步即可。 但是,如果流是并行的,它将降序为顺序运行。
实现非常简单。 Knuth的描述使用0到1之间的随机数,但Java Random
类允许我们在半开区间内选择一个随机整数。 因此,我们需要做的就是保留计数器的数量,以及剩下多少元素可供选择, 等等 :
/** * A stateful predicate that, given a total number * of items and the number to choose, will return 'true' * the chosen number of times distributed randomly * across the total number of calls to its test() method. */ static class Selector implements Predicate
现在我们有了谓词,它很容易在流中使用:
static List randomSelectN(Collection extends E> coll, int n) { assert n <= coll.size(); return coll.stream() .filter(new Selector(coll.size(), n)) .collect(toList()); }
在Knuth的同一部分中也提到的替代方案建议随机选择具有恒定概率n / N的元素。 如果您不需要精确选择n个元素,这将非常有用。 它平均会选择n个元素,但当然会有一些变化。 如果这是可以接受的,则有状态谓词变得更加简单。 我们可以简单地创建随机状态并从局部变量中捕获它,而不是编写整个类:
/** * Returns a predicate that evaluates to true with a probability * of toChoose/total. */ static Predicate
要使用它,请将上面的流管道中的filter
行替换为
.filter(randomPredicate(coll.size(), n))
最后,为了进行比较,这里是使用传统Java编写的选择算法的实现,即使用for循环并添加到集合:
static List conventionalSelectN(Collection extends E> coll, int remain) { assert remain <= coll.size(); int total = coll.size(); List result = new ArrayList<>(remain); Random random = new Random(); for (E e : coll) { if (random.nextInt(total--) < remain) { remain--; result.add(e); } } return result; }
这很简单,这没有什么不妥。 它比流方法更简单,更自包含。 尽管如此,流方法还是展示了一些在其他环境中可能有用的有趣技术。
参考:
Knuth,Donald E. 计算机程序设计的艺术:第2卷,系数算法,第2版。 版权所有1981,1969 Addison-Wesley。
您总是可以创建一个“哑”比较器,它将在列表中随机比较元素。 调用distinct()
将确保元素是唯一的(来自队列)。
像这样的东西:
static List nDistinct(Collection queue, int n) { final Random rand = new Random(); return queue.stream() .distinct() .sorted(Comparator.comparingInt(a -> rand.nextInt())) .limit(n) .collect(Collectors.toList()); }
但是我不确定将元素放在列表中,将其洗牌并返回子列表会更有效率。
static List nDistinct(Collection queue, int n) { List list = new ArrayList<>(queue); Collections.shuffle(list); return list.subList(0, n); }
哦,并且在语义上更好的是返回Set
而不是List
因为元素是区别的。 这些方法也被设计为采用Integer
,但设计它们是通用的没有困难。 🙂
就像一个注释,Stream API看起来像一个我们可以用于所有东西的工具箱,但情况并非总是如此。 如您所见,第二种方法更具可读性(IMO),可能更高效,并且没有更多代码(甚至更少!)。
您可以使用限制来解决您的问题。
http://docs.oracle.com/javase/8/docs/api/java/util/stream/Stream.html#limit-long-
Collections.shuffle(collection); int howManyDoYouWant = 10; List smallerCollection = collection .stream() .limit(howManyDoYouWant) .collect(Collectors.toList());
作为接受答案的shuffle
方法的补充:
如果您只想从大型列表中选择几个项目并希望避免洗牌整个列表的开销,您可以按如下方式解决任务:
public static List getRandom(List source, int num) { Random r=new Random(); for(int i=0; i
它的作用与shuffle
的作用非常相似,但它减少了仅使用num
随机元素而不是source.size()
随机元素的动作......
List collection = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10); int n = 4; Random random = ThreadLocalRandom.current(); random.ints(0, collection.size()) .distinct() .limit(n) .mapToObj(collection::get) .forEach(System.out::println);
这当然会有中间索引集的开销,如果n> collection.size(),它将永远挂起。
如果你想避免任何非constatn开销,你将不得不制作一个有状态Predicate
。
应该清楚的是,流式传输集合并不是您想要的。
使用generate()
和limit
方法:
Stream.generate(() -> list.get(new Random().nextInt(list.size())).limit(3).forEach(...);