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

 撩人的东莞博文 发布于 2022-10-26 22:40

hi,all

最近在看redis的代码(huangz注释过的),是2.6版本的。在看到t_zset.c这个文件的时候,了解到跳跃表的概念,大概原理是懂的,但是不太了解这个生成随机层数的算法原理。不知道有没童鞋能介绍下这段代码其实是怎么做到模拟幂次定律的?


/* Returns a random level for the new skiplist node we are going to create. * The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL * (both inclusive), with a powerlaw-alike distribution where higher * levels are less likely to be returned. * * 返回一个介于 1 和 ZSKIPLIST_MAXLEVEL 之间的随机值,作为节点的层数。 * * 根据幂次定律(power law),数值越大,函数生成它的几率就越小 * * T = O(N) */ int zslRandomLevel(void) { int level = 1; // TODO 了解这个公式背后的数学原理 while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF)) level += 1; return (level
1 个回答
撰写答案
今天,你开发时遇到什么问题呢?
立即提问
热门标签
PHP1.CN | 中国最专业的PHP中文社区 | PNG素材下载 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有