Number of distinct substrings of a string [continuation]

Bearophile bearophileHUGS at lycos.com
Sun Nov 29 14:12:07 CET 2009


n00m:
> My Py solution:
> ...

Cute. You can replace:
a[ord(s[i])] += [i]
With:
a[ord(s[i])].append(i)

If you want to micro-optimize this with Psyco may be a little faster:
(lev >> 1)
Than:
lev // 2

But to increase speed it's usually better to reduce memory
allocations. So you can try to find a way to pull this out of the
function:
a = [[] for i in xrange(128)]
And to avoid a true append:
a[ord(s[i])] += [i]

(There are many ways to avoid an append. One of them is to have an
already allocated list/array and just bump forward an index variable
that starts from 0. This is worth doing especially when you use
Psyco).

Bye,
bearophile



More information about the Python-list mailing list