12
$\begingroup$

I'm looking for a data structure that supports the following operations:

add(elem) - Add an element to the data structure.
remove_random() - Remove and return a random element.

The best I got so far is just shuffling a list on every insertion (or on every lookup), and popping from the top. However, this can be quite slow, so I'm looking for a more specialized data structure. Assume we can generate random numbers for free.

$\endgroup$
3
  • $\begingroup$ How many elements $\endgroup$ Nov 24 at 9:21
  • 8
    $\begingroup$ By "remove a random element", do you mean "remove one chosen with equal probability (or any other distribution)", or do you mean "remove any one, I don't care which"? $\endgroup$
    – Pablo H
    Nov 24 at 15:19
  • $\begingroup$ What's the "profile" of your operations? How many add and remove_random do you intend to handle? Interleaved or separated (all adds first, then all removes, in which case one shuffle is enough)? Is this theoretical (want best O()) or practical (want good cache locality etc.)? $\endgroup$
    – Pablo H
    Nov 24 at 15:22
28
$\begingroup$

You can achieve constant amortized time per operation by keeping a dynamically-sized array $A$ (using the doubling/halving technique). To insert an element append it at the end. To implement remove_random() generate a random index $k$ between $1$ and $n$, swap $A[k]$ with $A[n]$ and delete (and return) $A[n]$.

If you want a non-amortized worst-case bound on the time complexity, then an AVL in which each node $v$ has been augmented to also store the size of the subtree rooted in $v$ supports both those operation in $O(\log n)$ worst-case time per operation.

To implement remove_random() simply generate a random number $k$ between $1$ and $n$ and find the element $e$ of rank $k$ in the tree. Then delete $e$ from the tree and return it.

$\endgroup$
9
  • 7
    $\begingroup$ I wonder why you didn't put the dynamic size array first, as it's clearly the better option over AVL. $\endgroup$
    – justhalf
    Nov 23 at 7:21
  • 4
    $\begingroup$ @justhalf. I swapped the two options. The AVL approach is not completely dominated by the array approach since the complexity of the array approach is amortized. $\endgroup$
    – Steven
    Nov 23 at 8:58
  • 3
    $\begingroup$ Noted. I would say that amortized constant time is usually better than log n worst case, especially since in this case the array approach is much simpler than AVL, but you have a point too, for example in the system where memory might not be so cheap, AVL might get better memory utilization due to its pointer structure compared to the required contiguous memory by the array. $\endgroup$
    – justhalf
    Nov 23 at 9:16
  • 7
    $\begingroup$ @Steven The AVL approach is dominated in terms of runtime. If non-amortized O(1) time is needed, you can do it with a bit more wasted space. What you need is two dynamically sized arrays $A$ and $B$, with $B$ having double the capacity of $A$. Then, whenever you do an operation on $A$, duplicate the same operation on $B$. When $A$ gets full, swap pointers $A$ and $B$ and replace $B$ with an uninitialized allocation twice as large as $A$. Finally whenever we swap $A$ and $B$ set an index $i$ to 0, and on any operation set $B[i] = A[i]$ and $i = i + 1$ to explicitly amortize. $\endgroup$
    – orlp
    Nov 23 at 13:22
  • 5
    $\begingroup$ @orlp. Thanks! I know about this trick and I have even used it before. A tricky detail is that it requires the additional assumption that a block of $n$ contiguous words of unallocated memory can be reserved in constant time. This is clearly true in the word-RAM model of computation where the memory is just an infinite array of words indexed by their address and all words are available for our algorithm to use, but might not be true in practice. (To be fair I'm not even sure if it's reasonable to assume that $n$ words can be reserved in $O(n)$ time in practice). $\endgroup$
    – Steven
    Nov 23 at 13:51
15
$\begingroup$

Since you clearly don't care about the order of elements changing, I think the simplest approach is to use a resizable array (like C++'s std::vector or Java's java.util.ArrayList). When you remove an element, if it's not the last element, you just move the last element to take its place.

That gives amortized-constant-time add and constant-time remove_random.

For example, in Java:

public final class Example<E> {
    private final Random random = new Random();
    private final ArrayList<E> elements = new ArrayList<>();

    public void add(final E elem) {
        this.elements.add(elem);
    }

    public E removeRandom() {
        if (this.elements.isEmpty()) {
            throw new NoSuchElementException();
        }
        final int n = this.elements.size();
        Collections.swap(
            this.elements,
            this.random.nextInt(n),
            n - 1);
        return this.elements.remove(n - 1);
    }
}
$\endgroup$
4
  • $\begingroup$ Wouldn't generating the random value for remove_random be O(log(n))? $\endgroup$ Nov 24 at 15:35
  • $\begingroup$ Use a sentinel for pseudoremoval $\endgroup$
    – jermenkoo
    Nov 24 at 16:51
  • 2
    $\begingroup$ @SolomonUcko: The question specifies to "Assume we can generate random numbers for free." $\endgroup$
    – ruakh
    Nov 24 at 18:30
  • 2
    $\begingroup$ @jermenkoo: Why? $\endgroup$
    – ruakh
    Nov 24 at 18:30
9
$\begingroup$

Another solution that provides amortized constant time operations is to use a dynamic array with insertion and removal at the end, just as in Steven's answer, but swap the last element with a random one after insert, instead of before removal as in Steven's method.

That is, instead of doing what Steven suggests (in pseudocode):

public method insert(element):
   array.push_to_end(element)

public method remove_random():
   swap_last_with_random()
   return array.pop_from_end()

private method swap_last_with_random():
   i = array.length - 1
   j = random(min: 0, max: i)
   array.swap_elements_at(i, j)

you can equivalently do:

public method insert(element):
   array.push_to_end(element)
   swap_last_with_random()

public method remove_random():
   return array.pop_from_end()

with swap_last_with_random() defined as above.

Both of these implementations can be easily shown to work correctly by induction, and they have the same asymptotic time complexity, but their performance in practice may differ.

In particular, with my implementation, multiple consecutive removals require only reading elements sequentially from the end of the array and no writes to the array at all, which might yield a more cache-friendly access pattern. Also, the fact that my method doesn't need to modify the contents of the array during element removal could potentially make implementing efficient concurrent access easier (although it's still not trivial, since removal still changes the length of the array).

All that said, I make no claim that this method is actually any faster in practice than Steven's approach. Depending on your access patterns, it could even be slower. But if performance matters, it's at least worth comparing both of them.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.