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

Question

我正在尝试使用Java 8中的Streams API从Collection中检索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());

编辑：第三次尝试，如果coll.size（）很大而n很小时，它将消除很多随机播放的开销：

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第2卷，第3.4.2节，
随机抽样和混洗 ，算法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， DonaldE。《计算机编程的艺术：第二卷，半数值算法》，第二版。 版权所有1981，1969 Addison-Wesley。