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

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 (n) для общего случая ArrayList: (

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

Answer 2

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

Реализация на C #, но легко конвертируемая в Java: Является ли использование Random и OrderBy хорошим алгоритмом перемешивания?

Answer 3

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

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

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

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

Answer 4

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

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 5

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

Answer 6

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

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

Answer 7

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 8

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

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

Answer 9

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

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

Answer 10

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