Write this accumuator in a functional style
Ned Batchelder
ned at nedbatchelder.com
Thu Jul 13 19:06:06 EDT 2017
On Thursday, July 13, 2017 at 10:59:52 AM UTC-4, Pavol Lisy wrote:
> On 7/13/17, Steve D'Aprano <steve+python at pearwood.info> wrote:
>
> > [1] Actually, CPython's lists initially quadruple the size of the array, up
> > to a
> > certain point, and then switch to doubling. This ensures that small lists
> > have
> > even fewer expensive resizes, at the cost of wasting a bit more memory, but
> > its
> > only a small array so who cares?
>
> IMHO problem is doubling size for huge lists.
>
> Or waste big memory for huge frozensets. I mean resize it to 2*N if
> its size is just N+1.
Steve's summary is qualitatively right, but a little off on the quantitative
details. Lists don't resize to 2*N, they resize to ~1.125*N:
new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);
(https://github.com/python/cpython/blob/master/Objects/listobject.c#L49-L58)
--Ned.
More information about the Python-list
mailing list