Concatenative topics
Concatenative meta
Other languages
Meta
Let's consider these conceputal data structures:
Nothing out of the ordinary, right ?
An indexable deque which is optimal in space and time [3].
This is simply a O(sqrtN) array of O(sqrtN) sub-arrays.
Two lists of arrays are maintained, small and big (twice bigger)
Also, pointers to head/tail indexes, and the big/small separation are maintained.
Conceptually, the virtual array is the concatenation of all small sub-arrays followed by the big sub-arrays, and indexed between head/tail.
All operations are straightforward. In order to maintain the global invariants, small sub-arrays are sometimes merged into big arrays, or big arrays are split into small arrays (this happens at the boundary between the two lists). when one of both lists is empty, lists are swapped (big arrays become small and vice-versa)
Asymptotic complexity:
This is implemented by growing the integer range of sub-arrays dynamically when an update overflows. It makes updates O(sqrtN) worst case (O(1) amortized if O(N) numbers take O(lgM) bits).
Asymptotic complexity:
Monolithic lists are lists stored without any managed pointers, in a flat array. Each node in the list is identified by a number in [1..N]. 0 is the head and -1 the tail. Insertion allocates nodes, removal reclaims them. Because the links are xor-coded, two consecutive nodes are needed to form a cursor. given a cursor, you can query the list for the next or previous element. To store values at each node, you can simply use node identifiers to index a [1..N] array. This makes cache behavior even worse, but it doesn't matter much, as indexing lists is slow anyway.
note: unrolled lists are isomorphic to lists of arrays. they offer no improvement.
Asymptotic complexity:
A succinct data structure has space usage close to the information theoretic lower bound.
In essence, a list is isomorphic to an Hamiltonian cycle in a complete graph of n nodes. There are O(N!) such cycles.
Thus at least lg(N!) + o(N) bits are needed to encode a list. This gives us NlgN + o(N) as a lower bound.
Succinct lists achieve this lower bound (tightly) and can still operate efficiently. To achieve this, succinct lists are simply monolithic lists stored in the previously defined compact integer arrays.
Asymptotic complexity:
Split hashtables are a variation of cuckoo hashing that doesn't move anything around.
In essence, this structure is a pair of arrays of lists of key/value pairs. Lookup is done by splitting the hash of the key in two, using this pair to index the arrays, and then search each list for the key. The twist is that insertion is always in the shortest list. Surprisingly, that gives us an information-theoretic advantage that reduces the expected worst case list length significantly [4]. This works so well that it's a waste of time to make any effort to move elements around (as in cuckoo hashing). Also, the structure can achieve near 100% load efficiently.
Of course, to get the good performance, some tweaks can make the difference.
For space usage: If possible, lists are inlined in the tables. (there are two words to accomodate for a key/value pair per position). When needed full lists are stored as arrays. Full lists have very low expectation, so they are not important. The effort to recover inlined lists is to scan a single cache line in each table.
For speed: The most critical operation for an unordered set is to answer queries. This is divided into three stages in split hashtables:
Insertions and removal are performed with a variant of query that returns the key/value pair by reference.
Allocation has many possibilities: allocating full lists, growing tables, or even swapping values around (like cuckoo hashing) to achieve better results.
A load of 50% gives expected performance similar to cuckoo hashes, as the short inline path will miss with very low probability. Very high loads (near 100%) can be achieved as the saturation of inlined lists has very low probability (on the order of 1% for millions of elements, grows in lglgN).
Asymptotic complexity:
hit rate for the fast pathB+ trees (hereinafter called btrees) are boring. In essence, a btree is a tree where each node contains a perfectly balanced implicit binary tree along with pointers to the child nodes. All the nodes but the root are balanced (they have between B and 2B elements) and the leaf nodes contain the records (for us, key/value pairs).
The large size of the nodes make them very cache efficient. Also, it's very easy to navigate an implicit binary tree (childs = position2 + 0 or 1) so search is very fast. One weakness is the cost of insertion/removal in a node. rotated lists can bring that cost down, especially for the key exchanges needed to balance.
Balance is maintained by exchanging elements with neighbours. if consecutive nodes are at the threshold, then nodes are split (2 nodes into 3) or merged (3 nodes into 2). The cost of a parent pointers at each node is very low, and allows finger operations along with simplified maintainance. Space usage is at least between 50-100% load, but constant time on updates can be traded for higher compacity (using leaves of variable sizes).
Asymptotic complexity:
A packed memory array (hereinafter called PMA) is a an array of records stored in order, with some gaps to allow for efficient updates. The array is cut in lgN chunks, and an implicit binary tree keeps track of the number of elements for each 2klgN region. To enforce balance, regions have density thresholds, which are tighter for larger regions. After updates, if the density of any region is out of bounds, all elements in the region are redistributed uniformly. The adaptive PMA improves upon pmas by redistributing unevenly in order to achieve lgN updates for many common update patterns (like bulk insertions). PMAs are especially attractive for external storage (like disks) as they have great locality (all elements are in order) and do not age (locality isn't degraded by updates). This is why PMAs are often a building block for cache oblivious data structures. For instance, using an implicit binary tree with a van Emde Boas layout to index a PMA gives a 'cache oblivious B+ tree'. Note that the log2(N) amortized cost can be reduced to lgN using an indirection with lgN sub-blocks.
Asymptotic complexity:
Search in the comparison model is optimal in lgN. However, for an indexable, finite universe, van Emde Boas trees can beat that bound, bringing it to lglgN.
The way to achieve that is very simple. The universe (the set of all possible elements) has size U. Consider an implicit radix tree over U. Every node which has only one child stores the biggest/smallest value of it's child (the one that's closest from the set spanned by missing child), other nodes or marked full/empty. All values are also stored in a doubly linked list.
It's possible to access any node in the tree in constant time, and given a value, the path from it's leaf to the root is known. With a binary search on that path it's possible to find the deepest node with only one child on the path. This node gives the predecessor/successor of the value searched for (depending if the value is under the right or left child), and the list can then be queried to find the successor/predecessor.
The tree has depth lgU, so a binary search over a path costs lglgU, and updates cost lgU. However, using a binary search with a fixed pattern, and because search can terminate as soon as a node with only one child is found, there is not need to access or update the whole path, but only the steps accessed be the search. This way only lglgN operations are needed for queries and updates.
Asymptotic complexity:
y-fast trees are simply sparse van Emde Boas trees. As is, the space usage is impractical. Using a hashtable to store the implicit tree, we can get the space usage down to O(N), in exchange for randomization.
Asymptotic complexity:
Given a set U that can be partitionned into a finite amount of [a, (1+e)a) intervals, we can store these intervals in an ordered multiset over finite keys. Thus we get an e-approximate ordered map, where all operations take constant time O(ln(ln2(max(U)-min(U))). This can be used to sort sets with a minimum relative difference between elements in linear time, to compute e-approximate minimum spanning trees in linear time, etc...
Asymptotic complexity:
[ basic red-black trees with full persistence in O(1) space per update ]
[1] J. R. Driscoll, N. Sarnak, D. D. Sleator, R. E. Tarjan. Making data structures persistent. Journal of Computer and System Sciences. Volume 38, Issue 1, February 1989.
http://www.cs.cmu.edu/~sleator/papers/making-data-structures-persistent.pdf
[2] P. F. Dietz. Fully Persistent Arrays (Extended Array). Lecture Notes in Computer Science, Volume 382, 1989
https://gummo.lib.rochester.edu/retrieve/14496/tr%23290.pdf
[3] A. Brodnik, S. Carlsson, E. D. Demaine, J. I. Munro, and R. Sedgewick. Resizable arrays in optimal time and space. Technical Report CS-99-09, U. Waterloo, 1999.
http://www.cs.uwaterloo.ca/~imunro/resize.ps
[4] M. Mitzenmacher. The power of two choices in randomized load balancing. Parallel and Distributed Systems, IEEE Transactions on. Volume 12, Issue 10, Oct 2001
http://www.eecs.harvard.edu/~michaelm/postscripts/mythesis.pdf
This revision created on Thu, 11 Dec 2008 09:05:18 by prunedtree