[Python-checkins] r75714 - python/trunk/Python/bltinmodule.c

[Nick Coghlan]

mark.dickinson wrote:
> Modified: python/trunk/Python/bltinmodule.c
> ==============================================================================
> --- python/trunk/Python/bltinmodule.c	(original)
> +++ python/trunk/Python/bltinmodule.c	Mon Oct 26 15:18:44 2009
> @@ -2350,6 +2350,15 @@
>  			}
>  			break;
>  		}
> +		/* It's tempting to use PyNumber_InPlaceAdd instead of
> +		   PyNumber_Add here, to avoid quadratic running time
> +		   when doing 'sum(list_of_lists, [])'.  However, this
> +		   would produce a change in behaviour: a snippet like
> +
> +		     empty = []
> +		     sum([[x] for x in range(10)], empty)
> +
> +		   would change the value of empty. */
>  		temp = PyNumber_Add(result, item);
>  		Py_DECREF(result);
>  		Py_DECREF(item);

Could you get the best of both worlds by switching to in-place add only
after the first pass through the addition loop?

Then [0]+empty would create a new list that is private to the sum()
call, with further results accumulated in that new object to avoid the
quadratic behavour.

There may be other corner cases that would make even that a bad idea,
but it would at least avoid the issue mentioned in the new comment.

Cheers,
Nick.

-- 
Nick Coghlan   |   ncoghlan at gmail.com   |   Brisbane, Australia
---------------------------------------------------------------