reverse a string (Python recipe) by anurag uniyal

ActiveState Code (http://code.activestate.com/recipes/119029/)

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.

how about.

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

not really a one liner ;)

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

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 :)

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 :-)

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 :-)

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

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.

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...)

(...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...)

(...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))])

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...

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!

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

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.