G家电面

yawnzh 发表于 2015-8-28 04:14
你可以直接random一个0-1的数，然后除以区间的大小就可以得到区间的index了，然后再在这个区间找这个随机 ...

明白了 谢谢！
不过这样是不是存在一种极端情况，比如有4个id，概率分别是1/16, 5/16, 5/16, 5/16，这样预处理之后第一个区间还是有四个id，也就是说有可能某一个区间会出现有n个值的情况，查找的时候还是log(n)的复杂度，这种应该算可能出现的问题吧？

w41q 发表于 2015-8-27 12:22
明白了 谢谢！
不过这样是不是存在一种极端情况，比如有4个id，概率分别是1/16, 5/16, 5/16, 5/16，这样 ...

为什么会有四个id呢，你这样分区间大小是多少啊？如果区间长度是0.5，那么第一个区间是【1/16, 3/8, 1/2】，第二个区间是【11/16, 1】。某个区间有n个值的情况只可能发生在第一个或者最后一个id的概率大于n-1个区间长度的和的时候吧。

yawnzh 发表于 2015-8-28 04:31
为什么会有四个id呢，你这样分区间大小是多少啊？如果区间长度是0.5，那么第一个区间是【1/16, 3/8, 1/2 ...

呃，n个id n个区间 每个区间1/n，对应到例子里就是每个区间都是1/4的大小，lz原帖里就是这个意思吧？

yawnzh 发表于 2015-8-28 04:31
为什么会有四个id呢，你这样分区间大小是多少啊？如果区间长度是0.5，那么第一个区间是【1/16, 3/8, 1/2 ...

我明白了 咱俩预处理方式不一样。。
如果按照你的方式 概率分别为 1/16, 1/16, 1/16, 13/16时 第一个区间就是四个id了。。

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

分配完之后为什么要取每个bucket 中probability 最大的id 输出呢?

hj867955629 发表于 2015-8-26 11:53
就二分去查找区间吧

请问怎么用二分查找优化啊，能详细点不？谢谢啦

走路草May 发表于 2015-8-28 13:30
请问怎么用二分查找优化啊，能详细点不？谢谢啦

就是本来你要一个区间一个区间的从第一个区间开始去比较，二分就是每次取中间那个区间，用它边界去比较

hj867955629 发表于 2015-8-28 13:44
就是本来你要一个区间一个区间的从第一个区间开始去比较，二分就是每次取中间那个区间，用它边界去比较

明白了，非常感谢！

say543 发表于 2015-8-28 12:18
分配完之后为什么要取每个bucket 中probability 最大的id 输出呢?

因为现在的优化是希望能够用O(1)时间返回一个id，并且保证这个id的生成概率符合之前给定的概率分布。
如果一个桶里有多个id，还不知道输出哪个id，这个优化的O(1)目标就无法达到了
所以一个桶里只放2个id，没选中一个桶，直接输出概率大的id,这样保证了O(1)时间，同时可以证明生成概率符合之前给定的分布，证明似乎有点复杂，不过说出区间查找方法之后，说这个方法，可以跟interviewer讨论的

alittlesheep 发表于 2015-8-29 10:35
因为现在的优化是希望能够用O(1)时间返回一个id，并且保证这个id的生成概率符合之前给定的概率分布。
如 ...

受教了 原来能够证明以lz的例子来说
桶0： (0.2(id1)+0.13(id3)) >> id1
桶1： (0.3(id2)+0.03(id3)) >> id2
桶2： （0.33(id3)） >> id3

第一次random 出0.23 输出id 1 第二次ranmdom 出0.25 也是输出id1 吗?

另外有个case 想讨论如果id1 id2 id3 probabilitys = 0.3 0.35 0.35. 这样一个桶为了要平均就不会只有一个id lz的方法还能用吗? 感谢讨论~~