
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...@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...@python.org <javascript:> https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/