写给自己看的Paxos/Raft笔记

这篇文章主要记录自己对Paxos/Raft的一点不成体系的理解,不是写给别人看的,所以不会有专门的图表。起因是学习它们的过程比较痛苦,啃过论文也看了不少别人的理解,但问题始终没有解决:1. 想编程实现它们”似乎”比较简单;2. 想知道它们为什么正确却很困难;3. 第2点导致了第1点”实际”并不简单。网上的文章大部分是基于”抢锁”或者”选主”这类角度来剖析的,虽然方便鸟瞰其大致过程,但是不利于理解其正确性。 [继续阅读]
标签: 技术 算法

聊聊一看就会一写就跪的二分查找

图书馆自习的时候,一个女生背着一堆书走进阅览室,结果警报响了。阿姨让女生看是哪本书把警报弄响了,女生把书倒出来,一本一本地测。阿姨见状急了,把书分成两份,第一份过了一下,响了。又把这一份分成两份接着测,三回就找到了。阿姨用鄙视的眼神看着女生,仿佛在说 O(n) 和 O(log n) 都分不清。 [继续阅读]
标签: 技术 算法

关于AVL树和红黑树的一点看法

AVL树和红黑树是两类重要的二叉查找树,关于它们孰优孰劣,人们往往众说纷纭莫衷一是。本文从空间开销、实现难度和时间开销(最坏/均摊/期望)等多个维度进行了细致而具体的比较,最终得出结论:AVL树和红黑树在不同的场景下均有各自的微弱优势,但几乎不可能形成碾压。工程实践本身是个充满了 trade-off 的过程,与其武断(却毫无底气)地说哪一个更好,深入探究它们底层隐藏的奥秘恐怕会更有趣一些。 [继续阅读]
标签: 技术 算法

An Erlang Syntactic Sugar Library

Motivation 我大概是在2014年的时候认识Erlang的,并且深深爱上了这个为我解决许多工作难题的”微型操作系统”。但在和别人的交流中,我也听到一些对于Erlang的抱怨,其中最多的竟然是关于它的语法!直到有一天我发现一个开源日志库Lager,里面有一个技巧就是利用编译参数parse_transform对源代码按照自己的意愿进行转换。于是我去查阅了parse_transform的相关资料,并且写下了这个项目ESugar:一方面它作为DEMO展示了原来利用parse_transform我们还可以做许多很酷的事情;另一方面你也可以把它当做一个Erlang的语法糖库拿去使用或者扩展。 [继续阅读]
标签: 技术 编程

Y Combinator (续前一篇Lambda)

这篇文章是对前一篇An Online Lambda Interpreter的续写,搞清楚 Y Combinator 这个概念的来龙去脉。当然这两篇文章里的 lambda 演算语法定义实际上并不是标准的定义,具体的标准定义与实现我在这个目录做了单独实现。 [继续阅读]
标签: 技术 编程

知乎备份:如何在七天之内学会Erlang

如何在七天之内学会Erlang? 众所周知,上海的冬天实在是太冷了。 我穿棉袄开空调盖两层被子却依然每天都冻得瑟瑟发抖。 所以我决定学Erlang, 年后去温暖的广州做页游服务端。 那么,我应该如何在七天之内学会Erlang呢? 求教,真诚的。 [继续阅读]
标签: 随笔 编程

知乎备份:绝地求生赢家的期望人头

n个水平相同的人参加大逃杀游戏,最后赢家所消灭玩家数的期望值是多少? 记X为每局最后胜利者在本局游戏中所击杀的玩家数,求X的期望。 在以上条件下X的期望可求吗?如果不可求,那么至少要补充什么条件? 在X期望可求的条件下,“玩家水平相同”的严格定义是什么呢? [继续阅读]
标签: 技术 数学