psyduck's memo
Dynamo paper notes

Paper link

Hexo workflow

I recently migrated this blog from Workdpress to hexo which is light-weighted and suitable for raspberry-pi.

BitTree: a more powerful bitset

Recently I ran into a problem that asks for a data structure that efficiently allocate and recycle integer id in [0, MAX_ID). Each id can be allocated again after being recycled. The data structure runs on single machine in single thread. The goal is to optimize time and memory. An intuitive solution is to use a set to track recycled ids, and use a counter to track maximum allocated id so far.

Skip List in LevelDB

In earlier post, we presented a skip list implementation in C++. I am going to go thorough a skip list implementation in real world software: leveldb.

Inorder traversal in constant space - Morris algorithm explained

The well known recursive binary tree inorder traversal needs O(H) space where _H_ is the height of the tree.

Beautiful Scheme - Macros

Macros are not covered in SICP. I didn’t know how to use macro in scheme until I read Peter Norvig’s JScheme code. Only then I started to understand why “symbol” and “quote” are important to scheme. Scheme macros is similar to C macro, both transform some pattern into another. Scheme macros are more powerful because expansion/transformation happens at run time, and input/output patterns are structured scheme data that represents scheme code.

Beautiful Scheme - quote

Scheme is a beautiful language. – prof Ben Leong

GCC Allows Arrays of Variable Length!!

This is very surprising. When I was learning C, I was convinced that array size must be determined at compile time, and I never wrote a line of code that violate this. Today, my friend (a C beginner) asked me to help him to debug his code. His code contains following lines:

Javascript tips

I am reading Secrete of Javascript Ninja these days. This book introduced many js tips/patterns, and I wish to summarize what I find useful in this post.

Expressive Javascript

When I was learning Scheme), I was told that Scheme is a expressive language, because it can implement higher order function, closure, and even OOP.