记录历史：持久化数据结构
文本编辑器里的 "undo" 和 "redo"，数据库系统的 MVCC，git 的历史记录，mac 的 Time Machine，等等功能，他们都有一个共同点，就是记录历史。这个功能依赖一种数据结 构：持久化数据结构 (Persistent data structure)。持久化数据结构记录所有历史版本， 你可以读取任…
algorithms 标签归档
共 6 篇文章 · 返回首页
关于二分查找算法
二分查找，也叫 binary search，half-interval search，logarithmic search， binary chop，是在可随机寻址的有序列表中根据元素的值查找元素的位置的算法。它拥有和 排序二叉树相似的查询效率，也就是 $O(\log n)$ 的时间复杂度。通俗的讲，在一个长度为 $n…
如何计算高频页面
高频数据项问题 (Heavy Hitters)，在互联网时代有许多应用场景，如计算热门 商品、计算热搜、识别高流量的TCP流、识别高频交易的股票。计数再排序的方 法太消耗内存了，本文介绍一个 \( O(n) \) 时间，常量空间的概率算法，解决 这个问题。
字符串匹配算法: kmp和bm算法
字符串匹配，是开发工作中最常见的问题之一。它要求从一个较长的字符串中查找一个较短 的字符串的位置。例如从字符串 $Tbacbababaabcbab$ 中查找字符串 $Pababaca$ 的位置。 $T$ 称为主串， 字符串 $P$ 称为模式串。
一致性哈希的原理和历史
一致性哈希是现代分布式系统最常用的算法，它能让数据节点增减变化时，尽可 能地保持原来再某个节点上的数据仍然还在那个节点上。最初，一致性哈希被应用 peer-to-peer 网络上，最开始是Chord，后来也被用在 BitTorrent 上。如今， 所有的分布式数存储都用了，大概是 Amazon 的 Dynamo 的文章…
设计一个限流器
网络服务中，限流器用于控制一个客户端的请求频率或数据速率。速率限制 器常见的场景如下：