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

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);
}

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

洗牌方法有几个缺点.它需要复制所有的元素,然后它需要洗牌所有的元素.如果元件的总数量大并且要选择的元件的数量小,这可能是相当昂贵的.

OP提出的方法和几个其他答案是随机选择元素,同时拒绝重复,直到选择了所需数量的唯一元素.如果要选择的元素数量相对于总数较少,那么这个效果会很好,但是随着选择数量的增加,这种情况会因为选择重复上升的可能性而减慢.

如果有一种方法可以在输入元素的空间上单独选择并选择所需的号码,这些选择是否随机均匀地进行,那不是很好吗？事实证明,有一样,和往常一样,答案可以在克努特找到.参见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(randomPredicate(coll.size(),n))

最后,为了比较的目的,这里是使用常规Java编写的选择算法的实现,即使用for-loop并添加到集合中：

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. The Art of Computer Programming：Volume 2,Seminumerical Algorithms,2nd edition.版权1981年,1969年Addison-Wesley.