Lol I read the OP and knew there had to be matchmaking involved. I don’t think I fully understand the use-case here but putting that aside for a moment…

This is what I was going to suggest, but I see you figured it out first I was feeling so clever, too!

But why do you have to sample from the start? Sample from a random index in the uniform space and just scan until you hit the quota. Wrap around if you hit the end.

I don’t think this is equivalent to a true random sample but for this use-case I don’t think anyone will be able to tell.

Edit: Actually if you choose 100 random indices and call :ets.next_lookup() with them (instead of scanning from the first) I think this would be a truly random sample. Right?

1..100
|> Enum.map(fn _ -> Enum.random(1..1_000_000) end)
|> Enum.map(fn i ->
  {_, [{_, value}]} = :ets.next_lookup(table, i)
  value
end)

Of course you could get duplicates but there are ways to deal with that.

Since the keys are already truly random there should be no bias from adding/removing users, no matter which users they are.

I meant “draw” in the lottery sense:

• get an index with Enum.random(1..current_max)
• fetch the element with that key
• if no element, try again

This would work fine for systems with infrequent deletions, since most of the time the first lookup succeeds.

It would be extremely BAD for a high-churn system, since current_max would be increasing constantly but the table is mostly unoccupied. The average runtime of a “pick a random user” would just get worse and worse…

I think it should be pretty efficient due to the :ordered_set, which should get you O(log n). Only way to know for sure is to test in your specific use case.

As @garrison pointed out though this scheme might not be rigorously uniform. Some simulation testing might be helpful to confirm it’s fairness.

For matchmaking wouldn’t you want to prefer people having waited longer over people just having joined the queue? Also would there really be a million people waiting in the queue or rather be a million people playing? If you form couples quickly enought the queue might stay at a reasonable size.

Ah yes, you can start at a random location by generating a fake key and then wrap around. That seems to fix the problem. I updated the GitHub gist above with this idea… code was done in haste, so don’t judge me too hard