Python speed-up

[Alex Martelli]

Guyon Morée <gumuz at NO_looze_SPAM.net> wrote:
   ...
> I hope someone can tell me why these are slow.

I see many others have offered excellent answers: they all boil down
to...:

"Strings are immutable; each time you code
    astring = <some operation on> astring
you're making a new string object (and throwing away the old one, unless
it's also known by other names), including the times in which you spell
this as:
    astring <someop>= whatever
which, since astring is immutable, is only a shortcut for the former."

Putting together a big string with a loop of 'bigstring+=piece' is
perhaps the best-known performance trap in Python.  Python 2.4 has
turned somersaults to lessen the penalty you pay for this, but it's
still pretty slow compared to "accumulate pieces in a list, ''.join the
list when it's done".  There's really nothing better than this _in
general_.  For your specific case, since you know in advance how long
you want the resulting sequence to be, you have options: make
encoded_text a list of the same length as it will be at the end, and
loop filling it.  In other words, you might be able to shave a little
time by coding, for example:

encoded_text = list(original_text)
for i, c in enumerate(encoded_text):
    encoded_text[i] = table[c]

another possibility that might turn out to be faster (particularly in
2.4) is:

encoded_text = map(table.__getitem__, original_text)

or similarly, in 2.3, with table.get (table.__getitem__ is slower than
it should be in 2.3... fortunately 2.4 has fixed that issue).  I'm not
sure which of these options will be faster: time them with timeit.py,
that's what it's _there_ for!-).  Anyway, encoded_text will end up as a
list, so you'll ''.join it when you're done.

"consuming a string a piece at a time from the front" is a lesser-known
trap -- interestingly, it would apply to lists as well, for different
reasons (namely, that a list is a compact array in memory, so removing
some stuff from the front requires "sliding down" all of the rest, an
operation taking time proportional to the sequence length, O(N) in
common parlance -- consuming a whole sequence that way is therefore O(N
squared), i.e., pretty bad).  The list-comprehension-of-slices solution
I've seen more than one responder propose is in fact quite a good one
(it's O(1) per step, O(N) for the whole 'consumption' operation).

You might also consider whether you want encoded_text to be a string at
all, rather than a list or array.array of 1's and 0's.  If the latter,
then 'encoded_text.extend(table[c])' as the first loop's body would do
it -- and you could make the values of table into tuples of numbers,
rather than strings, optionally.


Alex