[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