如何weighted sample without replacement

k种不同颜色的球，个数为[n1, n2, n3, ..., n_k]， 如何sample without
replacement？要求sample operation time complexity log(k)

class WeightedSample:
def __init__(self, num_balls):
pass

def sample(self):
pass # return a color in time complexity of log(k)

看了https://en.wikipedia.org/wiki/Reservoir_sampling 似乎也做不到logk, 这里
面有什么技巧吗？