in-place string reversal

S

Sathyaish

How would you reverse a string "in place" in python? I am seeing that
there are a lot of operations around higher level data structures and
less emphasis on primitive data. I am a little lost and can't find my
way through seeing a rev() or a reverse() or a strRev() function around
a string object.

I could traverse from end-to-beginning by using extra memory:

strText = "foo"
strTemp = ""
for chr in strText:
strTemp = chr + strTemp


but how would I do it in place?


Forget it! I got the answer to my own question. Strings are immutable,
*even* in python. Why not! The python compiler is written in C, right?
It is amazing how just writing down your problem can give you a
solution.


PS: Or, if my assumption that strings are immutable and an in-place
reversal is possible, is wrong, please correct me.
 
S

Sathyaish

And that the "extra-memory" operation I've given above is expensive, I
believe. Is there an efficient way to do it?
 
S

Sybren Stuvel

Sathyaish enlightened us with:
How would you reverse a string "in place" in python?

You wouldn't, since strings are immutable.
Forget it! I got the answer to my own question. Strings are
immutable, *even* in python.

Indeed :)
Why not! The python compiler is written in C, right?

Yup. But what's got that to do with it? Strings are very mutable in C.
It is amazing how just writing down your problem can give you a
solution.

:)

Sybren
 
S

Sathyaish

But what's got that to do with it? Strings are very mutable in C.

I realized after posting that I'd said something incorrect again. The
concept of "mutability" itself is a high-level concept compared to C.
Memory allocation for strings is expensive because of the way malloc()
works to find a "best-fit" against a "first-fit" in traditional memory
management systems. Because of the performance hit, high level
languages and frameworks, such as the Common Type System of the .NET
Framework for example, considers strings as immutable. That, unlike
Python, doesn't however, make them impossible to modify in-place.
 
S

Sion Arrowsmith

Sathyaish said:
How would you reverse a string "in place" in python?
[ ... ]
Forget it! I got the answer to my own question. Strings are immutable,
*even* in python.

I'm not sure what that "*even*" is about, but glad that "You can't,
strings are immutable" is a satisfactory answer. Rather than writing
your own reversing code, you might like to look at:
 
Y

Yu-Xi Lim

Sathyaish said:
I realized after posting that I'd said something incorrect again. The
concept of "mutability" itself is a high-level concept compared to C.
Memory allocation for strings is expensive because of the way malloc()
works to find a "best-fit" against a "first-fit" in traditional memory
management systems. Because of the performance hit, high level
languages and frameworks, such as the Common Type System of the .NET
Framework for example, considers strings as immutable. That, unlike
Python, doesn't however, make them impossible to modify in-place.

I believe part of the reason for their immutability is so that they can
be used as dictionary keys, which is a very common use.
 
F

Felipe Almeida Lessa

Em Ter, 2006-03-28 às 16:03 +0100, Sion Arrowsmith escreveu:
Rather than writing
your own reversing code, you might like to look at:

Or not:

----
$ python2.4
Python 2.4.2 (#2, Nov 20 2005, 17:04:48)
[GCC 4.0.3 20051111 (prerelease) (Debian 4.0.2-4)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
"".join(reversed("foo")) 'oof'
"foo"[::-1]
'oof'

$ python2.4 -mtimeit '"".join(reversed("foo"))'
100000 loops, best of 3: 2.58 usec per loop

$ python2.4 -mtimeit '"foo"[::-1]'
1000000 loops, best of 3: 0.516 usec per loop

$ calc 2.58/0.516
5
 
A

Adam DePrince

And that the "extra-memory" operation I've given above is expensive, I
believe. Is there an efficient way to do it?

How big is your string?

For short strings (i.e. where large means you don't have enough RAM to
hold one extra copy.)


Also, anytime you reach for a for-loop to build a string step by step,
you are making a mistake. Consider your example.

strText = "foo"
strTemp = ""
for chr in strText:
strTemp = chr + strTemp

Each loop you are copying the string again, the timing behavior of your
function is O(n^2).

If you are really concerned about memory allocation, well, I don't know
if you realize this, but every time you call

strTemp = chr + strTemp

you are throwing away your old copy and building a new copy. Ouch.

Forgive me for preaching, but you just committed the grievous act of
premature optimization. Don't worry about that first malloc, if Python
is going to call malloc, it has a lot of opportunity to do so later.
And malloc isn't as evil as you make it out to be.

One of the advantages of using a high level language is you get to leave
the issue of how to implement the small stuff up to the language
designer and focus on the bigger picture - algorithmic appropriateness
and overall correctness.

In my experience I've found that when under time pressure python
programs tend to out perform C because doing it right is so much easier
in the former.

As for mutability, immutability is a big virtue and performance gain.
If I have two pointers to immutable strings, once I compare them I can
know for eternity which is larger, so long as I don't let go of my
references to them. Thus I can use them as keys in a complicated and
efficient data structure. If Python strings were mutable the best
implementation we could hope for dict would be a linked list.

Also, consider some other side effects of mutable strings.

s = "Abc"
myfancy_structre.add_somehow( s )
t = s[::-1]
print s Abc
print t
cbA

Now if strings were mutable:
cbA

Other users of s between assignment and reversal (like
myfancy_structure) might not be happy that is was reversed when they
next must use it.

Cheers - Adam DePrince
 
S

Sion Arrowsmith

Felipe Almeida Lessa said:
Em Ter, 2006-03-28 às 16:03 +0100, Sion Arrowsmith escreveu:
$ python2.4 -mtimeit '"".join(reversed("foo"))'
100000 loops, best of 3: 2.58 usec per loop

But note that a significant chunk is the join():

$ python2.4 -mtimeit '"".join(reversed("foo"))'
100000 loops, best of 3: 2.72 usec per loop
$ python2.4 -mtimeit 'reversed("foo")'
1000000 loops, best of 3: 1.69 usec per loop
$ python2.4 -mtimeit '"foo"[::-1]'
1000000 loops, best of 3: 0.516 usec per loop

Yeah, I forget about [::-1] due to the high profile of the introduction
of reversed(). Well, of sorted(), and reversed() coming along for the
ride. And at some point reversed() will become a win:

$ python2.4 -mtimeit 'reversed(range(200))'
100000 loops, best of 3: 6.65 usec per loop
$ python2.4 -mtimeit 'range(200)[::-1]'
100000 loops, best of 3: 6.88 usec per loop
 
O

olsongt

Sathyaish said:
How would you reverse a string "in place" in python? I am seeing that
there are a lot of operations around higher level data structures and
less emphasis on primitive data. I am a little lost and can't find my
way through seeing a rev() or a reverse() or a strRev() function around
a string object.

I could traverse from end-to-beginning by using extra memory:

strText = "foo"
strTemp = ""
for chr in strText:
strTemp = chr + strTemp


but how would I do it in place?


Forget it! I got the answer to my own question. Strings are immutable,
*even* in python. Why not! The python compiler is written in C, right?
It is amazing how just writing down your problem can give you a
solution.


PS: Or, if my assumption that strings are immutable and an in-place
reversal is possible, is wrong, please correct me.

If you are using strings that are long enough where you're going to run
into memory issues, you can create a character array from the array
module. This will basically create a mutable string.
 
F

Fredrik Lundh

Sion said:
But note that a significant chunk is the join():

$ python2.4 -mtimeit '"".join(reversed("foo"))'
100000 loops, best of 3: 2.72 usec per loop
$ python2.4 -mtimeit 'reversed("foo")'
1000000 loops, best of 3: 1.69 usec per loop

your second benchmark doesn't do any reversal, though. it only
creates a bunch of reversed() iterator objects.

it's a little like my old faster-than-the-speed-of-light XML parser
benchmark:
dir test.xml
....
2005-05-04 20:41 12 658 399 test.xml
....
python -m timeit -s "import cElementTree" "matches = (elem.get('value')
for event, elem in cElementTree.iterparse('test.xml') if elem.get('name')
== 'reselectApi')"
1000 loops, best of 3: 198 usec per loop
python -c "print 12658399 / 198e-6"
63931308080.8

(64 gigabytes per second? who said XML was a performance hog ?)

</F>
 
F

Felipe Almeida Lessa

Em Ter, 2006-03-28 às 17:32 +0100, Sion Arrowsmith escreveu:
ride. And at some point reversed() will become a win:

$ python2.4 -mtimeit 'reversed(range(200))'
100000 loops, best of 3: 6.65 usec per loop
$ python2.4 -mtimeit 'range(200)[::-1]'
100000 loops, best of 3: 6.88 usec per loop

Not fair:

$ python2.4
Python 2.4.2 (#2, Nov 20 2005, 17:04:48)
[GCC 4.0.3 20051111 (prerelease) (Debian 4.0.2-4)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
range(200)[::-1] [199, 198, ..., 1, 0]
reversed(range(200))
list(reversed(range(200))) [199, 198, ..., 1, 0]
list(reversed(range(200))) == range(200)[::-1] True
^D

Now we're in a fair competition:
$ python2.4 -mtimeit -s 'a=range(200)' 'a[::-1]'
100000 loops, best of 3: 2.23 usec per loop
$ python2.4 -mtimeit -s 'a=range(200)' 'list(reversed(a))'
100000 loops, best of 3: 5.62 usec per loop
$ calc 5.62/2.23
~2.52017937219730941704
$ python2.4 -mtimeit -s 'a=range(200000)' 'a[::-1]'
100 loops, best of 3: 10.7 msec per loop
$ python2.4 -mtimeit -s 'a=range(200000)' 'list(reversed(a))'
100 loops, best of 3: 11.5 msec per loop
$ calc 11.5/10.7
~1.07476635514018691589

But:
$ python2.4 -mtimeit 'range(199, -1, -1)'
100000 loops, best of 3: 4.8 usec per loop
$ python2.4 -mtimeit 'range(200)[::-1]'
100000 loops, best of 3: 7.05 usec per loop
$ calc 7.05/4.8
1.46875
$ python2.4 -mtimeit 'range(199999, -1, -1)'
100 loops, best of 3: 13.7 msec per loop
$ python2.4 -mtimeit 'range(200000)[::-1]'
10 loops, best of 3: 24 msec per loop
$ calc 24/13.7
~1.75182481751824817518

And worse:
$ python2.4 -mtimeit 'list(reversed(range(200)))'
100000 loops, best of 3: 10.5 usec per loop
$ calc 10.5/4.8
2.1875
$ python2.4 -mtimeit 'list(reversed(range(200000)))'
10 loops, best of 3: 24.5 msec per loop
$ calc 24.5/13.7
~1.78832116788321167883


HTH,
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,479
Members
44,899
Latest member
RodneyMcAu

Latest Threads

Top