An efficient data structure for access by ID and finding the weighted random item

user_1915854 0
Viewed 85

Could you, please, help me with the data structure that allows O(logN) (or at least O(sqrtN)) operations for the following:

  1. Insert an item having ID (int64_t) and health (double)
  2. Remove an item by ID
  3. Find an item that is weighted random by health

The preferred language is C++ or C. By the weighted random I mean the following:

Consider totalHealth=Sum(health[0], health[1], ..., health[N-1]). I need a fast (as described above) operation that is equivalent to:

  1. Compute const double atHealth = rand_uint64_t()*totalHealth/numeric_limits<uint64_t>::max();
  2. Iterate over i=0 to N-1 to find the first i such that Sum(health[0], health[1], ..., health[i]) >= atHealth

Constraints: health[i] > 0, rand_uint64_t() returns a uniformly distributed integer value between 0 and numeric_limits<uint64_t>::max().

What I have tried so far is a C++ unordered_map that allows quick (Θ(1)) insertion by ID and removal by ID, but the operation #3 is still linear in N as described in my pseudo-code above.

You help is very appreciated!

data-structures algorithm c++ performance
1 Answers

I can't think of a way to do it with the existing STL containers but I can think of a way to do it if you're willing to code up your own binary tree. The trick is that each node maintains the total health of all the nodes to its left (it doesn't need to worry about nodes to its right as you'll see below). Then, if you walk the tree in ID order you can also compute the "cumulative health", also in ID order, in log(n) time. So the tree is sorted by both ID and cumulative health and you can do lookups in log(n) time either by ID or by "cumulative health". For example, consider a very simple tree like the following:

         ID: 8
         h: 10
         chl: 15
   +-------|--------+
   |                |
   ID: 4          ID: 10
   h: 15          h: 7
   chl: 0         chl: 0

in the above h is the health of the node and chl is the cumulative health of all nodes to it's left. So the total health of all nodes in the above is 15 + 10 + 7 = 32 (and I assume you maintain that count separately though you could also track cumulative health of nodes the right and you wouldn't need to). Let's look at 3 cases:

  1. You compute an atHealth < 15. Then at the first node you can see that your value is less than the chl so you know you need to go left and you end up at the correct leaf.
  2. You compute an atHealth >= 15 < 25 so you know it's > 15 so you don't go left at the root, the node you're at has health 10 and 10 + 15 means the cumulative health at that node is between 15 and 25 so you're good.
  3. You compute an atHealth >= 25. Every time you visit a node and go right you must add the chl and h of the node you were at to keep computing cumulative health as you walk the tree so you know you're starting at 10 + 25 = 25 when you go right and you'll add that to the h or chl of any node you encounter after that. Thus you can quickly find that the node to the right is the correct one.

When you insert a new node you increment the total health of each parent node as you walk the tree and when you remove a node you walk back up the tree subtracting from the total health. Inserts and deletions are thus still O(log(n)) and lookups by ID are also log(n) either by ID or by atHealth.

Things obviously get more complicated if you want to maintain a balanced tree but it's still do-able.

user_14312440
Related