Получить случайный элемент из последовательной коллекции

Question

Я говорю с API, который дает мне java.util.Iterator над коллекцией.Это означает, что я могу перебирать его, но не могу получить прямой / произвольный доступ к элементам.

Теперь к моей проблеме: я хочу получить один случайный элемент из этой коллекции.Как я могу это сделать?Я думаю, я мог бы создать новую коллекцию, которая обеспечивает прямой доступ, но разве это не потребляет немного памяти?Я также мог бы перебрать всю коллекцию и для каждого элемента «бросить кубик», чтобы посмотреть, должен ли я взять этот элемент и выйти из итерации или продолжить.Но тогда мне нужен размер коллекции, и я не могу получить это от Итератора.

Заранее спасибо.

Answer 1

Есть способ сделать это за один проход через коллекцию, который не использует много дополнительной памяти (только размер одного элемента коллекции плюс число с плавающей запятой).В псевдокоде:

• Итерация по коллекции.
• Для каждого предмета генерировать случайное число с плавающей точкой.
• Если число с плавающей точкой является самым низким (или самым высоким, это не имеет значения), которое вы видели до сих пор, сохраните текущий элемент из коллекции во временной переменной.(Также сохраните новое наименьшее случайное значение.)
• Как только вы достигнете конца коллекции, у вас есть случайный элемент в переменной temp.

Очевидно, что это имеет недостатокперебирая всю коллекцию каждый раз, когда вы ее вызываете, но у вас нет большого выбора с теми ограничениями, с которыми вы сталкиваетесь.

Обновление: Название проблемы такого типанаконец вернулся ко мне.Это называется Отбор проб из резервуара .

Answer 2

Когда вы выполняете итерацию, вы знаете, сколько объектов вы прошли, поэтому вы знаете вероятность того, что текущий элемент будет выбран случайно. Так что вам просто нужно сохранить количество и текущий случайно выбранный элемент.

public static <T> T selectRandom(final Iterator<T> iter, final Random random) {
    if (!iter.hasNext()) {
        throw new IllegalArgumentException();
    }
    if (random == null) {
        throw new NullPointerException();
    }
    T selected = iter.next();
    int count = 1;
    while (iter.hasNext()) {
        final T current = iter.next();
        ++count;
        if (random.nextInt(count) == 0) {
            selected = current;
        }
    }
    return selected;
}

(Отказ от переполнения стека: не скомпилирован и, конечно, не проверен.)

См. Также раздел о Collections.shuffle в Java Puzzlers.

Answer 3

Единственное безопасное решение (если дополнительная информация не известна / не гарантирована) - это способ, которым вы описали: Создайте List из Iterator и выберите случайный элемент.

Если размер базовой коллекции всегда один и тот же, вы можете уменьшить в среднем половину усилий - просто используйте элемент, полученный после Iterator.next () после случайного числа итераций.

Кстати : Вы действительно используете коллекцию, которая реализует java.util.Iterator?

Answer 4

Используется для генерации взвешенных тестовых данных. это не эффективно, но легко

class ProbabilitySet<E> {

    Set<Option<E>> options =  new HashSet<Option<E>>(); 

    class Option<E> {
        E object;
        double min;
        double max;

        private Option(E object, double prob) {
            this.object = object;
            min = totalProb;
            max = totalProb + prob;
        }

        @Override
        public String toString() {
            return "Option [object=" + object + ", min=" + min + ", max=" + max + "]";
        }
    }

    double totalProb = 0;
    Random rnd = new Random();

    public void add(E object, double probability){
        Option<E> tuple = new Option<E>(object, probability);
        options.add(tuple);
        totalProb += probability;
    }

    public E getRandomElement(){

        double no = rnd.nextDouble() * totalProb;
        for (Option<E> tuple : options) {
            if (no >= tuple.min && no < tuple.max){
                return tuple.object;
            }
        }


        return null;  // if this happens sumfink is wrong.

    }

    @Override
    public String toString() {
        return "ProbabilitySet [options=" + options + ", totalProb=" + totalProb + "]";
    }

}

ПРИМЕЧАНИЕ: параметры вероятности будут относительными к общему, а не 1,0

Использование:

public static void main(String[] args) {
    ProbabilitySet<String> stati = new ProbabilitySet<String>();
    stati.add("TIMEOUT", 0.2);
    stati.add("FAILED", 0.2);
    stati.add("SUCCESSFUL", 1.0);

    for (int i = 0; i < 100; i++) {
        System.out.println(stati.getRandomElement());
    }

}

Answer 5

Это зависит от требований: если размер коллекции не велик, тогда это будет сделано, в противном случае вам следует повторить и использовать метод кости, который вы упомянули

List<Object> list = Arrays.asList(yourCollection.toArray(new Object[0]));
result = list.get(new Random().nextInt(list.size()));

Answer 6

Если у вас действительно нет произвольного доступа, и у вас очень большой список, и вы не можете скопировать его, тогда вы можете сделать следующее:

int n = 2
iterator i = ...
Random rand = new Random();
Object candidate = i.next();
while (i.hasNext()) {
    if (rand.nextInt(n)) {
        candidate = i.next();
    } else {
        i.next();
    }
    n++;
}
return candidate;

Это сохранит случайный элементиз списка, но требует, чтобы вы пересекали весь список.Если вы хотите по-настоящему равномерно распределенное значение, у вас нет другого выбора, кроме как сделать это.

В качестве альтернативы, если количество элементов мало, или если вы хотите случайную перестановку списка неизвестного размера (другими словамиВы хотите получить доступ ко всем элементам списка в произвольном порядке), затем я рекомендую скопировать все ссылки в новый список (это не займет значительный объем памяти, если у вас нет миллионов элементов, поскольку вы храните только ссылки),Затем либо используйте get со случайным целым числом, либо используйте стандартный метод java.util.Collections shuffle для перестановки списка.