How a Python list grows
A list in CPython keeps references to its elements in an array with spare room. While there is room, append simply writes to the next cell. When the list is full and one more element is added, CPython allocates a new array. If the list will hold s elements (that is, s is the size including the one being added), the new capacity is the number s + ⌊s/8⌋ + 6 rounded down to a multiple of four:
In code it is one line: (s + (s >> 3) + 6) & ~3. An empty list has capacity 0, so the very first append allocates 4 cells, and after that the capacities go 8, 16, 24, 32, 40, 52, 64, 76…
Assume that at every allocation all elements already in the list are copied into the new array. For each n, answer: what will the capacity be after n calls of append to an empty list, how many times was memory allocated along the way (the first allocation counts too), and how many elements were copied in total.
This is the real rule of Python 3.13: the test generator checks it against sys.getsizeof on lists of up to a hundred thousand elements.
Input
The first line holds the number of queries q (1 ≤ q ≤ 100,000). The second holds q numbers n (1 ≤ n ≤ 10¹⁸).
Output
For each query, a line of three numbers: the capacity, the number of allocations, the number of copied elements. All answers fit in a signed 64-bit integer.
Examples
Example 1
5 1 4 5 9 17
4 1 0 4 1 0 8 2 4 16 3 12 24 4 28
Example 2
3 1000 1000000 1000000000000000000
1100 28 7556 1056084 86 8445096 1108046317219334708 321 8864370537754664216
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 7 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
A direct simulation, one append at a time up to n, will never finish at n = 10¹⁸. But nothing interesting happens between allocations: the size just grows by one. Can you jump from one allocation straight to the next?
2Hint 2
The capacity grows by a factor of about 1.125. How many allocations does it take to reach 10¹⁸? And does the sequence of capacities depend on the n in the query?
3The idea
There is one sequence of capacities for all queries: 0, 4, 8, 16, 24, 32… Each next one comes from the previous c by putting s = c + 1 into the formula: an allocation happens exactly when one more element is added to a full list. It grows geometrically, and up to 10¹⁸ it has only 322 terms. Compute them once together with the accumulated number of copies, and for each query find by binary search the first capacity that holds n.
4Walkthrough
The array caps: caps[0] = 0, caps[k+1] = (s + (s >> 3) + 6) & ~3 with s = caps[k] + 1. The array copies: copies[k+1] = copies[k] + caps[k], since at the (k+1)-th allocation the list was full and moved all its caps[k] elements (zero at the first allocation). For a query n the index k of the first capacity not less than n is also the number of allocations, and the answer is caps[k] k copies[k].
A sanity check: a million appends give 86 allocations and 8,445,096 copies, about 8.4 per element. The theorem from the article predicts this: with a factor r there are fewer than r/(r − 1) copies per element, and Python's r ≈ 1.125 gives a limit of 9.
Why not multiply by 1.125 in floating point: the formula with >> 3 is integer, and a double keeps only 53 bits of mantissa. While the capacity is below 2⁵³ ≈ 9·10¹⁵, s * 1.125 + 6 is computed exactly, but beyond that the low digits are lost and the capacities drift away from the real ones. The second sample catches this.
4+Solution
5Complexity
The precomputation is O(log1.125 N), about 322 steps. Each query is a binary search over them: O(q · log 322).
6Common mistakes
- Simulating one append at a time. Correct, but 10¹⁸ steps take years.
- The factor 1.125 in floating point. Correct up to 2⁵³ and wrong after.
- Forgetting the rounding to a multiple of 4 or the added 6. The sequence goes astray from the first steps: without the rounding you get 7, 15, 24, 34 instead of 4, 8, 16, 24.
- Not counting the first allocation. Going from an empty list to four cells is also a memory allocation, even though there is nothing to copy yet.