Archives

I’ve considered the opposite problem, to address…

Comment on “BList” by Daniel Stutzbach

I've considered the opposite problem, to address the use case where the list is used as a LIFO stack or used exclusively for lookups.

Here is my plan: Start with a flat data structure and keep it flat as long as the only operations are lookups, appends, or deleting the last element. Switch to the B-Tree style structure on the first operation that would have cost O(n). The cost of initially building a list of size n is O(n), so we can amortize the one-time conversion cost as part of the list construction.

Are there common use cases where a list is modified frequently, then becomes fixed and used only for lookups?

The most recent work I did was to try to integrate the BList into the Python interpreter (replacing the regular list), but that effort has stalled. I ran up against some problems that (apparently) require a deep knowledge of the Python interpreter to debug and I didn't have the time to pursue it.

Share

Comments are closed.