python a,b = b,a implementation? How is it different from C++ swap function?

Question

I met this problem when I want to try a python version of: https://leetcode.com/problems/first-missing-positive/discuss/17071/My-short-c++-solution-O(1)-space-and-O(n)-time

I am not sure why a[0], a[a[0]] = a[a[0]], a[0] this one does not do the swap?

>>> nums
[2, 1, 0]
>>> a = [2,1,0]
>>> a[0], a[a[0]] = a[a[0]], a[0]
>>> a
[2, 1, 0]
>>> a[0]
2
>>> a[0],a[2] = a[2], a[0]
>>> a
[0, 1, 2]

My guess is that the implementation of a, b = b, a syntax is something like:

tmp = a[0] (tmp = 2)
a[0]  = a[a[0]] (a[0] = a[2] = 0)
a[a[0]] = tmp (a[a[0]] = a[0] = tmp = 2)

Then I checked the implementation of swap function in C++. I know nothing about C++, but it looks like the idea is the same : http://www.cplusplus.com/reference/algorithm/swap/

The behavior of these function templates is equivalent to:
template <class T> void swap (T& a, T& b)
{
  T c(std::move(a)); a=std::move(b); b=std::move(c);
}
template <class T, size_t N> void swap (T (&a)[N], T (&b)[N])
{
  for (size_t i = 0; i<N; ++i) swap (a[i],b[i]);
}

we have c = a, then a = b and b = a So why C++ swap function does not have this problem? And how to write this kind of swap function in a pythonic way?

Answer 1

This kind of the behaviour is indeed related to the way Python evaluates the expression of the type

a,b=b,a

In fact, what Python does is first it "prepares" the values of the right side by creating a tuple (b,a). Then this tuple is unpacked and assigned to the variables in the reverse order.

It is important to note that although Python uses references to objects the objects the variable names refer to may change if they refer to values of immutable type. It is not so with mutable types (illustrated by example in Python FAQ).

To break down the example with mutable types (lists) that you used:

a = [2,1,0]    
a[0], a[a[0]] = a[a[0]], a[0]

1. a[a[0]] takes the value from the a[0] element (equal to 2) of the list a (value 0).
2. a[0] is 2 hence the tuple created is (0,2)
3. Tuple (0,2) is unpacked and 0 replaces 2 in the list (0th element).
4. Now, a[a[0]] can be read as: take 0th element of list a (which is currently 0) and then replace the value in the list at that place with 2 from tuple unpacking (now 0 is replaced by 2 - which make the operation look like it does nothing to the list).

As suggested in the answer from von Oak changing the order helps because the step from the point 4. above does not replace the value again.

I suggest you refer to passing by assignment answer to understand functions and parameter passing.

Answer 2

To understand this you need to go inside the implementation using dis.

First lets consider a simple swap function:

from dis import dis

def swap(i, j):
    i, j = j, i

dis(swap)

Output Byte Code:

4             0 LOAD_FAST                1 (j)
              2 LOAD_FAST                0 (i)
              4 ROT_TWO
              6 STORE_FAST               0 (i)
              8 STORE_FAST               1 (j)
             10 LOAD_CONST               0 (None)
             12 RETURN_VALUE

You can see that there is ROT_TWO which means that

Swaps the two top-most stack items.

This ROT_TWO is mainly responsible for the swapping.

Now coming to your question:

Lets take the example which is working:

from dis import dis

def swap():
    a = [2, 1]
    a[0], a[1] = a[1], a[0]

dis(swap)

Output Byte Code :

  4           0 LOAD_CONST               1 (2)
              2 LOAD_CONST               2 (1)
              4 BUILD_LIST               2
              6 STORE_FAST               0 (a)

  5           8 LOAD_FAST                0 (a)
             10 LOAD_CONST               2 (1)
             12 BINARY_SUBSCR
             14 LOAD_FAST                0 (a)
             16 LOAD_CONST               3 (0)
             18 BINARY_SUBSCR
             20 ROT_TWO
             22 LOAD_FAST                0 (a)
             24 LOAD_CONST               3 (0)
             26 STORE_SUBSCR
             28 LOAD_FAST                0 (a)
             30 LOAD_CONST               2 (1)
             32 STORE_SUBSCR
             34 LOAD_CONST               0 (None)
             36 RETURN_VALUE

Output byte code is similar to what we have when it is a simple swap function.

But when the code is changed:

from dis import dis

def swap():
    a = [1, 0]
    a[0], a[a[0]] = a[a[0]], a[0]
dis(swap)

swap()

Output is

  4           0 LOAD_CONST               1 (1)
              2 LOAD_CONST               2 (0)
              4 BUILD_LIST               2
              6 STORE_FAST               0 (a)

  5           8 LOAD_FAST                0 (a)
             10 LOAD_FAST                0 (a)
             12 LOAD_CONST               2 (0)
             14 BINARY_SUBSCR
             16 BINARY_SUBSCR
             18 LOAD_FAST                0 (a)
             20 LOAD_CONST               2 (0)
             22 BINARY_SUBSCR
             24 ROT_TWO
             26 LOAD_FAST                0 (a)
             28 LOAD_CONST               2 (0)
             30 STORE_SUBSCR
             32 LOAD_FAST                0 (a)
             34 LOAD_FAST                0 (a)
             36 LOAD_CONST               2 (0)
             38 BINARY_SUBSCR
             40 STORE_SUBSCR
             42 LOAD_CONST               0 (None)
             44 RETURN_VALUE

You can see the output byte code that top two items are the same. Hence it doesn't swap

Answer 3

It's easy to think about it also only on the paper (e.g. at the job interview) and you don't need to debug or disassemble code to bytecode for understanding.

I also think it hasn't anything to do with the implementation of swap function in C++. These are unrelated things.

What you only need to know is that the right side is completely evaluated first and then the values from the right side of the expression are assigned to the values on the left side in the order from the left to the right. Sophros answered it right way I only expand the idea further and in more detail.

Imagine the first case. We have:

a = [2,1,0]

a[0], a[a[0]] = a[a[0]], a[0]

When we start to execute this code, the right side evaluates first, so we will have

a[0], a[a[0]] = a[a[0]], a[0]    # a[a[0]] == 0, a[0] == 2, a == [2, 1, 0]

On the right side, we have tuple (0, 2) and a is still [2, 1, 0]

Next, we start to assign to the left side of the expression from the left, so to the a[0] we assign the first item from the tuple, which is 0. Now we have

a[0], a[a[0]] = (0, 2)   # a[0] == 0, a == [0, 1, 0]

And now we execute the last part of the assignment, which is to a[a[0]] assign 2. But a[0] is now 0, so after reduction we assign to a[0] value 2. Therefore values after the last assignment are

a[0], a[a[0]] = (0, 2)   # a[a[0]] == 2, a == [2, 1, 0]

Which seems, that nothing changed and values didn't swap, but as is apparent from above a was [2,1,0], then [0,1,0] and lastly again [2,1,0]. So it seems, nothing changed and swap doesn't work.

And now the second case, where we only change the order of variables in the expression:

a = [2,1,0]

a[a[0]], a[0] = a[0], a[a[0]]

When we start to execute this code, the right side evaluates first, so we will have

a[a[0]], a[0] = a[0], a[a[0]]    # a[0] == 2, a[a[0]] == 0, a == [2, 1, 0]

On the right side, we have tuple (2, 0) and a is still [2, 1, 0]

Next, we start to assign to the left side of the expression from the left, so to the a[a[0]] we assign the first item from the tuple, which is 2. a[0] is 2, so after reduction, we assign to a[2] value 2. Now we have

a[a[0]], a[0] = (2, 0)   # a[a[0]] == 2, a == [2, 1, 2]

And now we execute the last part of the assignment, which is to a[0] assign 0. Therefore values after the last assignment are

a[a[0]], a[0] = (2, 0)   # a[0] == 0, a == [0, 1, 2]

Now this works as expected.

So it is necessary also think about the order when you have dependent variables in your swap expression. As dependent variables I mean that in the first case we have on the left side a[0], a[a[0]] that means a[0] change it's value and a[a[0]] use this changed value, which leads to unwanted behavior.

Finally, regardless of the programming language, it's better not to use dependent variables (array index for another array index etc.), when you want to swap their values.

Answer 4

Python and C++ are different languages with different rules. That's largely the reason why superficially similar constructs behave differently in these languages.

You cannot write a generic swap in Python that would work with input like a[0], a[a[0]]. This is not a problem. You shouldn't ever try to swap such things in any language in order to avoid confusion and improve your chances for future employment as a programmer.

If you absolutely positively need to swap array elements indexed by elements of the same array, you can do it like so in Python:

p, q, a[p], a[q] = index0, index1, a[q], a[p]

where index0 and index1 may be any expression involving a[i], a[a[i]], a[a[a[i]]] or anything similar. For example

p, q,  a[p], a[q] = a[0], a[a[0]],  a[q], a[p]

works.

Answer 5

So, this is actually a feature of python called multiple assignment that is sometimes difficult to grasp if you are coming from other languages. This is how it works.

Eg. a, b = b, a

This code will actually swap the elements. I will give a simple intuitive explanation, and then a more technical one.

1. The RHS is first evaluated, and then values are assigned respectively to variables (labels) on the LHS.
2. So you can actually define a tuple (a,b) as a,b in python, the parentheses are just for better readability. So your RHS is a tuple that is unpacked and each element is assigned respectively to each label on the LHS. So all the following code snippets are equivalent.

a, b = b, a
a, b = (b, a)
a, b = [b, a]

NOTE: The notion of variables in python is very very different from other languages where they are containers of a certain type to store values of that type. In python, labels is a more correct term than variables because you are just labeling an object with this name, and the object can be of any datatype. So to understand this code, you are not actually swapping values when you do a,b = b,a, you are swapping labels.
So, python first looks up the values that labels b and a point to on the RHS, puts those values there, and then it just gives these values new labels.