David Robles David Robles - 1 year ago 66
Java Question

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

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;
for (Foo f : myList) {
if (f.property) {
randomPick = f;

Thanks in advance!

Answer Source

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

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download