Write this accumuator in a functional style

[Steve D'Aprano]

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.


> 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.



-- 
Steve
“Cheer up,” they said, “things could be worse.” So I cheered up, and sure
enough, things got worse.