如何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, 这里
面有什么技巧吗？

我有一种方法是二分查找的。感觉搜索过程是logk

1. 
   
2. import itertools, bisect, random
   
3. 
   
4. def weighted_sample(values, probs):
   
5.     cumulative_probs = [0.0] + list(itertools.accumulate(probs))
   
6.     interval_idx = bisect.bisect(cumulative_probs, random.random()) - 1
   
7.     return values[interval_idx]
   
8. 
   
9. values = [3, 5, 7, 11]
   
10. probs = [9/18, 6/18, 2/18, 1/18]
    
11. 
    
12. 
    
13. d = {}
    
14. 
    
15. for _ in range(1000000):
    
16.     value = weighted_sample(values, probs)
    
17.     d[value] = d.get(value, 0) + 1
    
18.    
    
19. print(d)
    
20. 
    
21. {5: 332339, 3: 501134, 7: 110865, 11: 55662}

复制代码

YZDH 发表于 2021-1-18 08:21
我有一种方法是二分查找的。感觉搜索过程是logk

[mw_shl_code=python,true]

你的解法是with replacement情况下，二分可以做logk。这个是without replacement， 我不知道怎么可以在logk时间内更新 cdf 数组

感觉没有更好的办法，每次sampling都需要O(N)来update cdf

有一种方法可以做到 O(log(k)) 来update cdf, 用 fenwick tree/ binary indexed tree 来存prefix sum 以及query。但是缺点是，query单个prefix sum 的时间会从O(1) 增加到 O(log(k)), 每次operation的时间会增加到 O(log(k)^2)

用heap吧。
我assume题的意思是sample logk但是init复杂度另算

lilianzcc 发表于 2021-1-18 11:57
用heap吧。
我assume题的意思是sample logk但是init复杂度另算

heap key用什么呢？heap size取k吗？

AbelEinzbern 发表于 2021-1-18 10:32
有一种方法可以做到 O(log(k)) 来update cdf, 用 fenwick tree/ binary indexed tree 来存prefix sum 以及q ...

嗯嗯，我面试的时候提到过这个，反馈不明显。似乎面试官脑子中的思路不是从数据结构的角度来提示，感觉像是数学思路来解决