26 items | 3 visits
pascal dupond's List: algo
-
-
CouchDB is not the first implementation of an append-only B-Tree, but it may be unique that it has the ability to interleave multiple indexes on disk in an append-only way. This interleaving is what gives it the ability to update the by-sequence and by-id indexes together atomically, without transactions.
The overall effect of this design is to maximize for reliability and concurrency. There is no way to corrupt the data, as we never touch what we've already written to disk.
-
-
-
The usual linked list operations (inserting a subsection, deleting a subsection, and so on) still complete in constant time.
The new operation, of reversing a list or a list segment, also completes in constant time.
-
Here's a link to Osterman and Rego's paper.
-
-
-
- Cumulative frequency tables
- A quick (log-time) mechanism for maintaining a cumulative frequency table. Useful in adaptive compression methods (particularly arithmetic compression). Might also have applications in assembly or code generation.
- A block-sorting approach to string searching
- A method of searching one string for another, inspired by the Burrows-Wheeler transform. Unlike most searching algorithms, which are optimised to search for one needle in a large amount of haystack text, this algorithm is optimised to take one fixed haystack and search it very fast for lots of different needles.
- Sorting a linked list using Mergesort
- All the serious computer-science literature about sorting tells you how to do it on arrays. As it turns out, sorting a linked list is much easier, but nobody actually bothers to tell you about it. Well, I do, and here's how you can use a variant of Mergesort to sort a linked list in reliable
O(N log N)time, with no worst cases, no auxiliary storage requirements, and stably.- Counted B-trees
- An enhancement to the well known B-tree algorithms to allow you to look up items in the tree by numeric index, or to find the numeric index of an item. Useful for finding percentiles, for deciding on a strategy for a complex search operation, or for storing items in a B-tree in arbitrary order without a sorting criterion.
- Reversible linked lists
- A modified form of doubly linked list, which allows an arbitrary section of a list to be reversed in constant time, simply by changing a few pointers around, like any list splice operation. Completely useless as far as I know, but very cute.
-
-
-
Comparing floating point numbers
-
-
-
Stop using unsafe keyed hashes, use HMAC
-
-
-
-
-
When predicting the outcome of chess games, you typically need two things; a rating system wherein the current ability of each player is estimated based on past results, and a model for estimating the expected score for each player, once you know their ratings.
-
Here are some links to articles existing on rating systems:
Elo and Ken Thompson
Glicko
Chessmetrics
Microsoft TrueSkill
-
-
-
-
-
List Comments
(0)
List Info