Re: in-place string reversal

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
Received on Sun Apr 30 21:25:50 2006