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

Neil Girdhar mistersheik at gmail.com
Sun Feb 15 23:19:06 CET 2015


What if we create a view (ChainMap) to be the result of the | operator?  Or 
would that not work?

On Thursday, February 12, 2015 at 12:06:14 PM UTC-5, Steven D'Aprano wrote:
>
> 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 <st... at pearwood.info 
> <javascript:>> 
> > 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 
> _______________________________________________ 
> Python-ideas mailing list 
> Python... at python.org <javascript:> 
> https://mail.python.org/mailman/listinfo/python-ideas 
> Code of Conduct: http://python.org/psf/codeofconduct/ 
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20150215/b7f5f0c6/attachment.html>


More information about the Python-ideas mailing list