Now on ScienceBlogs: And so, driven on ceaselessly toward new shores
Finding the fun in good math; Shredding bad math and squashing the crackpots who espouse it.
Mark Chu-Carroll (aka MarkCC) is a PhD Computer Scientist, who works for Google as a Software Engineer. My professional interests center on programming languages and tools, and how to improve the languages and tools that are used for building complex software systems.
Category: Data Structures
As an alert commenter pointed out, I left out one really important thing in my earlier post about finger trees. That's what I get for trying to write when I'm sick :-). Seriously, this is a point that's implied...
Posted by Mark C. Chu-Carroll at 10:28 AM • 10 Comments •
Category: Data Structures
For ages, I've been promising to write about finger trees. Finger trees are an incredibly elegant and simple structure for implementing sequence-based data structures. They're primarily used in functional languages, but there's nothing stopping an imperative-language programmer from using...
Posted by Mark C. Chu-Carroll at 4:36 PM • 16 Comments •
Category: Data Structures
This post is very delayed, but things have been busy. I'm working my way up to finger trees, which are a wonderful functional data structure. They're based on trees - and like many tree-based structures, their performance relies heavily...
Posted by Mark C. Chu-Carroll at 9:55 AM • 5 Comments •
Category: Data Structures
Last week, I promised to continue my discussion of ropes. I'm going to break that promise. But it's in a good cause. If you're a decent engineer, one of the basic principles you should follow is keeping this as...
Posted by Mark C. Chu-Carroll at 9:03 PM • 24 Comments •
Category: Data Structures
It's been a while since I've written about any data structures. But it just so happens that I'm actually really working on implementing a really interesting and broadly useful data structure now, called a Rope. A bit of background,...
Posted by Mark C. Chu-Carroll at 10:14 PM • 11 Comments •
Category: Data Structures
Another cool, but frequently overlooked, data structure in the tree family is called the B-tree. A B-tree is a search tree, very similar to a BST in concept, but optimized differently. BSTs provide logarithmic time operations, where the performance...
Posted by Mark C. Chu-Carroll at 5:53 PM • 10 Comments •
Category: Data Structures
Last post, I described the basic idea of the binary heap data structure. But I didn't talk about how to implement it - and there's a very cool way of implementing it - optimally space efficient, very fast, and...
Posted by Mark C. Chu-Carroll at 10:49 AM • 24 Comments •
Category: Data Structures
One of the most neglected data structures in the CS repertoire is the heap. Unfortunately, the jargon is overloaded, so "heap" can mean two different things - but there is a connection, which I'll explain in a little while....
Posted by Mark C. Chu-Carroll at 11:37 AM • 34 Comments •
