Swapping values of two variables

[EK]

In python, I set:

x=1
y=3

z = x
x = y
y = z


This gave me 3 1, which are the values of x and y swapped.
The following would have given me the same result:
x, y = y, x



But could the swapping be done using less extra memory than this? What is the minimum amount of extra memory required to exchange two 32-bit quantities? What would be the pseudocode that achieves this minimum?

 

[tony.clarke5]

> In python, I set:
> x=1
> z = x

> x = y
> This gave me 3 1, which are the values of x and y swapped.

> The following would have given me the same result:
> But could the swapping be done using less extra memory than this? What is the minimum amount of extra memory required to exchange two 32-bit quantities? What would be the pseudocode that achieves this minimum?

How about:
def transpose(x, y):
print x, y, 'becomes: ',
x = x + y
y = x - y
x = x - y
print x, ' ', y

transpose(1,3)
transpose (9,8)

 

[Steven D'Aprano]

> In python, I set:

>

> x=1

> y=3

>

> z = x

> x = y

> y = z

>

>

> This gave me 3 1, which are the values of x and y swapped. The following

> would have given me the same result: x, y = y, x

Yes.

> But could the swapping be done using less extra memory than this? What

> is the minimum amount of extra memory required to exchange two 32-bit

> quantities? What would be the pseudocode that achieves this minimum?

Ints in Python are *objects*, not 32-bit quantities. An int is 12 bytes
(96 bits) in size; a long will use as much memory as needed. If your
application needs to optimize a swap of two ints, then Python is probably
going to be much too memory-intensive for you.

(But my money is on you doing premature optimization.)

 

[Steven D'Aprano]

How about:
def transpose(x, y):
print x, y, 'becomes: ',
x = x + y
y = x - y
x = x - y
print x, ' ', y

transpose(1,3)
transpose (9,8)

I'm not sure what the point of that function is. It doesn't actually swap
its arguments:
42

And it certainly doesn't save memory, as the original poster asked:

1 0 LOAD_NAME 0 (y)
3 LOAD_NAME 1 (x)
6 ROT_TWO
7 STORE_NAME 1 (x)
10 STORE_NAME 0 (y)
13 LOAD_CONST 0 (None)
16 RETURN_VALUE

2 0 LOAD_FAST 0 (x)
3 PRINT_ITEM
4 LOAD_FAST 1 (y)
7 PRINT_ITEM
8 LOAD_CONST 1 ('becomes: ')
11 PRINT_ITEM

3 12 LOAD_FAST 0 (x)
15 LOAD_FAST 1 (y)
18 BINARY_ADD
19 STORE_FAST 0 (x)

4 22 LOAD_FAST 0 (x)
25 LOAD_FAST 1 (y)
28 BINARY_SUBTRACT
29 STORE_FAST 1 (y)

5 32 LOAD_FAST 0 (x)
35 LOAD_FAST 1 (y)
38 BINARY_SUBTRACT
39 STORE_FAST 0 (x)

6 42 LOAD_FAST 0 (x)
45 PRINT_ITEM
46 LOAD_CONST 2 (' ')
49 PRINT_ITEM
50 LOAD_FAST 1 (y)
53 PRINT_ITEM
54 PRINT_NEWLINE
55 LOAD_CONST 0 (None)
58 RETURN_VALUE



The compiled code of the transpose function *alone* (not including all
the other associated parts) takes 59 bytes, or 472 bits.
59

Even if it worked, that's hardly using less memory than a direct swap.

 

[Kottiyath]

>> In python, I set:

> >> x=1
> >> z = x

> >> x = y
> >> This gave me 3 1, which are the values of x and y swapped. The

> >> following would have given me the same result: x, y = y, x

> >> But could the swapping be done using less extra memory than this? What

> >> is the minimum amount of extra memory required to exchange two 32-bit

> >> quantities? What would be the pseudocode that achieves this minimum?

> > How about:

> > def transpose(x, y):

> > * * print x, y, 'becomes: ',

> > * * x = x + y

> > * * y = x - y

> > * * x = x - y

> > * * print x, ' ', y
> > transpose(1,3)

> > transpose (9,8)

I'm not sure what the point of that function is. It doesn't actually swap
its arguments:

23 42 becomes: *42 * 23>>> x
23
42

And it certainly doesn't save memory, as the original poster asked:

* 1 * * * * * 0 LOAD_NAME * * * * * * * *0 (y)
* * * * * * * 3 LOAD_NAME * * * * * * * *1 (x)
* * * * * * * 6 ROT_TWO
* * * * * * * 7 STORE_NAME * * * * * * * 1 (x)
* * * * * * *10 STORE_NAME * * * * * * * 0 (y)
* * * * * * *13 LOAD_CONST * * * * * * * 0 (None)
* * * * * * *16 RETURN_VALUE

* 2 * * * * * 0 LOAD_FAST * * * * * * * *0 (x)
* * * * * * * 3 PRINT_ITEM
* * * * * * * 4 LOAD_FAST * * * * * * * *1 (y)
* * * * * * * 7 PRINT_ITEM
* * * * * * * 8 LOAD_CONST * * * * * * * 1 ('becomes: ')
* * * * * * *11 PRINT_ITEM

* 3 * * * * *12 LOAD_FAST * * * * * * * *0 (x)
* * * * * * *15 LOAD_FAST * * * * * * * *1 (y)
* * * * * * *18 BINARY_ADD
* * * * * * *19 STORE_FAST * * * * * * * 0 (x)

* 4 * * * * *22 LOAD_FAST * * * * * * * *0 (x)
* * * * * * *25 LOAD_FAST * * * * * * * *1 (y)
* * * * * * *28 BINARY_SUBTRACT
* * * * * * *29 STORE_FAST * * * * * * * 1 (y)

* 5 * * * * *32 LOAD_FAST * * * * * * * *0 (x)
* * * * * * *35 LOAD_FAST * * * * * * * *1 (y)
* * * * * * *38 BINARY_SUBTRACT
* * * * * * *39 STORE_FAST * * * * * * * 0 (x)

* 6 * * * * *42 LOAD_FAST * * * * * * * *0 (x)
* * * * * * *45 PRINT_ITEM
* * * * * * *46 LOAD_CONST * * * * * * * 2 (' ')
* * * * * * *49 PRINT_ITEM
* * * * * * *50 LOAD_FAST * * * * * * * *1 (y)
* * * * * * *53 PRINT_ITEM
* * * * * * *54 PRINT_NEWLINE
* * * * * * *55 LOAD_CONST * * * * * * * 0 (None)
* * * * * * *58 RETURN_VALUE

The compiled code of the transpose function *alone* (not including all
the other associated parts) takes 59 bytes, or 472 bits.

59

Even if it worked, that's hardly using less memory than a direct swap.
[/QUOTE]

Is it possible to swap two floats without a variable?

 

[tony.clarke5]

> On Thu, 29 Jan 2009 17:50:04 -0800, tony.clarke5 wrote:









I'm not sure what the point of that function is. It doesn't actually swap
its arguments:


23 42 becomes: *42 * 23>>> x
23

42

And it certainly doesn't save memory, as the original poster asked:


* 1 * * * * * 0 LOAD_NAME * * * * * * * *0 (y)
* * * * * * * 3 LOAD_NAME * * * * * * * *1 (x)
* * * * * * * 6 ROT_TWO
* * * * * * * 7 STORE_NAME * * * * * * * 1 (x)
* * * * * * *10 STORE_NAME * * * * * * * 0 (y)
* * * * * * *13 LOAD_CONST * * * * * * * 0 (None)
* * * * * * *16 RETURN_VALUE


* 2 * * * * * 0 LOAD_FAST * * * * * * * *0 (x)
* * * * * * * 3 PRINT_ITEM
* * * * * * * 4 LOAD_FAST * * * * * * * *1 (y)
* * * * * * * 7 PRINT_ITEM
* * * * * * * 8 LOAD_CONST * * * * * * * 1 ('becomes: ')
* * * * * * *11 PRINT_ITEM

* 3 * * * * *12 LOAD_FAST * * * * * * * *0 (x)
* * * * * * *15 LOAD_FAST * * * * * * * *1 (y)
* * * * * * *18 BINARY_ADD
* * * * * * *19 STORE_FAST * * * * * * * 0 (x)

* 4 * * * * *22 LOAD_FAST * * * * * * * *0 (x)
* * * * * * *25 LOAD_FAST * * * * * * * *1 (y)
* * * * * * *28 BINARY_SUBTRACT
* * * * * * *29 STORE_FAST * * * * * * * 1 (y)

* 5 * * * * *32 LOAD_FAST * * * * * * * *0 (x)
* * * * * * *35 LOAD_FAST * * * * * * * *1 (y)
* * * * * * *38 BINARY_SUBTRACT
* * * * * * *39 STORE_FAST * * * * * * * 0 (x)

* 6 * * * * *42 LOAD_FAST * * * * * * * *0 (x)
* * * * * * *45 PRINT_ITEM
* * * * * * *46 LOAD_CONST * * * * * * * 2 (' ')
* * * * * * *49 PRINT_ITEM
* * * * * * *50 LOAD_FAST * * * * * * * *1 (y)
* * * * * * *53 PRINT_ITEM
* * * * * * *54 PRINT_NEWLINE
* * * * * * *55 LOAD_CONST * * * * * * * 0 (None)
* * * * * * *58 RETURN_VALUE

The compiled code of the transpose function *alone* (not including all
the other associated parts) takes 59 bytes, or 472 bits.


59

Even if it worked, that's hardly using less memory than a direct swap.

Should have been more explicit about that: the values are swapped
within the namespace of the function, the function is just for
demonstration of the process. WIthout the function, this is the
result:
Python 2.5.1 (r251:54869, Apr 18 2007, 22:08:04)
[GCC 4.0.1 (Apple Computer, Inc. build 5367)] on darwin
Type "help", "copyright", "credits" or "license" for more information.Need to think about swapping floats though.
Tony

 

[Steven D'Aprano]

Is it possible to swap two floats without a variable?

In Python? Sure.

f = 1.23
g = 2.87
f, g = g, f



This idiom is independent of the types of the objects:

x = "hello world"
y = [1, 2.0, None, "xyz", {}]
x, y = y, x

In other languages? Hard to say. You *might* be able to use the XOR trick
on floats, if you can access a float as a set of raw bytes. Same for
strings, if they are the same length.

Assuming that the floats are of similar size, not NaNs or INFs, not
subject to overflow or underflow, and not subject to rounding error, you
can do this trick:
(2.8700000000000001, 1.2299999999999995)

But notice the round-off error in g. It gets worse if your values are of
radically different sizes:

(1.2000000000000001e+35, 0.0)


This really is a trick, not something you should be doing in production
code.

 

[Aahz]

>In python, I set:



>z = x

>x = y

>This gave me 3 1, which are the values of x and y swapped.

>The following would have given me the same result:


>But could the swapping be done using less extra memory than this? What

>is the minimum amount of extra memory required to exchange two 32-bit

>quantities? What would be the pseudocode that achieves this minimum?

This looks like a homework problem to me....