Write this accumuator in a functional style

[Pavol Lisy]

On 7/13/17, Steve D'Aprano <steve+python at pearwood.info> wrote:
> On Fri, 14 Jul 2017 12:59 am, 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.
>
> If your list is so huge that a factor of two makes a difference, then you
> should
> be using a different data structure. Something that doesn't live in memory
> all
> at once. And by huge, I mean hundreds of millions or billions of items.
>
> But under normal circumstances, a factor of two is nothing.
>
> (Unless you're working on an embedded device, where memory is really
> constrained. But then you shouldn't be using CPython. Try MicroPython.)
>
> It's not 1970 where 64K is more memory than anyone can imagine using and we
> have
> to count every byte of memory. Its 2017 and memory is cheap, we can afford
> to
> use some memory to speed up our algorithms.

Maybe I don't remember it well but we have thread on python-list (or
python-ideas) where somebody had problem with memory after update to
python3.5 which  was following with this issue ->
https://bugs.python.org/issue29949

He has enough memory (maybe 64GB or 128GB? my brain memory has limits
too) but his models was very slow after upgrade python. (due to
swapping)

>> Or waste big memory for huge frozensets. I mean resize it to 2*N if
>> its size is just N+1.
>
> Frozensets aren't mutable, so they never resize.

Yes so it seems to be easy to allocate just precisely amount of memory.

But they are created by using same quadrupling/doubling machinery as
you can see:

   from sys import getsizeof
   print( [getsizeof(frozenset(range(n))) for n in range(20)] )
[224, 224, 224, 224, 224, 736, 736, 736, 736, 736, 736, 736, 736, 736,
736, 736, 736, 736, 736, 736]

I was thinking that this could be good starting point to try to make
some patch.

Is there any tutorial for dummy beginner how to start to be good at
cpython patchwork? :)