G家电面

yawnzh 发表于 2015-8-27 03:29
如果id太多不能都放到内存里的话，第一次二分查找区间，第二次在区间内二分查找，只需要把这个区间load到 ...

嗯，有道理

alittlesheep 发表于 2015-8-26 04:48
优化的话，大致是这样：
现在概率分布是 0.2 0.3 0.5
如果想在O(1)时间找出 random结果对应的区间

我开始想的是等分id的数量，没考虑等分概率因为觉得不大好等分，不过如果id很多的情况下，说明每个id的概率很小，等分概率的时候就算有点微小的偏差也应该无所谓，等分以后在每个组内normalize就好了吧。

alittlesheep 发表于 2015-8-26 20:48
优化的话，大致是这样：
现在概率分布是 0.2 0.3 0.5
如果想在O(1)时间找出 random结果对应的区间

这样的话感觉每个id的概率就相等了啊。。
可能是我没看明白，麻烦lz再解释下行不。。

alittlesheep 发表于 2015-8-26 04:48
优化的话，大致是这样：
现在概率分布是 0.2 0.3 0.5
如果想在O(1)时间找出 random结果对应的区间

开始没仔细看，你把卡在区间中间的概率分到了两个区间啊，这样做的话每个区间的概率之和都是精确相等的，应该是最好的答案吧，不过为什么要用minheap和maxheap?还有可能出现的问题那里也没懂。

yawnzh 发表于 2015-8-27 05:24
开始没仔细看，你把卡在区间中间的概率分到了两个区间啊，这样做的话每个区间的概率之和都是精确相等的， ...

每个区间的概率之和相等的话 每个id输出的概率不也就相等了？

我自己用python写了一下，这个是代码：

1. import random
   
2. class MyRandom(object):
   
3. 
   
4.     def __init__(self,a):
   
5.         m=int(len(a)**0.5)
   
6.         self.step=1/m
   
7.         self.groups=self.preprocess(a,int(len(a)**0.5))
   
8. 
   
9.     def get_random(self):
   
10.         groups=self.groups
    
11.         r=random.random()
    
12.         j=int(r/self.step)
    
13.         return groups[j][0]+self.binary_search(groups[j][1],r)
    
14. 
    
15.     def preprocess(self,a,m):
    
16.         groups=[[0,[]] for _ in range(m)]
    
17.         step=1/m
    
18.         sum=0
    
19.         j=0
    
20.         for i in range(len(a)):
    
21.             sum+=a[i]
    
22.             if sum<step*(j+1):
    
23.                 groups[j][1].append(sum)
    
24.             elif sum==step*(j+1):
    
25.                 groups[j][1].append(sum)
    
26.                 j+=1
    
27.                 if j<m:
    
28.                     groups[j][0]=i+1
    
29.             else:
    
30.                 groups[j][1].append(step*(j+1))
    
31.                 j+=1
    
32.                 groups[j][0]=i
    
33.                 groups[j][1].append(sum)
    
34.         return groups
    
35. 
    
36.     def binary_search(self,a,target):
    
37.         i=0
    
38.         j=len(a)-1
    
39.         while i<=j:
    
40.             mid=(i+j)//2
    
41.             if a[mid]==target:
    
42.                 return mid
    
43.             elif a[mid]>target:
    
44.                 j=mid-1
    
45.             else:
    
46.                 i=mid+1
    
47.         return i
    

复制代码

然后用一个大小为100和为1的数组进行测试，随机生成10000个数，统计频率然后跟给的概率进行比较：

1. a=[random.random() for i in range(100)]
   
2. while sum(a)>1 or 1-sum(a)>0.1**10:
   
3.     s=sum(a)
   
4.     a=[x/s for x in a]
   
5. sol=MyRandom(a)
   
6. count=[0]*10000
   
7. i=0
   
8. while i<10000:
   
9.     x=sol.get_random()
   
10.     count[x]+=1
    
11.     i+=1
    
12. f=[x/sum(count) for x in count]
    
13. e=[abs(f[i]-a[i]) for i in range(len(a))]
    
14. print(sum(e))

复制代码

补充内容 (2015-8-26 16:43):
有个地方写错了，应该是count=[0]*100。思想就是按楼主说的等概率分组。

w41q 发表于 2015-8-26 13:40
每个区间的概率之和相等的话 每个id输出的概率不也就相等了？

区间概率之和相等只是为了迅速找到随机数在哪个区间里面，这个区间还包含了很多id, 要继续用二分查找啊，概率怎么会一样呢。

yawnzh 发表于 2015-8-27 08:55
区间概率之和相等只是为了迅速找到随机数在哪个区间里面，这个区间还包含了很多id, 要继续用二分查找啊， ...

谢谢，如果我理解没错的话，思路是这样的对吗：
预处理之后输出id时，先random一个区间，然后在这区间里random一个数，做二分查找，在输出数所对应的id。

看来是要复习一些概率的基本知识，谢谢楼主啦

w41q 发表于 2015-8-27 10:30
谢谢，如果我理解没错的话，思路是这样的对吗：
预处理之后输出id时，先random一个区间，然后在这区间里 ...

你可以直接random一个0-1的数，然后除以区间的大小就可以得到区间的index了，然后再在这个区间找这个随机数