[Guido] >> My own ideal solution would be a subtle hack to the list >> implementation to make pop(0) and insert(0, x) go a lot faster -- >> this can be done by adding one or two extra fields to the list head >> and allowing empty space at the front of the list as well as at the >> end. [Josiah Carlson] > I'm sure you know this, but just for sake of argument, how many extra > fields? A couple? A few? 20? 30? As Guido said, "one or two" would be enough. I think you're talking about different things, though: Guido is talking about the number of new named struct members that would have to be added to Python's list object header. I think you're talking about how many array slots to leave unused on both ends. Just as now, on a reallocation the number of free slots asked for has to be proportional to the total number of slots, so that growth via a huge number of one-at-a-time appends takes (amortized) constant-time per append. Picking any fixed number of free slots leads to overall quadratic-time (in the number of appends) behavior.
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4