记录历史：持久化数据结构
文本编辑器里的 "undo" 和 "redo"，数据库系统的 MVCC，git 的历史记录，mac 的 Time Machine，等等功能，他们都有一个共同点，就是记录历史。这个功能依赖一种数据结 构：持久化数据结构 (Persistent data structure)。持久化数据结构记录所有历史版本， 你可以读取任…
algorithms 分类归档
共 5 篇文章 · 返回首页
关于二分查找算法
二分查找，也叫 binary search，half-interval search，logarithmic search， binary chop，是在可随机寻址的有序列表中根据元素的值查找元素的位置的算法。它拥有和 排序二叉树相似的查询效率，也就是 $O(\log n)$ 的时间复杂度。通俗的讲，在一个长度为 $n…
如何计算高频页面
高频数据项问题 (Heavy Hitters)，在互联网时代有许多应用场景，如计算热门 商品、计算热搜、识别高流量的TCP流、识别高频交易的股票。计数再排序的方 法太消耗内存了，本文介绍一个 \( O(n) \) 时间，常量空间的概率算法，解决 这个问题。
字符串匹配算法: kmp和bm算法
字符串匹配，是开发工作中最常见的问题之一。它要求从一个较长的字符串中查找一个较短 的字符串的位置。例如从字符串 $Tbacbababaabcbab$ 中查找字符串 $Pababaca$ 的位置。 $T$ 称为主串， 字符串 $P$ 称为模式串。
正则表达式
正则表达式，是计算机科学史上闪闪发光的优秀理论：有好的理论，好的代码， 好的程序，应用广泛。70 年代末，正则表达式已经成为 unix 的关键特性，并 且拥有大量以正则表达式为主要功能的优秀程序： ed, sed, grep, egrep, awk, lex。如今，正则表达式在程序设计中被广泛使用。