IT夜航船

天下学问，惟夜航船中最难对付

  • 写给自己看的Paxos/Raft笔记

    Posted on 2021-10-31

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

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

    Posted on 2021-01-08

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

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

    Posted on 2019-11-23

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

  • An Erlang Syntactic Sugar Library

    Posted on 2019-11-22

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

  • Y Combinator (续前一篇Lambda)

    Posted on 2019-11-20

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

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

    Posted on 2018-02-12

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

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

    Posted on 2018-02-01

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