锐客网

  1. 首页 > it技术 > >

Probabilistic|一次遍历等概率选取字符串中的某个字符

algorithmProbabilisti

http://blog.chinaunix.net/uid-7921481-id-3022614.html
存在一个等概率的0、1发生器。
给一个文本流，给定一个指定的字符'x'，写一个函数，等概率地返回'x'的一个文本流偏移（就是'x'在字符串中的位置，比如文本为 axbx，那么x的偏移为{1, 3}，最后你需要获得1或者3，概率分别为1/2
假设文本流每个字符1字节）

============================基本问题=========================================
-----------------------------------------------------------------------------
已知等概率的0-1生产器uint make0~1()，求等概率的0~n生产器uint make0~n(uint n)
uint make0~n(uint n)
{
//...
//make0~1();
//...
return ?; //
}
具体什么方法使得make0~n最高效还是大家去想吧。。。
这里高效的意思是很快就能够返回结果。
-----------------------------------------------------------------------------
=============================================================================
【方法一】
设共有N个字符.
for(; ; )
{
产生0~N-1的随机数r
if(A[r]=='x') return r;
}
分析：因为0~N-1是等概率的，产生'x'的位置也是等概率的.
缺陷：循环return的概率是R/N (R为'x'的个数)
若N超级大R很小,for循环很难return.

【方法二】
1：vector a_pos; //从头到尾记录'x'出现的位置
2：这里有R==a_pos.size(). 产生0~R-1的随机数r
3：取a_pos[r]即可。
缺陷：当R很大时空间开销很大。
比方法一的优势在于： 这个无须循环一下就可return.

【方法三】
先遍历一遍字符串，记下有'x'出现的次数为R；
产生0~R-1 的随机数 r
再遍历一遍字符串获取第r个'x'的位置
缺陷：最坏情况要遍历两遍字符串
优势：克服了方法一和二的缺陷

=========面试官会问，还有没有更好的方法=========================
【方法四】
有没有只遍历一遍就OK的方法呢？
直观的，我们每碰到一个'x'，设当前碰到的'x'的位置是i，我们可以以某个概率p去获取这个
'x'。此时获取'x'的概率绝对不是1/R，因为我们还不知道R的确切数字呢。
我们仍然需要继续遍历i之后的字符串，然后覆盖之。。。
于是列个方程组（*），获取第一个的概率是P(1)，获取第i个的概率是P(i)，获取第R个的概率是P(R)
满足：
P(1)(1-P(2))(1-P(3))...(1-P(R))=1/R
P(2)(1-P(3))...(1-P(R))=1/R
P(3)(1-P(4))...(1-P(R))=1/R
...
P(R-1)(1-P(R))=1/R
P(R)=1/R
上述方程组的思想是：每个字符获取的概率为1/R,遍历到它时能获取它，其后的所有该字符都不会获取。
求P(i)，得：
P(R)=1/R
P(R-1)=1/(R-1)
P(R-2)=1/(R-2)
...
P(2)=1/2
P(1)=1
于是乎，碰到第一个'x'就取，碰到第二个就以1/2的概率去取（若概率发生，就更新当前的'x'的位置），
...第R个'x'就以1/R的概率去取，于是乎完成操作。
优势：遍历一遍
缺陷：每碰到一个指定的字符都需要产生相应的随机数（产生等概率的随机数的最高效的算法是什么呢？）
注意了：对于一个文本流，在该流没有流完之前，你不知道该流总共有多少个字符，你也不知道总共有多少个指定的字符，并且只流一次（不会再流一次），因此，方法一和方法三都不行不通。

http://www.cnblogs.com/DeadKnight/archive/2010/06/21/1762190.html
题：
给你一个字符串（可能有几亿个字符），给定一个特殊的字符'a'，再给定一个可以产生0和1的随机数发生器，然后让你写一个函数，等概率地返回'a'的一个索引（就是'a'在字符串中的位置，比如字符串为 aaba，那么a的索引为{0, 1, 3}，等概率地返回0、1或者3）

想：
最简单的想法：这个如果产生随机数，再把该随机数哈希到字符串长度范围内，再把得到的哈希值作为下标去看对应的字符满足不满足条件，满足条件则返回下标，不满足条件的话重新随机。缺点——如果满足条件的字符很少，那么完全不靠谱！
稍微容易想到的方法：遍历这个字符串，对满足条件的下标建立索引，然后根据索引大小产生随机数，随机访问索引，返回索引所对应的下标值。这个可以有，但是也有明显缺点——如果满足条件的字符很多，那么索引很大，占用大量存储！
最后就是完美的解答了：

答：
【Probabilistic|一次遍历等概率选取字符串中的某个字符】

#include #include #include #include using namespace std; int given_rand() { return rand() % 2; }unsigned int my_rand() { int i, result; for( i = 0, result = 0 ; i < 32 ; i++ ) { result <<= 1; result += given_rand(); } return result; }int main() { int index = 0, cnt = 0; stringstream strstring("aabbbaaabbbbabbbbabbbbbbbbbbbaabbbbbbb"); int ret = 0; char c; srand(time(NULL)); while (strstring >> c) { index++; if (c == 'a') { ++cnt; int rr = my_rand() % (cnt); if (rr < 1) ret = index; }} cout << ret; return 0; }

    推荐阅读


    上一篇：Android|Android 图片压缩即生成缩略图方法-BitmapFacotry.Options。

    下一篇：你应该知道的|你应该知道的 5 种 TypeScript设计模式