Fastest way to swap characters in a string (Python)

Krishnan Shankar 0
Viewed 60

I've seen many questions on the most efficient way to do certain things, but one I haven't seen (and one which would help a lot) is the most efficient way to swap two characters in a string. As I thought of it, I immediately went to converting it into a list, swapping the elements, and then joining it back:

def swap(s: str, index1: int, index2: int) -> str:
    new_s = list(s)
    new_s[index1], new_s[index2] = new_s[index2], new_s[index1]
    return "".join(new_s)

However, I was wondering if there's a better way. I tried list slicing with something like this:

def swap(s: str, index1: int, index2: int) -> str:
    lindex = min(index1, index2)
    gindex = max(index1, index2)
    return s[:lindex] + s[gindex] + s[lindex + 1:gindex] + s[lindex] + s[gindex + 1:]

However, it seemed to be much slower, a whole 45% slower than the first approach. Does anyone of a better (read: more efficient) solution to this? Or is the most efficient way just converting it to a list?

performance python-3.x python
1 Answers

You're wasting time on the function calls to min and max. You can rewrite your function as:

def swap(s: str, index1: int, index2: int) -> str:
    lindex, gindex = (index1, index2) if index1 < index2 else (index2, index1)
    return s[:lindex] + s[gindex] + s[lindex + 1:gindex] + s[lindex] + s[gindex + 1:]

and even for small strings it is more performant than the list-based approach.

In fact, as the strings get bigger, the list-based approach gets signficantly slower than using strings directly. For example, with this timeit setup

from timeit import timeit

timeit(setup='''
import random
s = "abcdefghijklmnopqrstuvxyz" * 100
num = 1000000
indexes = [random.choices(range(len(s)), k=2) for _ in range(num)]
def swap(s: str, index1: int, index2: int) -> str:
    new_s = list(s)
    new_s[index1], new_s[index2] = new_s[index2], new_s[index1]
    return "".join(new_s)
''',
stmt='for i in range(num): swap(s, *indexes[i])',
number=1
)

the string-based functions are about 15x faster than the list-based function.

Update

Prompted by a comment, I benchmarked the two methods of swapping the index values, calling the functions with 2 random numbers, swapping the order of the inputs for a second call to remove any bias for a particular ordering. The testing code was:

timeit(setup='''
import random
i1, i2 = random.choices(range(1000000), k=2)
def swap(index1: int, index2: int) -> (int, int):
    lindex = min(index1, index2)
    gindex = max(index1, index2)
    return lindex, gindex
''', stmt='''
swap(i1, i2)
swap(i2, i1)
''',
number=1000000
)

timeit(setup='''
import random
i1, i2 = random.choices(range(1000000), k=2)
def swap(index1: int, index2: int) -> (int, int):
    lindex, gindex = (index1, index2) if index1 < index2 else (index2, index1)
    return lindex, gindex
''', stmt='''
swap(i1, i2)
swap(i2, i1)
''',
number=1000000
)

On my computer, the results were:

min/max     0.4447700999735389
if/else     0.22195569999166764

So about 2x faster for the if test.

usergAKD0
Related