使用Streams API对Collection中的n个随机不同元素执行操作

Question

我正在尝试使用Java 8中的Streams API从集合中检索n个唯一的随机元素以进行进一步处理,但是没有太多或任何运气.

更准确地说,我想要这样的东西:

Set<Integer> subList = new HashSet<>();
Queue<Integer> 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() < n) {
  subList.add(collection.get(random.nextInt()));
}
sublist.forEach(v -> v.doSomethingFancy());

我想尽可能高效地做到这一点.

可以这样做吗？

编辑:我的第二次尝试 - 虽然不是我的目标:

List<Integer> 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<Integer> sublist = new ArrayList<>(collection);   
Random r = new Random();
for(int i = 0; i < n; i++)
    Collections.swap(sublist, i, i + r.nextInt(source.size() - i));
sublist.stream().limit(n).forEach(v -> v.doSomethingFancy());

Answer 1

正如评论中的fge和另一个答案中的ZouZou所建议的那样,改组方法运作得相当好.这是改组方法的一个通用版本:

static <E> List<E> shuffleSelectN(Collection<? extends E> coll, int n) {
    assert n <= coll.size();
    List<E> list = new ArrayList<>(coll);
    Collections.shuffle(list);
    return list.subList(0, n);
}

我会注意到,使用subList比获取流然后调用更可取limit(n),如其他一些答案所示,因为生成的流具有已知大小并且可以更有效地分割.

改组方法有几个缺点.它需要复制所有元素,然后它需要洗牌所有元素.如果元素的总数很大并且要选择的元素的数量很少,则这可能非常昂贵.

OP和其他几个答案建议的方法是随机选择元素,同时拒绝重复,直到选择了所需数量的唯一元素.如果要选择的元素数量相对于总数较小,则效果很好,但随着要选择的数量增加,这会慢下来,因为选择重复数据的可能性也会增加.

如果有一种方法可以在输入元素的空间内进行单次传递并精确选择所需的数字,并且随机选择均匀,那会不会很好？事实证明,就像往常一样,答案可以在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<Object> {
    int total;  // total number items remaining
    int remain; // number of items remaining to select
    Random random = new Random();

    Selector(int total, int remain) {
        this.total = total;
        this.remain = remain;
    }

    @Override
    public synchronized boolean test(Object o) {
        assert total > 0;
        if (random.nextInt(total--) < remain) {
            remain--;
            return true;
        } else {
            return false;
        }
    }
}

现在我们有了谓词,它很容易在流中使用:

static <E> List<E> 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<Object> randomPredicate(int total, int toChoose) {
    Random random = new Random();
    return obj -> random.nextInt(total) < toChoose;
}

要使用它,请将filter上面的流管道中的行替换为

        .filter(randomPredicate(coll.size(), n))

最后,为了进行比较,这里是使用传统Java编写的选择算法的实现,即使用for循环并添加到集合:

static <E> List<E> conventionalSelectN(Collection<? extends E> coll, int remain) {
    assert remain <= coll.size();
    int total = coll.size();
    List<E> 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.