/Data Structure

Smolderingly Fast B-Trees

- Jamie Brandon tl;dr: “B-trees are typically slower than hashmaps, but I was surprised to find fairly wide variation in people's expectations of how much slower.” Jamie compares the speed of b-trees and hashmaps.

featured in #558

My Favourite Data Structure: The Trie

tl;dr: “The trie is a deeply nested tree. The structure is commonly used for predictive text engines because you can represent all strings as a tree. Then, you can use word probabilities to decide on what word you should recommend. This could be done by using a reference corpus of millions of words from English publications to identify how common different words are.” James illustrates how a trie works. 

featured in #495

My Favourite Data Structure: The Trie

tl;dr: “The trie is a deeply nested tree. The structure is commonly used for predictive text engines because you can represent all strings as a tree. Then, you can use word probabilities to decide on what word you should recommend. This could be done by using a reference corpus of millions of words from English publications to identify how common different words are.” James illustrates how a trie works. 

featured in #494

Text Editor Data Structures: Rethinking Undo

- Cameron DaCamara tl;dr: "Undo and redo have been a staple operation of text editors probably since the first typo was ever made, yet there has not been a lot of innovation around refining the idea of what undo and redo could be. Let’s explore what I mean..."

featured in #474

An Interactive Intro To CRDTs

- Jake Lazaroff tl;dr: “CRDT stands for “Conflict-free Replicated Data Type”. That’s a long acronym, but the concept isn’t too complicated. It’s a kind of data structure that can be stored on different computers (peers). Each peer can update its own state instantly, without a network request to check with other peers. Peers may have different states at different points in time, but are guaranteed to eventually converge on a single agreed-upon state. That makes CRDTs great for building rich collaborative apps, like Google Docs and Figma — without requiring a central server to sync changes.”

featured in #454

A Gentle Introduction To CRDTs

tl;dr: A CRDT is a data structure that is replicated across multiple computers in a network, with the following features: (1) The application can update any replica independently, concurrently and without coordinating with other replicas. (2) An algorithm (itself part of the data type) automatically resolves any inconsistencies that might occur. (3) Although replicas may have different state at any particular point in time, they are guaranteed to eventually converge. The article discusses when you need a CRDT, examples of them, pro and cons, and more.

featured in #391

Twintrees, Baxter Permutations, and Floorplans

- Donald Knuth tl;dr: Video of Donald Knuth's annual lecture covering "three fascinating concepts, which seem at first to be entirely unrelated to each other, are in fact in one-to-one correspondence, via three beautiful algorithms."

featured in #377

Challenging Algorithms And Data Structures Every Programmer Should Try

- Austin Henley tl;dr: "Not only have they come up during job interviews, but learning them changed how I think about problems." Austin's explains the following algorithms and data structures: (1) Topological sort. (2) Recursive descent parsing. (3) Myers string difference. (4) Bloom filter. (5) Piece table. (6) Splay tree.

featured in #376

In Defense Of Linked Lists

- Salvatore Sanfilippo tl;dr: "I got the feeling that many people think linked lists are like a joke. A trivial data structure that is only good for coding interviews, otherwise totally useless. In a word: the bubble sort of data structures. I disagree, so I thought of writing this blog post full of all the things I love about linked lists."

featured in #368

B-Trees: More Than I Thought I'd Want To Know

- Ben Congdon tl;dr: Ben's biggest takeaway is that there's "a significant difference between a data structure as an abstract mathematical concept (“a B⁺-Tree”) and concrete implementations (“SQLite’s database format”)." The optimizations to implementations "won’t improve the BigO characteristics of a data structure, but will have significant “real world” implications on performance & usability of a DB."

featured in #247