zip() function troubles

Paul Rubin http
Tue Jul 31 21:57:13 CEST 2007

"Chris Mellon" <arkanes at> writes:
> Better hand in your computer, then. You're never going to find a
> situation where the environment won't affect the running time of your
> algorithms.

The environment may affect the running time by an additive or linear
multiplicative constant but it should never turn an O(n) algorithm
into an O(n**2) one.

> For the record, the python GC is generational. This is a case of a
> default heuristic giving pathological behavior in a corner case, not
> anything broken about the design of the python GC.

No, it is broken, per discussion on a
comp.compilers/comp.lang.functional thread this week.  The notion of
using a generational collector was to collect less and less frequently
for older and older generations (e.g. doubling the amount of
allocation between generations) but the usual solution is apparently
to increase the heap size by some multiplicative factor when GC fails
to free enough memory.  

More information about the Python-list mailing list