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[i] - 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. """ -- http://mail.python.org/mailman/listinfo/python-list