Stephen Diehl's summary of the most influential advancements on top of the Attention Mechanism. The article comes with detailed descriptions and from-scratch codes demonstrating how exactly these techniques work.

Reservoir sampling is a technique for selecting a fair random sample when you don't know the size of the set you're sampling from.

An algorithm like this is applicable in cases like rate limiting sending a fixed number of logs per time interval to protect against bursting. A naive greedy approach will result in biases. We want to evenly sample the logs.

The trick is to use a fixed K slots of log entries (K corresponds to the per-bucket rate limit). For upcoming entries, first fill the slots (N<=K), for an upcoming entry after N>K, we decide to replace a slot with the new entry at the probability of K/N. The evicted slot is chosen randomly from the K slots. In the end of the time interval, flush the slots.

An encyclopedia of consistency models for concurrent systems.

The algorithm for de-pixelating a pixelated moving window with fixed content:

1. extract the frames and find the absolute positions of the window for each frame
2. assume the color of each pixelated cell is the color for the center pixel of each cell (think of pixelation as a magnifier filter focusing on the center pixel for each cell)
3. by tracking the locations of the centered pixels and its colors in each frame, we fill in more and more pixels with known colors.
4. for the remaining unfillled pixels, interpolate from nearest pixel of known colors (e.g. voronoi)

TIL succinct data structures - data stored in a compact fashion as in a compression, but the compact form itself has useful properties.

The Rank/Select Bit Vector is a bit vector equipped with two fast operations - rank and select. The rank operator returns the number of set bits up to the n-th bit. The select operator returns the index of the n-th set bit, i.e. inverse of rank. The data structure has nice uses as in string lookup, etc.

The Wavelet Matrix is a generalization of rank/select bit vector on non-binary symbols. Another data structure of the class is the FM-index, whose operators extend to working on patterns (substrings) instead of symbols.

How can a calculator program perform an exact calculation involving arithmetic operations, roots, trigonometric functions, etc? It's a difficult task. Here is how it can be done.

• rational type: bignum for both nom and denom
• recursive real arithmetic (RRA):
  • represent a real number as a computation that maps from a precision value (a rational) to the rational result etc.
  • for composite expression, compute the precision value needed for each of its components (e.g. for 2pi to be shown with a precision of 0.01, pi needs to be calculated to 0.005 precision)
• determine the exact equality between RRA
  • undecidable but decidable for a finite set of ops (proven by Dan Richardson, 1994), but slow
• the optimization
  • represent every number as an exact rational times a RRA. (e.g. (3/2)pi)
  • hard code the common types of RRA (sin, log, ..) whose identity can be checked directly.
  • for uncommon types of RRA, just store RRA (e.g. pi * sqrt(2))

the result: the digits shown on screen are always 100% correct. 99% of calculation gets perfect UX.

TIL VoxelSpace, a simple algorithm for rendering terrain map in high detail. The terrain is described by two identical sized textures: the height map and the color map. The color map is preshaded to contain shadows/other features. The rendering is performed from back to front at the viewer's perspective (painter's algorithm). For each depth, calculate a line corresponding to the given depth, use the line to sample textures on the height map and the color map. For each rasterized point of such line, render a vertical line into the view port from the given height to 0 with the given color. Repeat this process until the depth reaches the near z-plane. The algorithm can be optimized by drawing from front to back to avoid drawing unnecessary vertical line segments at the cost of an extra z-buffer.

The naive collision detection algorithm takes O(n^2) by checking pairwise intersection. To improve the performance, sort the objects by x coordinates, scan from left to right and only check intersection if a.right < b.left. This method can be extended into 2D to further eliminate the necessary comparisons. Finally, note that insertion sort is more performant on mostly sorted lists than quick sorts, so it's more suitable in this case.

An interactive introduction to four-color problem and zero-knowledge proof.

Pratt parsing is a parsing algorithm that solves the awkward handling of left-recursion in a recursive descent parser. It elegantly handles both operator precedence and associativity using a single "binding power" concept. The core algorithm is as simple as follows:

fn expr(input: &str) -> S {
    let mut lexer = Lexer::new(input);
    expr_bp(&mut lexer, 0) 
}

fn expr_bp(lexer: &mut Lexer, min_bp: u8) -> S { 
    let mut lhs = match lexer.next() {
        Token::Atom(it) => S::Atom(it),
        t => panic!("bad token: {:?}", t),
    };

    loop {
        let op = match lexer.peek() {
            Token::Eof => break,
            Token::Op(op) => op,
            t => panic!("bad token: {:?}", t),
        };

        let (l_bp, r_bp) = infix_binding_power(op);
        if l_bp < min_bp { 
            break;
        }

        lexer.next(); 
        let rhs = expr_bp(lexer, r_bp);

        lhs = S::Cons(op, vec![lhs, rhs]); 
    }

    lhs
}

fn infix_binding_power(op: char) -> (u8, u8) {
    match op {
        '+' | '-' => (1, 2),
        '*' | '/' => (3, 4),
        _ => panic!("bad op: {:?}"),
    }
}

An interger hash function is a bijection in the domain of N-bit unsigned integers with hashing properties. To make a good hash function, for each flip in input bit, roughly 1/2 of the output bit should flip (known as "high avalanche effect"). Furthermore, there should be no correlation between flipped input bits and output bits (known as "low bias"). The author of this article describes an algorithm to generate integer hash functions by composing reversible functions, and test the two hashing properties on the function to find the best ones.

TIL A* with fixed iteration depth.

This article talked about three data structures for efficient text editing (a.k.a. text buffer data structure): Rope, Gap Buffer, and Piece Table. It's first time I learned about Piece Table, it works like this:

• Store the text in an append-only fashion in two buffers known as original file and add file
• Store the information about segments of the files as a list of reference to the slices into the two buffers (known as "piece table")

The inserting/deleting in this data structure would simply need to breaking up items in the piece table. It seems like a good candidate as a basis to implement CRDT in a collaborative editor.

From my preliminary understanding of the nature of this data structure, it doesn't seem necessary to have two buffers, a single append-only buffer preloaded with the file should be sufficient.

UPDATE: I found this post on vscode blog extremely helpful: https://code.visualstudio.com/blogs/2018/03/23/text-buffer-reimplementation

The author wrote a program that solves Mario levels by exploring the state space with a path-finding algorithm with a guiding heuristic. This is a nice demo of how you sometimes don't need sophisticated algorithm or machine learning to tackle complex problems.

Oxford's publications on algorithms, functional programming, and category theories. I peeked through a few articles. From those I learned novel ideas and enjoyed them.

An article on dithering techniques.

An interesting approach towards procedurely generated level/room/dungeon: specify various constraints and use a solver to place the objects on the tiles.

This is a not-so-short article teeming with "Aha!" moments.

1. reduce all branching in the solution to a math expression
2. converted to a lookup algorithm
3. we need a perfect hash function
4. use multiplication + shr as bit mixer
5. store answers directly in a single u32 integer
6. cram the answers even tighter with overlaps

The post shows off lot of tricks, very interesting read.

A collection of seemingly interesting data structure and algorithms.

A document by OpenAI on Deep Deterministic Policy Gradient (DDPG), a Q-learning like algorithm that works for continuous action space.