Ответ 1
Подход к перетасовке работает достаточно хорошо, как было предложено fge в comment и 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, и еще несколькими ответами - это выбор элементов случайным образом, а также отказ от дубликатов до тех пор, пока не будет выбрано желаемое количество уникальных элементов. Это хорошо работает, если количество элементов для выбора невелико относительно общего числа, но по мере того, как число выбирается, это немного замедляется из-за вероятности выбора дубликатов.
Было бы неплохо, если бы был способ сделать один проход по пространству входных элементов и выбрать именно то, что нужно, с выбором, сделанным равномерно случайным образом? Оказывается, что есть, и, как обычно, ответ можно найти в Кнуте. См. TAOCP Vol 2, с. 3.4.2, Random Sampling and Shuffling, Алгоритм S.
Вкратце, алгоритм должен посещать каждый элемент и решать, выбирать ли его в зависимости от количества посещенных элементов и количества выбранных элементов. Предположим, что у вас есть N элементов, и вы хотите выбрать n из них наугад. Следующий элемент следует выбирать с вероятностью
(n - m)/(N - t)
где t - количество посещенных элементов, а m - количество элементов, выбранных до сих пор.
Совершенно очевидно, что это даст равномерное распределение выбранных элементов, но, по-видимому, это так. Доказательство остается в качестве упражнения для читателя; см. упражнение 3 этого раздела.
Учитывая этот алгоритм, довольно просто реализовать его в "обычной" Java, перейдя по коллекции и добавив в список результатов на основе случайного теста. OP попросил об использовании потоков, поэтому здесь сделайте снимок.
Алгоритм S явно не работает с операциями потока Java. Он описывается полностью последовательно, и решение о том, следует ли выбирать текущий элемент, зависит от случайного решения плюс состояние, полученного из всех предыдущих решений. Это может заставить его казаться неотъемлемой последовательностью, но я раньше ошибался. Я просто скажу, что не сразу понятно, как сделать этот алгоритм параллельным.
Есть способ адаптировать этот алгоритм к потокам. Нам нужен предикат с состоянием. Этот предикат возвращает случайный результат, основанный на вероятности, определяемой текущим состоянием, и состояние будет обновлено - да, мутировано - на основе этого случайного результата. Кажется, что это трудно выполнить параллельно, но, по крайней мере, легко сделать потокобезопасным, если он запускается из параллельного потока: просто сделайте его синхронизированным. Однако, если поток параллелен, он будет деградировать, чтобы работать последовательно.
Реализация довольно проста. Описание Knuth использует случайные числа от 0 до 1, но класс Java Random позволяет выбрать случайное целое число в пределах полуоткрытого интервала. Таким образом, все, что нам нужно сделать, это сохранить счетчики количества элементов, которые нужно посетить, и сколько осталось выбрать, et voila:
/**
* 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());
}
Альтернатива, упомянутая в том же разделе Кнута, предполагает выбор элемента случайным образом с постоянной вероятностью 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;
}
Это довольно просто, и в этом нет ничего плохого. Это проще и более автономно, чем поток. Тем не менее, подход к потокам иллюстрирует некоторые интересные методы, которые могут быть полезны в других контекстах.
Ссылка:
Кнут, Дональд Э. Искусство компьютерного программирования: Том 2, Семинумерные алгоритмы, 2-е издание. Copyright 1981, 1969 Addison-Wesley.