关于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期望可求的条件下,“玩家水平相同”的严格定义是什么呢? [继续阅读]
标签: 技术 数学

记一道有趣的CodeReview题目

这道题目是在千里码(不知道这野鸡网站现在还在不在),大意就是这段代码会因为某个特殊的随机种子而抛出异常,需要你找到这个随机种子。 如果只是想要过题 这也是我写这篇学习资料的初衷,如果只是想要过题的话这再简单不过了。根据题目的描述,是由于seed变量取了某个特殊值导致了异常。那么最直接的方法:遍历seed的所有可能取值不断try..catch,接着坐下来喝杯咖啡估计结果就出来了。我相信稍微有点编程基础的人都能够顺利解决,但是仅止步于此的话未免太可惜了。 [继续阅读]
标签: 技术 编程

知乎备份:8个小球用天平称16次排序

八个重量不相等的小球,每次只能放两个球到天平上,现如何只用16次将这八个球重量排序? 16次是可行的,因为8个球最多有8!中排序。然而测量16次,最多产生2^16种分支。8!< 2^16,故理论上可行。但是究竟要如何去称? [继续阅读]
标签: 技术 算法