50

Is there any any faster way to swap two list elements in Python than

L[a], L[b] = L[b], L[a]

or would I have to resort to Cython or Weave or the like?

Gerald Senarclens de Grancy
  • 7,154
  • 7
  • 41
  • 55
  • 1
    Nope, not kidding. Am implementing an algorithm where this is done billions of times (depending on the problem size) and was wondering if there was anything easy I could do to speed this up. – Gerald Senarclens de Grancy Dec 29 '10 at 12:43
  • 2
    There is probably many ways to speed up your program before trying to speed up this particular swap. A bit of context could be interesting. – kriss Dec 29 '10 at 12:45
  • I mean, in full generality this could be hard to speed up, but in many particular cases it can be made faster. Say you have a == b, then to speedup just do nothing, etc. – kriss Dec 29 '10 at 12:47
  • The reason for the question was that, when putting the above in a one-lining function and using a profiler, the tottime of the function takes place 5 in hundreds of functions (after already optimizing a few other functions). I though that there wasn't anything faster than this, but wasn't absolutely sure - hence I asked. – Gerald Senarclens de Grancy Dec 29 '10 at 13:05
  • Exactly what algorithm are you implementing that requires swapping elements around in a list a whole bunch? – Karl Knechtel Dec 29 '10 at 13:10
  • A simple local search for a TSP. – Gerald Senarclens de Grancy Dec 29 '10 at 13:17
  • 1
    Having worked on similar TSP local search problems for my master's project, I can tell you that you'll a) want to choose a better algorithm than ones like 2-Opt, and b) Psyco (or Cython, etc.) is your friend. – Brandon Dec 29 '10 at 13:30
  • Thanks for the hint, I know that 2-Opt isn't grand. However, I'm not trying to find good solutions to a TSP but am benchmarking a series of implementations of the 2-Opt. Cython etc. will be used in some of them anyway. – Gerald Senarclens de Grancy Dec 29 '10 at 14:53
  • btw - yes, I have read http://www.scipy.org/PerformancePython :) – Gerald Senarclens de Grancy Dec 29 '10 at 15:22
  • 2
    Gerald, if you are interested, I think I still have a simple Tkinter GUI that reads TSPLIB problems and displays them while they're being solved (via 2-Opt) in a separate thread. It's good for visualizing whether your algorithms are running properly. – Brandon Dec 29 '10 at 15:27
  • That would be grand to have, thanks in advance! You can find a link to my email address on my SO user profile. – Gerald Senarclens de Grancy Dec 29 '10 at 15:40
  • Okay, I'm at work now, so I'll look at home when I get a chance. – Brandon Dec 29 '10 at 16:27
  • Gerald, I've posted it at http://mysite.verizon.net/bcorfman/readtsp032306.zip – Brandon Dec 30 '10 at 20:59
  • Was afk a little while and just saw your comment. Thanks for the download link, I'll play around w/ it sometime soon. Looks promising! – Gerald Senarclens de Grancy Jan 01 '11 at 23:57
  • 1
    @UkuLoskit: Don't be a jerk. – Jossie Calderon Aug 22 '16 at 19:00

4 Answers4

132

Looks like the Python compiler optimizes out the temporary tuple with this construct:

code:

import dis

def swap1():
  a=5
  b=4
  a, b = b, a

def swap2():
  a=5
  b=4
  c = a
  a = b
  b = c

print 'swap1():'
dis.dis(swap1)
print 'swap2():'
dis.dis(swap2)

output:

swap1():
  6           0 LOAD_CONST               1 (5)
              3 STORE_FAST               0 (a)

  7           6 LOAD_CONST               2 (4)
              9 STORE_FAST               1 (b)

  8          12 LOAD_FAST                1 (b)
             15 LOAD_FAST                0 (a)
             18 ROT_TWO             
             19 STORE_FAST               0 (a)
             22 STORE_FAST               1 (b)
             25 LOAD_CONST               0 (None)
             28 RETURN_VALUE        
swap2():
 11           0 LOAD_CONST               1 (5)
              3 STORE_FAST               0 (a)

 12           6 LOAD_CONST               2 (4)
              9 STORE_FAST               1 (b)

 13          12 LOAD_FAST                0 (a)
             15 STORE_FAST               2 (c)

 14          18 LOAD_FAST                1 (b)
             21 STORE_FAST               0 (a)

 15          24 LOAD_FAST                2 (c)
             27 STORE_FAST               1 (b)
             30 LOAD_CONST               0 (None)
             33 RETURN_VALUE

Two loads, a ROT_TWO, and two saves, versus three loads and three saves. You are unlikely to find a faster mechanism.

Ignacio Vazquez-Abrams
  • 776,304
  • 153
  • 1,341
  • 1,358
3

If you could post a representative code sample, we could do a better job of benchmarking your options. FWIW, for the following dumb benchmark, I get about a 3x speedup with Shed Skin and a 10x speedup with PyPy. 

from time import time

def swap(L):
    for i in xrange(1000000):
        for b, a in enumerate(L):
            L[a], L[b] = L[b], L[a]

def main():
    start = time()
    L = list(reversed(range(100)))
    swap(L[:])
    print time() - start
    return L

if __name__ == "__main__":
    print len(main())

# for shedskin:
# shedskin -b -r -e listswap.py && make
# python -c "import listswap; print len(listswap.main())"
TryPyPy
  • 6,214
  • 5
  • 35
  • 63
  • thanks for trying shedskin. I see about a 100x speedup though when I try this program. do you remember which version of shedskin you were using? –  May 20 '11 at 18:29
0

I try this method as the easiest way to swap two numbers in a list:

lst= [23, 65, 19, 90]
pos1 = lst.pop(0)
pos2 = lst.pop(1)
lst.append(pos1)
lst.append(pos2)
print(lst)
Bhupendra Soni
  • 1
  • 1
-5

I found this method as the fastest way to swap two numbers:

mylist   = [11,23,5,8,13,17];
first_el = mylist.pop(0)
last_el  = mylist.pop(-1)
mylist.insert(0, last_el)  
mylist.append(first_el)
Ashish Mohapatra
  • 1
  • 1