I think there’s one in your example.…

Comment on “BList” by bramcohen

I think there's one in your example. If you say x = [1, 2, 3, 4] * (2 ** 24) then it will have O(log(n)) lookup time. If you then proceed to use the resulting list with lots of lookups and modifies but no inserts and deletes, then if you do enough manipulation it will be much slower than if it had simply made a list up front. That problem could be fixed with amortized flattening. The flattening would make the data structure non-sparse in this example though. Whether this issue is worth the extra work is unclear, but that which is worth doing is worth doing to excess.

You should also probably modify insort so that it uses the b-tree structure to still run in log(n) instead of log(n) ** 2, which it will do if it has to treat the underlying blist as a black box.


Comments are closed.