redis的zslRandomLevel函数的实现原理是什么?

hi,all
最近在看redis的代码(huangz注释过的),是2.6版本的。在看到t_zset.c这个文件的时候,了解到跳跃表的概念,大概原理是懂的,但是不太了解这个生成随机层数的算法原理。不知道有没童鞋能介绍下这段代码其实是怎么做到模拟幂次定律的?
/*Returnsarandomlevelforthenewskiplistnodewearegoingtocreate.
*Thereturnvalueofthisfunctionisbetween1andZSKIPLIST_MAXLEVEL
*(bothinclusive),withapowerlaw-alikedistributionwherehigher
*levelsarelesslikelytobereturned.
*
*返回一个介于1和ZSKIPLIST_MAXLEVEL之间的随机值,作为节点的层数。
*
*根据幂次定律(powerlaw),数值越大,函数生成它的几率就越小
*
*T=O(N)
*/
intzslRandomLevel(void){
intlevel=1;
//TODO了解这个公式背后的数学原理
while((random()&0xFFFF)<(ZSKIPLIST_P*0xFFFF))
level+=1;
return(level}
繁花如伊
浏览 662回答 2
2回答
打开App,查看更多内容
随时随地看视频慕课网APP

相关分类

JavaScript