[Python-ideas] Adding "+" and "+=" operators to dict

[Steven D'Aprano]

On Thu, Feb 12, 2015 at 09:02:04AM -0430, Juancarlo Añez wrote:
> On Thu, Feb 12, 2015 at 6:13 AM, Steven D'Aprano <steve at pearwood.info>
> wrote:
> 
> > I certainly wouldn't want to write
> >
> >     new_dict = a + b + c + d
> >
> > and have O(N**2) performance when I can do this instead
> >
> 
> It would likely not be O(N), but O(N**2) seems exaggerated.

If you want to be pedantic, it's not exactly quadratic behaviour. But 
it would be about the same as as list and tuple repeated addition, 
which is also not exactly quadratic behaviour, but we often describe 
it as such. Repeated list addition is *much* slower than O(N):

py> from timeit import Timer
py> t = Timer("sum(([1] for i in range(100)), [])")  # add 100 lists
py> min(t.repeat(number=100))
0.010571401566267014
py> t = Timer("sum(([1] for i in range(1000)), [])")  # 10 times more
py> min(t.repeat(number=100))
0.4032209049910307


So increasing the number of lists being added by a factor of 10 leads to 
a factor of 40 increase in time taken. Increase it by a factor of 10 
again:

py> t = Timer("sum(([1] for i in range(10000)), [])")  # 10 times more
py> min(t.repeat(number=100)) # note the smaller number of trials
34.258460350334644

and we now have the time goes up by a factor not of 10, not of 40, but 
about 85. So the slowdown is getting worse. It's technically not as bad 
as quadratic behaviour, but its bad enough to justify the term.

Will repeated dict addition be like this? Since dicts are mutable, we 
can't use the string concatenation trick to optimize each operation, so 
I expect so: + will have to copy each of its arguments into a new dict, 
then the next + will copy its arguments into a new dict, and so on. 
Exactly what happens with list.

-- 
Steve