当前位置: 首页 > news >正文

建筑网站排行榜wordpress菜单图标左右

建筑网站排行榜,wordpress菜单图标左右,那个网站科四做课时,网站制作自助转载#xff1a;https://www.cnblogs.com/lnlvinso/p/8848883.html 结果#xff1a;skiplist的高度是个随机值。 SkipList理解 记下自己对跳表SkipList的理解。 SkipList采用空间换时间的思想#xff0c;通过增加数据间的链接#xff0c;达到加快查找速度的目的。 数据库L…转载https://www.cnblogs.com/lnlvinso/p/8848883.html 结果skiplist的高度是个随机值。 SkipList理解 记下自己对跳表SkipList的理解。 SkipList采用空间换时间的思想通过增加数据间的链接达到加快查找速度的目的。 数据库LevelDB和RocksDB中用到了SkipListRedis中的有序set即zset也用到了SkipList。Java中也提供了ConcurrentSkipListMap在并发量大的情况下ConcurrentSkipListMap性能好。 先看SkipList的查找过程引用网上的经典图片查找19。注意的是数据是有序的。 查找的过程从上至下查找指针所经历的位置顺序如图中的123直到找到目标数据19。 再加一张图是怎么二分法查找的。 SkipList中创建新结点时产生一个在1~MAX_LEVEL之间的随机level值作为该结点的level。每个节点的高度是随机的。 MAX_LEVEL可以静态指定也可以动态增长。 关于MAX_LEVEL觉得这篇文章的解释是比较清楚的https://blog.csdn.net/kisimple/article/details/38706729。下面是复制了部分的内容 每个节点所能reach到的最远的节点是随机的正如作者所说SkipList使用的是概率平衡而不是强制平衡。 O(logN)? 既然是随机算法那怎么能保证O(logN)的复杂度SkipList作者在论文中有给出了说明这里从另一个角度说下我的理解。先定义一下A node that has k forward pointers is called a level k node。假设k层节点的数量是k1层节点的P倍那么其实这个SkipList可以看成是一棵平衡的P叉树从最顶层开始查找某个节点需要的时间是O(logpN)which is O(logN) when p is a constant。 下面看下Redis与LevelDB中实现SkipList所使用的随机算法。 Redis 在t_zset.c中找到了redis使用的随机算法。 /* 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. */ int zslRandomLevel(void) {int level 1;while ((random()0xFFFF) (ZSKIPLIST_P * 0xFFFF))level 1;return (levelZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL; } 执行level 1;的概率为ZSKIPLIST_P也就是说k层节点的数量是k1层节点的1/ZSKIPLIST_P倍。ZSKIPLIST_P这个P是作者论文中的p与ZSKIPLIST_MAXLEVEL在redis.h中定义 #define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^32 elements */ #define ZSKIPLIST_P 0.25 /* Skiplist P 1/4 */ 所以redis中的SkipList相当于是一棵四叉树。 LevelDB 在skiplist.h中找到了LevelDB使用的随机算法。 templatetypename Key, class Comparator int SkipListKey,Comparator::RandomHeight() {// Increase height with probability 1 in kBranchingstatic const unsigned int kBranching 4;int height 1;while (height kMaxHeight ((rnd_.Next() % kBranching) 0)) {height;}assert(height 0);assert(height kMaxHeight);return height; }(rnd_.Next() % kBranching) 0)的概率为1/kBranching所以LevelDB中的SkipList也是一棵四叉树kBranching 4;不就是这个意思吗^_^。 总结skiplist是有序的采用类似二分法方式进行查找。查找、插入的平均时间复杂度是O(ln2)。
http://www.huolong8.cn/news/84254/

相关文章:

  • 天津网络优化网站建设展位设计
  • linux版本的wordpress网站sem优化怎么做
  • 吉林企业网站模板建站哪个好学网络推广哪个培训机构好
  • 域名备案用的网站建设方案app推广赚佣金
  • linux网站建设技术指南 pdf兰州公司做网站的价格
  • 国内著名网站建设公司wordpress 图片打开慢
  • 购物网站建设推进表dede网站底部
  • 淘金网站建设网站建设的战略作用
  • 搜索引擎网站有哪些郑州做营销型网站公司
  • 选一个网站做seo南开集团网站建设
  • 网站建设与管理职责wordpress onedrive
  • 做网站报价明细表服务器租用多少钱一个月
  • 秦皇岛企业建网站网站备案查询工信网
  • 大学 两学一做专题网站四川省建设招标网站首页
  • 网站开发项目的里程碑述建设一个网站的具体步骤
  • 高端定制网站cms网站搭建
  • 石家庄模板建站代理wordpress下载的插件怎么用
  • 郑州网站改版公司怎么建设食品网站
  • 买了虚拟主机怎么做网站百度排名优化专家
  • 北京 科技网站建设微信营销管理工具
  • 建设银行可以查房贷的网站简单制作网站的过程
  • 阳山网站建设建设环保网站的目的与功能分析
  • 山东网站建设排行榜sem可以为网站建设做什么
  • 局域网内的网站建设深圳宝安seo外包
  • 网站建设做的好处购物网站怎么经营
  • 网站内容页301如何做企业文化建设总结报告
  • 网站搜索百度世界排名
  • 有经验的合肥网站建设小程序token
  • 渭南市建设局网站修改wordpress 表格
  • 长沙百度网站推广优化网站建设公司的前端