ActiveState Code

Recipe 119029: reverse a string

one line to reverse a string

Python 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
f = lambda s:s and f(s[1:])+s[0]
#or
f = lambda s:reduce(lambda a,b:b+a,s,'')
#or 
f = lambda s,l=[]:[l.extend(s),l.reverse(),''.join(l)][2]
#after Davids observations I was wondering how come third
#version is slower ...IT can't be as it uses builtin list functions
#that are in C
#then I came to know that in third version default variable l=[] keeps
#its previous info
#try
#f('anurag') twice
#so I changed it to

f = lambda s,l=[[]]:[l.pop(),l.append(list(s)),l[0].reverse(),''.join(l[0])][2]

#now it is the fastest one!!

Comments

  1. 1. At 1:11 p.m. on 4 apr 2002, H. Krekel said:

    Very nice, but stack use is O( len(string) ). I like your ideas of recursive lambdas although

    f('a'*10000)

    will usually fail with stack overflow.

  2. 2. At 4:05 p.m. on 4 apr 2002, Kapil Thangavelu said:

    how about.

    strlist = list(string_var); strlist.reverse(); ''.join(strlist)

    not really a one liner ;)

  3. 3. At 3:17 a.m. on 5 apr 2002, anurag uniyal (the author) said:

    Second version won't fail. i tried that for f('a'*100000) :)

  4. 4. At 3:36 a.m. on 5 apr 2002, anurag uniyal (the author) said:

    but that can be done. see third version I have stiched it as a one liner, one liner i mean that can be used in lambda functions

    using list for evaluating mutiple expressions is a great techiniqe :)

  5. 5. At 3:47 a.m. on 5 apr 2002, H. Krekel said:

    Cool. Very good solution! By the way i would be interested in your oppinion about my related new recipe http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/119596 I actually came to it thinking about your recipe! Good that you didn't have the third solution from the beginning :-)

  6. 6. At 3:55 a.m. on 5 apr 2002, H. Krekel said:

    Maybe you can turn my recipe into a lambda? I just thought, that we might combine our ideas to turn my recipe into lambda functions. I have some ideas and see some problems. we should probably discuss this via email. drop me a note if you are interested to collaborate/discuss holger at trillke net. Or just deliver the lambda :-)

  7. 7. At 1:57 a.m. on 8 apr 2002, anurag uniyal (the author) said:

    sure. I am just doing that but as it is lot of code it seems slight difficult... ...any way i will try to improve your shortcut :)

    if u want to contact me my mail id is anuraguniyal@yahoo.com

  8. 8. At 8:59 p.m. on 19 apr 2002, David Gould said:

    Try using list comprehensions. Another way to do this is to use list comprehensions:

    f3 = lambda s: ''.join([s[i] for i in xrange(len(s)-1, -1, -1)])

    or

    f4 = lambda s: ''.join([s[-1 - i] for i in xrange(len(s))]))

    I find these pretty readable and easy to write. They also perform quite well (clearly better than the others). I will post my test results as a follow up to this. There are some surprises.

  9. 9. At 9:45 p.m. on 19 apr 2002, David Gould said:

    Performance surprises. I tested the various flavors of string reverse over the range of 10 to 100,000 character strings with 1 to 100,000 iterations.

    List comprehensions win. And there is some very odd behaviour for some of the others. Here is a summary of my observations:

    f0 = lambda s: s and f0(s[1:]) + s[0]

 recursive lambda   len(s)   iters   secs  ms/each  usec/chr
                       10   10000   0.38    0.038     3.815
                      100   10000   4.02    0.402     4.017
     maximum recursion depth exceeded at len 1000 count 1

    Ok, no suprise there.

    f1 = lambda s: reduce(lambda a,b: b+a, s, '')

  plus and reduce   len(s)   iters   secs  ms/each  usec/chr
                       10  100000   3.31    0.033     3.311
                      100  100000  28.72    0.287     2.872
                     1000    1000   3.05    3.049     3.049
                    10000     100   7.66   76.563     7.656
                   100000       1   9.13 9131.513    91.315

    Looks ok, except when the string gets large.

    f2 = lambda s, l=[]: (l.extend(s), l.reverse(), ''.join(l))[2]

transform to list   len(s)   iters   secs  ms/each  usec/chr
                       10      10   0.00    0.032     3.210
                       10     100   0.01    0.106    10.598
                       10    1000   0.89    0.886    88.625
                       10   10000 107.88   10.788  1078.757

                      100      10   0.20   20.260   202.599
                      100     100   2.19   21.888   218.880
                      100    1000  33.56   33.564   335.643

                     1000      10   0.43   43.131    43.131
                     1000     100   5.46   54.624    54.624

                    10000      10   0.76   76.485     7.648
                    10000     100  18.06  180.565    18.057

                   100000       1   0.32  322.159     3.222
                   100000      10   4.19  419.239     4.192

    Not only does it slow down as the strings get longer, but different iteration counts radically affect the timing in both absolute and per character terms. And not in a predictable way either, look at the 10 character string case which appears to be O(N*iterations) versus the 100 character string case which is O(N) but extremely slow anyway. Something there is that does not like a list... Also, this method seems to improve (relatively) as the string gets very large. Curiouser and curiouser.

    f3 = lambda s: ''.join([s[i] for i in xrange(len(s)-1, -1, -1)])

    (comment continued...)

  10. 10. At 9:45 p.m. on 19 apr 2002, David Gould said:

    (...continued from previous comment)

    list comprehension  len(s)   iters   secs  ms/each  usec/chr
                       10  100000   3.46    0.035     3.457
                      100  100000  17.71    0.177     1.771
                     1000   10000  15.99    1.599     1.599
                    10000    1000  16.01   16.007     1.601
                   100000     100  18.12  181.179     1.812

    This is twice as fast as any of the other methods and is also quite predictable, taking the same time per character no matter what length string or number of iterations. The alternative comprehension:

    f4 = lambda s: ''.join([s[-1 - i] for i in xrange(len(s))])

    was similar, but slightly slower.

    Here, for those who wish to play with it, or simply to laugh at my python style is the test program I used:

    import sys, time, gc

f0 = lambda s: s and f0(s[1:]) + s[0]
funs = (('recursive lambda', f0),
        ('plus and reduce',
          lambda s: reduce(lambda a,b: b+a, s, '')),
        ('transform to list',
          lambda s, l=[]: (l.extend(s), l.reverse(), ''.join(l))[2]),
        ('list comprehension',
          lambda s: ''.join([s[i] for i in xrange(len(s)-1, -1, -1)])),
        ('another lc',
          lambda s: ''.join([s[-1 - i] for i in xrange(len(s))])) )

hdr = '\n\n %20s   len(s)   iters   secs  ms/each  usec/chr'
fmt = '                       %6d  %6d %6.2f %8.3f  %8.3f'
strings = ['0123456789' * factor for factor in 1, 10, 100, 1000, 10000]

for title, fun in funs:
    print  hdr % (title,)
    skip = 0
    for s in strings:
        siz = len(s)
        for n in 1, 10, 100, 1000, 10000, 100000:
            gc.collect()
            t0 = time.time()
            try:
                for i in xrange(n):
                    fun(s)
                t = time.time() - t0
                print fmt % (siz, n, t, t*1000.0 / n, t*1000000.0 / (n*siz))
                if t > 3.0: break
            except RuntimeError:
                print sys.exc_type, sys.exc_value, 'at len', siz, 'count', n
                skip = 1
                break
        if skip or t > 3.0 and n I tested the various flavors of string reverse over the range
of 10 to 100,000 character strings with 1 to 100,000 iterations.


List comprehensions win. And there is some very odd behaviour for
some of the others. Here is a summary of my observations:


<pre>
f0 = lambda s: s and f0(s[1:]) + s[0]

 recursive lambda   len(s)   iters   secs  ms/each  usec/chr
                       10   10000   0.38    0.038     3.815
                      100   10000   4.02    0.402     4.017
     maximum recursion depth exceeded at len 1000 count 1

    Ok, no suprise there.

    f1 = lambda s: reduce(lambda a,b: b+a, s, '')

    (comment continued...)

  11. 11. At 9:45 p.m. on 19 apr 2002, David Gould said:

    (...continued from previous comment)

      plus and reduce   len(s)   iters   secs  ms/each  usec/chr
                       10  100000   3.31    0.033     3.311
                      100  100000  28.72    0.287     2.872
                     1000    1000   3.05    3.049     3.049
                    10000     100   7.66   76.563     7.656
                   100000       1   9.13 9131.513    91.315

    Looks ok, except when the string gets large.

    f2 = lambda s, l=[]: (l.extend(s), l.reverse(), ''.join(l))[2]

transform to list   len(s)   iters   secs  ms/each  usec/chr
                       10      10   0.00    0.032     3.210
                       10     100   0.01    0.106    10.598
                       10    1000   0.89    0.886    88.625
                       10   10000 107.88   10.788  1078.757

                      100      10   0.20   20.260   202.599
                      100     100   2.19   21.888   218.880
                      100    1000  33.56   33.564   335.643

                     1000      10   0.43   43.131    43.131
                     1000     100   5.46   54.624    54.624

                    10000      10   0.76   76.485     7.648
                    10000     100  18.06  180.565    18.057

                   100000       1   0.32  322.159     3.222
                   100000      10   4.19  419.239     4.192

    Not only does it slow down as the strings get longer, but different iteration counts radically affect the timing in both absolute and per character terms. And not in a predictable way either, look at the 10 character string case which appears to be O(N*iterations) versus the 100 character string case which is O(N) but extremely slow anyway. Something there is that does not like a list... Also, this method seems to improve (relatively) as the string gets very large. Curiouser and curiouser.

    f3 = lambda s: ''.join([s[i] for i in xrange(len(s)-1, -1, -1)])

list comprehension  len(s)   iters   secs  ms/each  usec/chr
                       10  100000   3.46    0.035     3.457
                      100  100000  17.71    0.177     1.771
                     1000   10000  15.99    1.599     1.599
                    10000    1000  16.01   16.007     1.601
                   100000     100  18.12  181.179     1.812

    This is twice as fast as any of the other methods and is also quite predictable, taking the same time per character no matter what length string or number of iterations. The alternative comprehension: <pre> f4 = lambda s: ''.join([s[-1 - i] for i in xrange(len(s))])

  12. 12. At 9:48 p.m. on 19 apr 2002, David Gould said:

    Eeeh... I don't know why the add comment procedure insisted on having an extra copy of my post, but it did, I previewed it many times and could never get rid of it...

    sigh...

  13. 13. At 3:41 a.m. on 8 may 2002, anurag uniyal (the author) said:

    Corrected version is fastest :). See the code above! I have changed third lambda slightly due to some feature of Python which I fail to understand!

  14. 14. At 5:21 a.m. on 14 aug 2003, j k said:

    f=lambda s:(lambda a:a.reverse()or a.tostring())(__import__('array').array('c', s))

  15. 15. At 12:25 a.m. on 23 dec 2003, Alexander Brück said:

    Python 2.3. This recipe is out of date since Python 2.3.

    Now you should simply use

    reversed_string = s[::-1]

    It is much simpler and faster than all solutions mentioned above.

Sign in to comment