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

Question

Мне нужно выбрать случайный элемент из списка, который выполняет определенное условие. Подход, который я использовал, работает, но я уверен, что это не каждый эффективный. Какой был бы самый эффективный способ сделать это?

Следующий код внутри цикла while (true), поэтому, очевидно, не очень эффективно перетасовывать список на каждой итерации.

Foo randomPick = null; 
Collections.shuffle(myList); 
for (Foo f : myList) { 
    if (f.property) { 
     randomPick = f; 
     break; 
    } 
} 

Заранее благодарен!

Answer 1

Наиболее эффективное решение будет отчасти зависеть от того, как часто вы собираетесь выбрать случайные элементы, хотите ли вы, чтобы выбрать различные случайных элементов, и какая доля элементов соответствуют критерию

Несколько вариантов :

• Создайте копию, содержащую только элементы, соответствующие критерию. Затем вы можете либо перетасовать это, либо перебрать его для последовательных отдельных случайных элементов, либо просто выбрать произвольные случайные элементы, выбрав случайный индекс. Это, очевидно, O (n) настройка как во времени, так и в пространстве, но более эффективно после этого.
• Перетасовывайте коллекцию один раз, затем повторяйте ее, как вы делаете, но сохраните итератор. В качестве альтернативы, выполните итерацию вручную, используя индекс. Это позволит вам получить отдельные случайные элементы. Это O (n) настройка снова.
• Продолжайте выбирать случайные элементы из исходного списка, пока не найдете тот, который соответствует критериям. Это может занять очень много времени, если у вас есть большой список только с несколькими «действительными» элементами. Это не требует установки, но вы можете в конечном итоге «растрачивать» работу, повторно тестируя одни и те же элементы.
• Гибридный подход: сохраняйте выбор случайных элементов из исходного списка, но удалите их, если они не соответствуют критерию. К сожалению, удаление из середины списка O (п) операция тоже для общего случая ArrayList :(

(Обратите внимание, что это я в основном в предположении ArrayList сложности. Получение к определенному индексу в LinkedList о (п), например, но затем удаление дешево)

Answer 2

Вместо того, чтобы перетасовывать, почему бы не выбрать случайное число целых чисел, а затем проверить его свойство?

    public Foo picker() { 
    while (true) { // TODO: realistically, you need to deal with exit conditions 
     int randIdx = myRand.nextInt(); 
     Foo randomPick = myList.get(randIdx % randIdx); 
     if (randomPick.property) 
     return randomPick; 
    } 
    } 

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

Если два предположения должны быть сфальсифицированы, вы должны выбрать подмножество, а затем произвольно выбрать один из них.

Answer 3

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

Answer 4

List<Foo> matchingItems = new ArrayList<Foo>(); 
    for(Foo f : myList) { 
     if (f.property) matchingItems.add(f); 
    } 

    Random randomGenerator = new Random(); 
    int index = randomGenerator.nextInt(matchingItems.size()); 
    Foo randomFoo = matchingItems.get(index); 

Answer 5

Используйте ленивым перетасовать:. он вычисляет и дает перемешиваются элементы только как они необходимы.

AC# реализация, но легко преобразуется в Java: Is using Random and OrderBy a good shuffle algorithm?

Answer 6

Поскольку вы делаете перетасовать, вы в основном прикасаясь каждый элемент, по крайней мере один раз, так что у вас уже есть большой вывод, по крайней мере, N. Если вы выберите случайный индекс, затем проверьте элемент в этом месте, затем вы получите требуемую переменную, прежде чем вы коснетесь N элементов, гарантированных, таким образом, гарантированное улучшение. Если у вас 20% распределение элементов, вы можете ожидать, что каждый пятый случайный индекс даст вам элемент, соответствующий вашим критериям. Хотя это не гарантия, это является вероятностью. Абсолютный худший сценарий, вы бы выбрали все 80% элементов, которые не соответствовали вашим критериям, а затем следующий будет вашим случайным элементом. максимальное выполнение будет ограничено, было бы .8N + 1, еще лучше, чем N., и в среднем ваша большая стоимость O будет чем-то вроде константы 5-10. WAAAAY лучше с точки зрения исполнения при увеличении N.

Answer 7

Просто выберите случайный индекс;

Random r = new Random(); 
while (true) 
{ 
    ... 
    Foo element = null; 
    while (element == null) 
    { 
     Foo f = myList.get(r.nextInt(myList.size()); 
     if (f.property) element = f; 
    } 
    ... 
} 

Answer 8

Вы можете использовать linear congruential random number generator какие циклы прямоточный индексы вашего списка, а также, возможно, несколько больше, чтобы быть в состоянии выбрать подходящие параметры, а затем проверить значения индексируются этой последовательности, отбрасывая индексы, которые слишком большой и выбирающий первый элемент, который вы найдете. Если вы ничего не обнаружите, вы можете остановиться, когда случайная последовательность начнет повторяться.

Для этого необходимо м. должно быть не менее, чем список. Чтобы иметь возможность выбрать a, модуль m должен содержать коэффициент 8 или квадрат некоторого простого> = 3. c следует выбирать случайным образом, чтобы он был взаимно простым с m. Также произвольно выберите начальное значение.

Answer 9

Случайно перетасовывание массива более одного раза глупо.

Shuffle один раз. Затем для каждого запроса случайного значения верните следующее значение, пока вы не исчерпали свой список.

Answer 10

O (п):

Random r = new Random(); 
int seen = 0; 
Foo randomPick = null; 
for (Foo foo : myList) { 
    if (foo.property && r.nextInt(++seen) == 0) { 
    randomPick = foo; 
    } 
} 

Answer 11

Пожалуйста, проверьте ссылку

http://www.javamex.com/tutorials/random_numbers/random_sample.shtml

public static <T> T[] pickSample(T[] population, int nSamplesNeeded, Random r) { 
    T[] ret = (T[]) Array.newInstance(population.getClass().getComponentType(), 
           nSamplesNeeded); 
    int nPicked = 0, i = 0, nLeft = population.length; 
    while (nSamplesNeeded > 0) { 
    int rand = r.nextInt(nLeft); 
    if (rand < nSamplesNeeded) { 
     ret[nPicked++] = population[i]; 
     nSamplesNeeded--; 
    } 
    nLeft--; 
    i++; 
} 
return ret; 
}