Most efficient way to "pre-grow" a list?

[sturlamolden]

On 7 Nov, 03:46, gil_johnson <gil_john... at earthlink.net> wrote:>

> I don't have the code with me, but for huge arrays, I have used
> something like:
>
> >>> arr[0] = initializer
> >>> for i in range N:
> >>>      arr.extend(arr)
>
> This doubles the array every time through the loop, and you can add
> the powers of 2 to get the desired result.
> Gil

You should really use append instead of extend. The above code is O
(N**2), with append it becomes O(N) on average.