1

Say I have a simulation that needs to pick between many discrete events with given weights, with the weights themselves following a known distribution.

I need some structure that supports updates, and efficiently picks random events.

It is trivial to get O(log(n)) insertion, deletion, and random-choice operations, with a binary search tree. It should be possible to improve the random-choice operation, with interpolation search for example.

What are some theoretical results stronger than this, or known good implementations?

EDIT: I consider Niklas's reply to this comment about the O(log* n) algorithm (ftp.cs.brown.edu/pub/techreports/92/cs92-36.pdf)to be exactly what I was looking for.

adomurad
  • 11
  • 3
  • And what is your programming language? – Lrrr Oct 30 '14 at 07:28
  • C++ I suppose, but it doesn't matter to me, I'm more interested in the theoretical aspect. – adomurad Oct 30 '14 at 07:30
  • The support for insert/delete is a strong assumption which leads me to the intuition that O(log n) is already pretty good. Have you looked at B-trees instead of classical balanced BSTs? – Niklas B. Oct 30 '14 at 09:36
  • I'm looking for something that specifically exploits the fact that weights are known for random choice. For example, a data structure that bins logarithmically and tries to get away with O(1) some >50% of the time. – adomurad Oct 30 '14 at 13:28
  • Solutions such as the [alias method](https://en.wikipedia.org/wiki/Alias_method) can do the random selection operation in O(1), but need some preprocessing after an insert/delete. (Preprocessing costs O(n) if you start from scratch, but it might be possible to do somewhat better by keeping some structure from the previous set up.) If you expect to do many more random selections than inserts/deletes, there might be something there... but I can't think of a way to do it. Yet. – Erik P. Oct 30 '14 at 20:15
  • ftp://ftp.cs.brown.edu/pub/techreports/92/cs92-36.pdf seems to provide practical dynamic discrete random sampling in O(log* n) per operation, which is asymptotically much better than what you have. – Niklas B. Oct 31 '14 at 02:26
  • Thanks guys. You can post as answers if you'd like. – adomurad Nov 01 '14 at 23:43

0 Answers0