in-place string reversal

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

[Sathyaish]

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

[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
--
The problem with the world is stupidity. Not saying there should be a
capital punishment for stupidity, but why don't we just take the
safety labels off of everything and let the problem solve itself?
Frank Zappa

[Martin P. Hellwig]

Sathyaish wrote:

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

If i recall correctly a string is an immutable list.
I would do it this way:

strTXT = "foo"
strREV = strTXT[::-1]
strREV

'oof'

--
mph

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

[Sion Arrowsmith]

Sathyaish <sa*******@gmail.com> wrote:

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:

"".join(reversed("foo"))

--
\S -- si***@chiark.greenend.org.uk -- http://www.chaos.org.uk/~sion/
___ | "Frankly I have no feelings towards penguins one way or the other"
\X/ | -- Arthur C. Clarke
her nu becomeþ se bera eadward ofdun hlæddre heafdes bæce bump bump bump

[Yu-Xi Lim]

Sathyaish wrote:

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.

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.

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

"".join(reversed("foo"))
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
----

"foo"[::-1] is cleaner and performs 5 times better -- 'nuff said.

Cheers,

--
Felipe.

[Adam DePrince]

On Tue, 2006-03-28 at 06:15 -0800, Sathyaish wrote:

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

"Abc"[::-1] 'cbA'

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:
s = "Abc"
myfancy_structre.add_somehow( s )
s.reverseme()
print s

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

[Sion Arrowsmith]

Felipe Almeida Lessa <fe**********@gmail.com> wrote:

Em Ter, 2006-03-28 Ã*s 16:03 +0100, Sion Arrowsmith escreveu:

>>> "".join(reversed("foo"))

$ 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

--
\S -- si***@chiark.greenend.org.uk -- http://www.chaos.org.uk/~sion/
___ | "Frankly I have no feelings towards penguins one way or the other"
\X/ | -- Arthur C. Clarke
her nu becomeþ se bera eadward ofdun hlæddre heafdes bæce bump bump bump

[olsongt]

Sathyaish wrote:

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.

[Fredrik Lundh]

Sion Arrowsmith wrote:

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>

[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)) <listreverseiterator object at 0xb7d1224c> 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,

--
Felipe.