Fastest way to pick a random element from a list that fulfills certain condition

Question

I need to pick a random element from a list, that fulfills certain condition. The approach I've been using works, but I'm sure is not every efficient. What would be the most efficient way to do it?

The following code is inside a while (true) loop, so obviously is not very efficient to shuffle the list on every iteration.

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

Thanks in advance!

Answer 1

Instead of shuffling, why not pick a random index integer, and then test its property?

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

Note that this does indeed assume that a non-trivial number of the list do have property true, and that these properties change.

If the two assumptions were to be falsified, you'd want to select a subset, and then randomly select one of those.

Answer 2

I would suggest making a temporary filtered list out of myList where every item satisfies your condition. Then at every iteration you can shuffle it and pick the top item, or pick a random item using a random index.

Answer 3

The most efficient solution will partly depend on how often you're going to pick random elements, whether you want to pick different random elements, and what proportion of the elements meet the criterion

A few options:

• Create a copy containing only the elements meeting the criterion. You can then either shuffle that and iterate over it for successive distinct random elements, or just pick arbitrary random elements by picking a random index. This is obviously O(n) setup in both time and space, but efficient thereafter.
• Shuffle the collection once, then iterate over as you are doing - but keep the iterator. Alternatively, perform the iteration manually using the index. This will allow you to get distinct random elements. This is O(n) setup again.
• Keep picking random elements from the original list until you find one which meets the criteria. This has could take a very long time if you have a large list with only a few "valid" items though. This requires no setup, but you could end up "wasting" work by repeatedly testing the same elements.
• A hybrid approach: keep picking random elements from the original list, but remove them if they don't meet the criterion. Unfortunately removal from the middle of a list is O(n) operation too for the common case of ArrayList :(

(Note that this I've been mostly assuming ArrayList complexity. Getting to a specific index in a LinkedList is O(n) for example, but then removal is cheap.)

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

Use a lazy shuffle: it calculates and yields the shuffled elements only as they are needed.

A C# implementation, but easily converted to Java: http://stackoverflow.com/questions/1287567/c-is-using-random-and-orderby-a-good-shuffle-algorithm/1287572#1287572

Answer 6

Since you are doing a shuffle, you are basically touching every element at least once, so you already have a big O of at least N. If you pick a random index, then test the element at that location, then you are going to get the variable you want before you have touched N elements, guaranteed, thus a guaranteed improvement. If you have a 20% distribution of elements then you would expect every 5th random index to give you an element that meets your criteria. While this is not a guarantee, it is a probabliltiy. Absolute worst case scenario, you would choose all 80% of the elements that didn't meet your criteria, then the next one would be your random element. you max execution would be limited to would be would be .8N + 1, still better than N. and on average your big O cost would be something like a constant of 5-10 . WAAAAY better in terms of execution as N increases.

Answer 7

Just choose a random index;

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

You could use a linear congruential random number generator which cycles once through the indexes of your list, plus maybe a few more to be able to chose suitable parameters, and then check the values indexed by this sequence, discarding indexes which are too big and picking the first element you find. If you find nothing you can stop when the random sequence starts repeating.

For this to work m needs be at least as large as the list. To be able to chose a the modulus m must contain a factor of 8 or a square of some prime >= 3. c should be chosen randomly so that it is relatively prime to m. Also pick the initial value randomly.

Answer 9

Randomly shuffling the array more than once is silly.

Shuffle once. Then, for each request of a random value, return the next value in order until you've exhausted your list.

Answer 10

O(n):

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