B
barnesc
Hi again,
Since my linear algebra library appears not to serve any practical
need (I found cgkit, and that works better for me), I've gotten bored
and went back to one of my other projects: reimplementing the Python
builtin classes list(), set(), dict(), and frozenset() with balanced
trees (specifically, counted B-trees stored in memory).
In short, this allows list lookup, insertion, deletion in O(log(N))
time. It allows the set and dictionary types to be maintained in
order, and insert/lookup/remove operations here take O(log(N)) time
as well. Getting the k least or k greatest elements takes
O(log(N)+k) time.
I'm about 50% done with the implementation of this module.
I thought I'd use this for Dijkstra's algorithm and some schedulers,
but then I noticed that a binary heap can be retrofitted to have the
DECREASE-KEY operation (see e.g. David Eppstein's priorityQueue).
Thus my B-tree based classes aren't really necessary, since there are
simpler heap implementations that do the same thing.
So my question is: are there any other *practical* applications of a
B-tree based list/set/dict ? In other words, is this module totally
worth coding, or is it just academic wankery and theoretical flim
flam ?
Thanks for your comments/opinions/etc...
- Connelly Barnes
'Y29ubmVsbHliYXJuZXNAeWFob28uY29t'.decode('base64')
---------------------------------------------------------------------
Detailed overview of the bcollections module (from the docstring)
---------------------------------------------------------------------
"""
....
The bset() and bdict() classes improve upon the builtin set and
dictionary types by maintaining the elements in sorted order.
Generally, the b* classes are a factor of O(log(N)) slower[2] than the
corresponding builtin classes, except for certain operations:
- For a bset(), it takes O(log(N)) time to get the minimum, maximum,
or ith element. Also, it takes O(log(N)+k) time to get the
k first, k last, or any slice of k elements from the sorted set.
- For a bdict(), dictionary keys can be retrieved in sorted order
with the above time bounds.
- For a blist(), items can be inserted and removed in O(log(N)) time.
It takes O(log(N)+k) time to get, set, or delete a slice of k
elements.
....
blist - List implemented via B-tree.
bset - Set implemented via B-tree.
Additional methods:
- s.min() - Minimum element
- s.max() - Maximum element
- s.index(x) - Index of x in sorted list of
elements.
- s.next(x) - Least element which is > x
(x need not be in the set).
- s.previous(x) - Greatest element which is < x
(x need not be in the set).
- s - Get element i from sorted list.
- s[i:j] - Get slice from sorted list.
bfrozenset - Immutable set implemented via B-tree.
bdict - Dict implemented via B-tree.
Additional methods:
- a.min() - Minimum key
- a.max() - Maximum key
- a.index(k) - Index of k in sorted list of
keys.
- s.next(x) - Least key which is > x
(x need not be an existing key).
- s.previous(x) - Greatest key which is < x
(x need not be an existing key).
- a.get_key_at(i) - Get key at index i from sorted
list of keys.
- a.get_key_at(i, j) - Get slice from sorted key list.
"""
Since my linear algebra library appears not to serve any practical
need (I found cgkit, and that works better for me), I've gotten bored
and went back to one of my other projects: reimplementing the Python
builtin classes list(), set(), dict(), and frozenset() with balanced
trees (specifically, counted B-trees stored in memory).
In short, this allows list lookup, insertion, deletion in O(log(N))
time. It allows the set and dictionary types to be maintained in
order, and insert/lookup/remove operations here take O(log(N)) time
as well. Getting the k least or k greatest elements takes
O(log(N)+k) time.
I'm about 50% done with the implementation of this module.
I thought I'd use this for Dijkstra's algorithm and some schedulers,
but then I noticed that a binary heap can be retrofitted to have the
DECREASE-KEY operation (see e.g. David Eppstein's priorityQueue).
Thus my B-tree based classes aren't really necessary, since there are
simpler heap implementations that do the same thing.
So my question is: are there any other *practical* applications of a
B-tree based list/set/dict ? In other words, is this module totally
worth coding, or is it just academic wankery and theoretical flim
flam ?
Thanks for your comments/opinions/etc...
- Connelly Barnes
'Y29ubmVsbHliYXJuZXNAeWFob28uY29t'.decode('base64')
---------------------------------------------------------------------
Detailed overview of the bcollections module (from the docstring)
---------------------------------------------------------------------
"""
....
The bset() and bdict() classes improve upon the builtin set and
dictionary types by maintaining the elements in sorted order.
Generally, the b* classes are a factor of O(log(N)) slower[2] than the
corresponding builtin classes, except for certain operations:
- For a bset(), it takes O(log(N)) time to get the minimum, maximum,
or ith element. Also, it takes O(log(N)+k) time to get the
k first, k last, or any slice of k elements from the sorted set.
- For a bdict(), dictionary keys can be retrieved in sorted order
with the above time bounds.
- For a blist(), items can be inserted and removed in O(log(N)) time.
It takes O(log(N)+k) time to get, set, or delete a slice of k
elements.
....
blist - List implemented via B-tree.
bset - Set implemented via B-tree.
Additional methods:
- s.min() - Minimum element
- s.max() - Maximum element
- s.index(x) - Index of x in sorted list of
elements.
- s.next(x) - Least element which is > x
(x need not be in the set).
- s.previous(x) - Greatest element which is < x
(x need not be in the set).
- s - Get element i from sorted list.
- s[i:j] - Get slice from sorted list.
bfrozenset - Immutable set implemented via B-tree.
bdict - Dict implemented via B-tree.
Additional methods:
- a.min() - Minimum key
- a.max() - Maximum key
- a.index(k) - Index of k in sorted list of
keys.
- s.next(x) - Least key which is > x
(x need not be an existing key).
- s.previous(x) - Greatest key which is < x
(x need not be an existing key).
- a.get_key_at(i) - Get key at index i from sorted
list of keys.
- a.get_key_at(i, j) - Get slice from sorted key list.
"""