0

I need a data structure for adding items, removing items, and picking a random item.

From what I've read, I think picking a random item from a list with random.choice takes constant time. However, removing an item from a list takes O(n) time.

On the other hand, removing and adding an item from/to to a set take O(1) time, but picking a random element from a set with random.sample takes O(n) time.

Is there a way to support those three operations in O(1) time?

Myath
  • 553
  • 1
  • 6
  • 23

1 Answers1

0

Why not use a dict? I know it's a little weird, but on average dict lookup and insertion is O(1). And you can use random.choice on it as it supports indexing!

Here is a graph showing the amount of time it takes to use random.choice on a dict. The x-axis is the size of the dict and the y-axis is time.

enter image description here

Shay Lempert
  • 311
  • 2
  • 9
  • From the source code, `random.choice(d)` picks a random integer from integer `i` from 0 to `len(d)` and returns `d[i]`. If you suggest using items as keys and the items are not integers, then this would result in KeyError. – Myath Mar 09 '19 at 20:25
  • You could use a unique integer for each element. For example the time.time at which it was inserted. – Shay Lempert Mar 09 '19 at 20:29
  • Let's say `d[0] = item0` and `d[2] = item2`. This could result in KeyError if `d[1]` is called and `d[2]` would never be picked. Again, the data structure needs to support quick add and remove as well. – Myath Mar 09 '19 at 20:34
  • You are correct.. – Shay Lempert Mar 09 '19 at 20:36
  • An alternative could be to use a counter, and use it as the key of each element. It's not the prettiest solution, but it is efficient. – Shay Lempert Mar 09 '19 at 20:37
  • What would I do for removing an element? – Myath Mar 09 '19 at 20:38
  • Removing an element is another problem.. I may have overlooked it. A solution could be to have a sort of "hash" function to use on elements. It's use will be in generating the keys for insertion and deletion of elements from the dict. For example if you turn "hello World" into the key 5 using this "hash", you will be able to use it for `dict[5] = "hello World"` and `del dict[5]`. Both operation being O(1). The hash function being the only bottleneck. – Shay Lempert Mar 09 '19 at 20:46