The difference between a=a+b and a+=b in Python
pub.towardsai.net
pub.towardsai.net
"For lists, += and *= do the operation in place, whereas a=a+b will create a new object and then copy. The former is marginally faster."
As seen from the below example, += is
marginally faster than the + operator.
This needs 34s on my laptop:
l1 = [1]
l2 = [2]
for i in range(int(10e4)): l1 = l1 + l2
l1 = [1]
l2 = [2]
for i in range(int(10e4)): l1 += l2That means that your first snippet is O(n^2) while your second snippet is O(n).
It's not about doing many operations, it's about the size of l1. In-place append doesn't care, copying into a new object does.
for i in xrange(big):
l1 = [i]
l1 += l2
for i in xrange(big):
l1 = [i]
l1 = l1 + l2(Edit) leaving the comment for integrity of the thread but I failed to notice that you absolutely revisit the first elements of the first array every time through the loop (which is growing in size), which absolutely makes it n^2 whereas the better version just tacks it on without reconstruction.
n^2 is the next best thing to log(n)! It doesn't come close to being exponential.
The arithmetic gets slightly obscured in this example because both lists have length 1 to start with. Let’s instead call the initial list lengths L₁ and L₂.
On the first iteration of the loop, we need to copy L₁ + L₂ elements to build the concatenated list.
However, on the second iteration, the length of l1 is now L₁ + L₂, so we need to copy (L₁ + L₂) + L₂ = L₁ + 2L₂ elements.
On subsequent iterations, we then need to copy L₁ + 3L₂ elements, then L₁ + 4L₂, etc.
If we are running the loop N times (in this example, N = 10⁵) then we end up copying the original elements from l1 N times, but the original elements from l2 get copied 1 + 2 + … + N = N(N+1)/2 times.
So the total number of element copies made during the entire run of the loop is NL₁ + ((N²+N)/2)L₂. With big-O, we need the term that grows fastest and conventionally we write it ignoring any constant scale factors. In this case, that term is the N² because everything else only grows as fast as N, so we say the algorithm is O(N²).
As an aside, for the same conventional reason, we would normally say the second version is O(N). It’s not technically incorrect to say it’s O(2N) according to the definition of big-O, but it’s not idiomatic.
> As an aside, for the same conventional reason, we would normally say the second version is O(N). It’s not technically incorrect to say it’s O(2N) according to the definition of big-O, but it’s not idiomatic.
Just to note, there is no difference between omitting the slower-growing term when we write n^2 + n = O(n^2) and omitting the scale factor when we write 2n = O(n). Just as you can write O(2n), you can write O(n^2 + n). The reason we don't is that O(2n) and O(n) are two names for the same set, just as O(n^2) and O(n^2 + n) are two names for the same set.
I was confused as in your comment I didn't connect that you were discussing the loop from the grandparent comment.
Your patient explanation makes it super clear, both for my over skimming and for others who read this and are less familiar with O notation!
I found the book Fluent Python to be a great introduction to the ideas behind abstraction in Python.
Apparently, it's cadged from the Art of the Metaobject Protocol, which is a great book (which annoyingly enough, is not available in ebook form, which is a shame as typing loads of code from a dead-tree book is time consuming).
For immutable types, a = a + b and a += b do behave exactly the same. For mutable ones, the problem is that of the three statements (taking lists as an example)
a = a + b # (1)
a += b # (2)
a.extend(b) # (3)
That doesn’t mean that knowing an implementation detail can’t be useful, just that I feel the way (1) and (2) for lists differ (“semantics”) is of a different nature from the way (1) and (2) for strings differ (“implementation”) and worth keeping in a different mental drawer.
It's possible (likely? ) that I'm missing something, but why are they exclusive? In principle, I would have thought that an optimizing compiler could rewrite (1) into (3) and thus give all three the same semantics.
(I'm not speaking about what would be possible for Python in particular, just in general terms)
If you start off with:
a=c=[1,2,3]
b=[4,5]
a=a+b
The other forms explicitly change the object pointed to by 'a'.
a = [1, 2]; b = [3, 4]
c = a
a += b
print(c) # [1, 2] — assignment was a copy
print(a) # [1, 2, 3, 4]
And certainly, there are languages that do that.
Just not Python — for performance reasons, you need to be explicit about copying large chunks of memory, though it includes a fair number of footguns like concatenation of strings and lists, or even slicing — eg. "for a in long_list[:-2]:" will make a duplicate of long_list in memory.
Eg.
a = [1, 2]
b = [3, 4]
c = a
Would you really expect a += b and a = a + b to behave the same, and what would c be in that case?
Yes, I would, and it really is worth noting that they don't.
c would be [1,2,3,4], and it would be an alias of a. But both of those points are also true of the way things actually do work. I don't really understand your question.
a = [1]
c = a
a = a + a
Now, what is c ? what is a?
Then try again with a+=a
>>> a = [1, 2]
>>> b = [3, 4]
>>> c = a
>>> a = a + b
>>> c
[1, 2]That is not true.
>>> a = [1, 2]
>>> b = [3, 4]
>>> c = a
>>> a += b
>>> c
[1, 2, 3, 4]
And contrast that with:
>>> a = [1, 2]
>>> b = [3, 4]
>>> c = a
>>> a = a + b
>>> c
[1, 2]
If "c" remains an alias of "a" after you've assigned something else to "a", then there is no way in language to keep a reference to what "a" was.
Eg. what you seem to be proposing is that assignment works like this:
a = 4
old_a = a
a = 5
print(old_a) # prints out 5.
Python is like it is for practical performance reasons: lists and dicts are by-reference because copying them is expensive. You've got to do it explicitely with .copy() or deepcopy module. That's a basic lesson on Python I was referring to. And sure, it could have been designed the other way around, when you'd have to introduce a "refcopy" or "&" operator when performance is needed, but it wasn't designed that way. There are other languages which do that.
I can see the point of "a += b" unexpectedly updating in place, but just upon reading it, I'd struggle to figure out what's supposed to happen. In a code review, I'd suggest a developer to switch to "a.extend(b)".
Basically, if they were to behave the same, I don't think an argument can be made for the common result of "c" to evaluate to [1, 2, 3, 4], but rather to [1, 2].
"Implementations of operator traits should be unsurprising in their respective contexts, keeping in mind their usual meanings"
Which seems like reasonable advice.
E.g.
1 + 2
1.__add__(2)
a += b
a.__iadd__(b)
Then in practise, there are a lot of optimizations and implementation details.
>>> mylist_1 = [1, 2, 3]
>>> mylist_2 = [4, 5]
>>> print(id(mylist_1), id(mylist_2))
1614327515784 1614319969800
>>> mylist_1 = mylist_1 + mylist_2
>>> print(mylist_1)
>>> print(id(mylist_1))
[1, 2, 3, 4, 5, 4, 5]
1614319969416
>>> l1=[1,2,3]
>>> l2=[4,5]
>>> l1=l1+l2
>>> print(l1)
[1, 2, 3, 4, 5] >>> id([1,2,3]) == id([4,5,6])
True
>>> id([1,2,3]), id([4,5,6])
(140720308985224, 140720308985224)
Not in this case though, but I'm not sure why the author uses a black-box model to explain it rather than looking at the source, `iadd` uses `extend`: https://github.com/python/cpython/blob/main/Objects/listobje...
And why wouldn't an explanation help the audience learn?
>>> a = [1,2,3]
>>> b = [4,5,6]
>>> id(a), id(b)
(140659402612872, 140659403098568) b = np.ones(1)
c = np.ones(1)
c = c/(2**73)
b += c
>>> ufunc 'add' output (typecode 'O') could not be coerced to provided output parameter (typecode 'd') according to the casting rule ''same_kind''
[1] https://stackoverflow.com/questions/12588986/typeerror-gener...
>>> orig = [1,2,3]
>>> L1 = orig
>>> L2 = [7,8]
>>> L1 = L1 + L2
>>> orig
[1, 2, 3]
>>> orig = [1,2,3]
>>> L1 = orig
>>> L2 = [7,8]
>>> L1 += L2
>>> orig
[1, 2, 3, 7, 8]I believe it works much like a self-fulfilling prophecy. Language designers think that it is more readable, so they do it. Language users use it and became habituated to it. So it becomes more readable because some people believe that it is more readable.
What is unreadable with:
a.extend(b)
c = a.clone().extend(b);
Even if it is more readable, does it justify all the obscurity?
Which, it turns out, you sometimes don't. It's especially bad when you think you know what it means, but you're mistaken.
I was kind of joking, of course, but only kind of. I'm a happy user of operator overloading.
You ask about a.add(b) but notice that's also using two operators.
First it needs a . operator for member access. Languages rarely allow you to overload this operator because doing so makes your head hurt, but there's no reason in theory it couldn't exist.
[In Python we can use __getattribute__ to meddle with this, but to avoid infinite recursion we can't use __getattribute__ to meddle with the operator overloading, such as __getattribute__ itself... ]
Second you need a () operator to call the member. This you can sometimes overload, for example in C++. So what this does might be defined by that operator overload.
The only way to avoid this being too confusing to use is to obey conventions, and even once you do that many of the operator overloads will be rarely needed and one wonders whether to just abolish overloading them.
Worse, unlike a function call, operators sometimes come with other semantic expectations that may be impossible to enforce.
For example the operators && and || are short-cutting logic booleans, in almost any programming language with such an operator, in_cache(foo) || slow_check(foo) only performs slow_check(foo) when in_cache(foo) was false. But an overload can't ensure this! Instead both will be evaluated and the results provided to the operator overload function, too late to optimise.
Overloading should be used very sparingly. If any significant fraction of your users find your overload confusing, it was a bad idea. Better than ten people wonder why they must write a.add(b) than that one person writes a + b and then is completely astonished by what you decided that does.