osdir.com


[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Write this accumuator in a functional style


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.