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

Question

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

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

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

Answer 1

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

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

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

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

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

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

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

Answer 3

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

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

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

Answer 4

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

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

Answer 5

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

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 для перестановки списка.

Answer 6

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

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

}