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]

Re: in-place string reversal

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

[Sybren Stuvel]

Re: in-place string reversal

Sathyaish enlightened us with:[color=blue]
> How would you reverse a string "in place" in python?[/color]

You wouldn't, since strings are immutable.
[color=blue]
> Forget it! I got the answer to my own question. Strings are
> immutable, *even* in python.[/color]

Indeed :)
[color=blue]
> Why not! The python compiler is written in C, right?[/color]

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

:)

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]

Re: in-place string reversal

Sathyaish wrote:[color=blue]
> And that the "extra-memory" operation I've given above is expensive, I
> believe. Is there an efficient way to do it?
>[/color]
If i recall correctly a string is an immutable list.
I would do it this way:[color=blue][color=green][color=darkred]
>>> strTXT = "foo"
>>> strREV = strTXT[::-1]
>>> strREV[/color][/color][/color]
'oof'

--
mph

[Sathyaish]

Re: in-place string reversal

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

Re: in-place string reversal

Sathyaish <sathyaish@gmai l.com> wrote:[color=blue]
>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.[/color]

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:
[color=blue][color=green][color=darkred]
>>> "".join(reverse d("foo"))[/color][/color][/color]

--
\S -- siona@chiark.gr eenend.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]

Re: in-place string reversal

Sathyaish wrote:[color=blue][color=green]
>> But what's got that to do with it? Strings are very mutable in C.[/color]
>
> 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.
>[/color]

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]

Re: in-place string reversal

Em Ter, 2006-03-28 às 16:03 +0100, Sion Arrowsmith escreveu:[color=blue]
> Rather than writing
> your own reversing code, you might like to look at:
>[color=green][color=darkred]
> >>> "".join(reverse d("foo"))[/color][/color][/color]

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.[color=blue][color=green][color=darkred]
>>> "".join(reverse d("foo"))[/color][/color][/color]
'oof'[color=blue][color=green][color=darkred]
>>> "foo"[::-1][/color][/color][/color]
'oof'

$ python2.4 -mtimeit '"".join(revers ed("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]

Re: in-place string reversal

On Tue, 2006-03-28 at 06:15 -0800, Sathyaish wrote:[color=blue]
> And that the "extra-memory" operation I've given above is expensive, I
> believe. Is there an efficient way to do it?
>[/color]

How big is your string?

For short strings (i.e. where large means you don't have enough RAM to
hold one extra copy.)
[color=blue][color=green][color=darkred]
>>> "Abc"[::-1][/color][/color][/color]
'cbA'[color=blue][color=green][color=darkred]
>>>[/color][/color][/color]


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.

[color=blue][color=green]
>> s = "Abc"
>> myfancy_structr e.add_somehow( s )
>> t = s[::-1]
>> print s[/color][/color]
Abc[color=blue][color=green]
>> print t[/color][/color]
cbA

Now if strings were mutable:
[color=blue][color=green]
>> s = "Abc"
>> myfancy_structr e.add_somehow( s )
>> s.reverseme()
>> print s[/color][/color]
cbA

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

Cheers - Adam DePrince

[Sion Arrowsmith]

Re: in-place string reversal

Felipe Almeida Lessa <felipe.lessa@g mail.com> wrote:[color=blue]
>Em Ter, 2006-03-28 às 16:03 +0100, Sion Arrowsmith escreveu:[color=green][color=darkred]
>> >>> "".join(reverse d("foo"))[/color][/color]
>$ python2.4 -mtimeit '"".join(revers ed("foo"))'
>100000 loops, best of 3: 2.58 usec per loop[/color]

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

$ python2.4 -mtimeit '"".join(revers ed("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
[color=blue]
>$ python2.4 -mtimeit '"foo"[::-1]'
>1000000 loops, best of 3: 0.516 usec per loop[/color]

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 -- siona@chiark.gr eenend.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@verizon.net]

Re: in-place string reversal


Sathyaish wrote:[color=blue]
> 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.[/color]

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]

Re: in-place string reversal

Sion Arrowsmith wrote:
[color=blue]
> But note that a significant chunk is the join():
>
> $ python2.4 -mtimeit '"".join(revers ed("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[/color]

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:
[color=blue]
> dir test.xml[/color]
....
2005-05-04 20:41 12 658 399 test.xml
....[color=blue]
> python -m timeit -s "import cElementTree" "matches = (elem.get('valu e')[/color]
for event, elem in cElementTree.it erparse('test.x ml') if elem.get('name' )
== 'reselectApi')"
1000 loops, best of 3: 198 usec per loop[color=blue]
> python -c "print 12658399 / 198e-6"[/color]
63931308080.8

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

</F>

[Felipe Almeida Lessa]

Re: in-place string reversal

Em Ter, 2006-03-28 às 17:32 +0100, Sion Arrowsmith escreveu:[color=blue]
> 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[/color]

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.[color=blue][color=green][color=darkred]
>>> range(200)[::-1][/color][/color][/color]
[199, 198, ..., 1, 0][color=blue][color=green][color=darkred]
>>> reversed(range( 200))[/color][/color][/color]
<listreverseite rator object at 0xb7d1224c>[color=blue][color=green][color=darkred]
>>> list(reversed(r ange(200)))[/color][/color][/color]
[199, 198, ..., 1, 0][color=blue][color=green][color=darkred]
>>> list(reversed(r ange(200))) == range(200)[::-1][/color][/color][/color]
True[color=blue][color=green][color=darkred]
>>>^D[/color][/color][/color]

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.520179372197 30941704
$ 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.074766355140 18691589

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

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


HTH,

--
Felipe.