I have a set in Python and I want to sample one element from it, like with random.sample() method. The problem is that sample() converts set to tuple internally which is O(n) and I have to do it in the most optimal way.
Is there a function that I can use to sample an element from a set with time complexity O(1) or the only way to do this is by creating your own implementation of set?
Because the data layout is irregular, it’s impossible to uniformly sample from a hash-based set in O(1) except, in the case of ω(n) queries, by preprocessing it into some sort of array. (Such an array could be maintained while building the set, of course, but that’s not the starting point given and isn’t faster to add than the tuple conversion.)