3 ms·
Amortising allocation won't help the article's example, which is insertion at the front, unless you have a quite unorthodox implementation of your array list (e
by barrkel 10y ago
Amortising allocation won't help the article's example, which is insertion at the front, unless you have a quite unorthodox implementation of your array list (e.g. implementing something like a deque using a circular buffer).
The Python growth allocation doesn't look peculiar to me. It's just calculating exponential growth without floating point operations. Whether you over-allocate in 50%, 25%, 12.5%, or whatever proportional increments (all trivial to calculate using bit shifts), they are all enough to make dynamic growth of the array O(n) over time. Any exponential growth will do. If anything, Python's list growth looks to me like it trades off slightly too much time to save space. Actual results will vary depending on realloc implementation etc of course.