code for Computer Language Shootout

[Jacob Lee]

There are a bunch of new tests up at shootout.alioth .debian.org for which
Python does not yet have code. I've taken a crack at one of them, a task
to print the reverse complement of a gene transcription. Since there are a
lot of minds on this newsgroup that are much better at optimization than
I, I'm posting the code I came up with to see if anyone sees any
opportunities for substantial improvement. Without further ado:

table = string.maketran s('ACBDGHK\nMNS RUTWVY', 'TGVHCDM\nKNSYA AWBR')

def show(s):
i = 0
for char in s.upper().trans late(table)[::-1]:
if i == 60:
print
i = 0
sys.stdout.writ e(char)
i += 1
print

def main():
seq = ''
for line in sys.stdin:
if line[0] == '>' or line[0] == ';':
if seq != '':
show(seq)
seq = ''
print line,
else:
seq += line[:-1]
show(seq)

main()


Making seq into a list instead of a string (and using .extend instead of
the + operator) didn't give any speed improvements. Neither did using a
dictionary instead of the translate function, or using reversed() instead
of s[::-1]. The latter surprised me, since I would have guessed using an
iterator to be more efficient. Since the shootout also tests memory usage,
should I be using reversed for that reason? Does anyone have any other
ideas to optimize this code?

By the way - is there a good way to find out the maximum memory a program
used (in the manner of the "time" command)? Other than downloading and
running the shootout benchmark scripts, of course.

--
Jacob Lee
jelee2@uiuc.edu | www.nearestneighbor.net

[Robert Kern]

Re: code for Computer Language Shootout

Jacob Lee wrote:
[color=blue]
> By the way - is there a good way to find out the maximum memory a program
> used (in the manner of the "time" command)? Other than downloading and
> running the shootout benchmark scripts, of course.[/color]

Inserting appropriate pauses with raw_input() and recording the memory
usage using top(1) is a quick and dirty way.

--
Robert Kern
rkern@ucsd.edu

"In the fields of hell where the grass grows high
Are the graves of dreams allowed to die."
-- Richard Harter

[Robert Kern]

Re: code for Computer Language Shootout

Here's my solution to the problem[1]:

[1] http://shootout.alioth.debian.org/be...p?test=revcomp

import sys
import string

basetable = string.maketran s('ACBDGHKMNSRU TWVYacbdghkmnsr utwvy',
'TGVHCDMKNSYAAW BRTGVHCDMKNSYAA WBR')
def revcomp(seqline s, linelength=60, basetable=baset able):
seq = ''.join(seqline s)
complement = seq.translate(b asetable)
revcomplement = complement[::-1]
for i in xrange(0, len(revcompleme nt), linelength):
print revcomplement[i:i+linelength]

def main():
seqlines = []
for line in sys.stdin:
if line.startswith ('>') or line.startswith (';'):
if seqlines:
revcomp(seqline s)
sys.stdout.writ e(line)
seqlines = []
else:
seqlines.append (line.strip())
revcomp(seqline s)

if __name__ == '__main__':
main()

--
Robert Kern
rkern@ucsd.edu

"In the fields of hell where the grass grows high
Are the graves of dreams allowed to die."
-- Richard Harter

[Michael Spencer]

Re: code for Computer Language Shootout

Jacob Lee wrote:[color=blue]
> There are a bunch of new tests up at shootout.alioth .debian.org for which
> Python does not yet have code. I've taken a crack at one of them, a task
> to print the reverse complement of a gene transcription. Since there are a
> lot of minds on this newsgroup that are much better at optimization than
> I, I'm posting the code I came up with to see if anyone sees any
> opportunities for substantial improvement. Without further ado:
>
> table = string.maketran s('ACBDGHK\nMNS RUTWVY', 'TGVHCDM\nKNSYA AWBR')
>[/color]
string.translat e is a good idea. Note you can handle upper-casing and
translation in one operation by adding a mapping from lower case to the
complement i.e.,

table = string.maketran s('ACBDGHK\nMNS RUTWVYacbdghkmn srutwvy',
'TGVHCDM\nKNSYA AWBRTGVHCDMKNSY AAWBR')
[color=blue]
> def show(s):
> i = 0
> for char in s.upper().trans late(table)[::-1]:[/color]

[color=blue]
> if i == 60:
> print
> i = 0
> sys.stdout.writ e(char)
> i += 1
> print[/color]

[color=blue]
> def main():
> seq = ''
> for line in sys.stdin:
> if line[0] == '>' or line[0] == ';':
> if seq != '':
> show(seq)
> seq = ''
> print line,
> else:
> seq += line[:-1]
> show(seq)
>
> main()
>[/color]

This looks unwieldy - especially writing to sys.stdout oe character at a time.
I may not have understood the spec exactly, but isn't this the same as:

for line in sys.stdin:
if line and (line[0] == ">" or line[0] == ";"):
print line
else:
print line.translate( table)

HTH

Michael

[Steven Bethard]

Re: code for Computer Language Shootout

Jacob Lee wrote:[color=blue]
> There are a bunch of new tests up at shootout.alioth .debian.org for which
> Python does not yet have code. I've taken a crack at one of them, a task
> to print the reverse complement of a gene transcription. Since there are a
> lot of minds on this newsgroup that are much better at optimization than
> I, I'm posting the code I came up with to see if anyone sees any
> opportunities for substantial improvement. Without further ado:
>
> table = string.maketran s('ACBDGHK\nMNS RUTWVY', 'TGVHCDM\nKNSYA AWBR')
>
> def show(s):
> i = 0
> for char in s.upper().trans late(table)[::-1]:
> if i == 60:
> print
> i = 0
> sys.stdout.writ e(char)
> i += 1
> print
>
> def main():
> seq = ''
> for line in sys.stdin:
> if line[0] == '>' or line[0] == ';':
> if seq != '':
> show(seq)
> seq = ''
> print line,
> else:
> seq += line[:-1]
> show(seq)
>
> main()[/color]

Don't know if this is faster for your data, but I think you could also
write this as (untested):

# table as default argument value so you don't have to do
# a global lookup each time it's used

def show(seq, table=string.ma ketrans('ACBDGH K\nMNSRUTWVY',
'TGVHCDM\nKNSYA AWBR')
seq = seq.upper().tra nslate(table)[::-1]
# print string in slices of length 60
for i in range(0, len(seq), 60):
print seq[i:i+60]

def main():
seq = []
# alias methods to avoid repeated lookup
join = ''.join
append = seq.append
for line in sys.stdin:
# note only one "line[0]" by using "in" test
if line[0] in ';>':
# note no need to check if seq is empty; show now prints
# nothing for an empty string
show(join(seq))
print line,
del seq[:]
else:
append(line[:-1])

[color=blue]
> Making seq into a list instead of a string (and using .extend instead of
> the + operator) didn't give any speed improvements. Neither did using a
> dictionary instead of the translate function, or using reversed() instead
> of s[::-1]. The latter surprised me, since I would have guessed using an
> iterator to be more efficient. Since the shootout also tests memory usage,
> should I be using reversed for that reason?[/color]

reversed() won't save you any memory -- you're already loading the
entire string into memory anyway.


Interesting tidbit:
del seq[:]
tests faster than
seq = []

$ python -m timeit -s "lst = range(1000)" "lst = []"
10000000 loops, best of 3: 0.159 usec per loop

$ python -m timeit -s "lst = range(1000)" "del lst[:]"
10000000 loops, best of 3: 0.134 usec per loop

It's probably the right way to go in this case anyway -- no need to
create a new empty list each time.

STeVe

[Jacob Lee]

Re: code for Computer Language Shootout

On Tue, 15 Mar 2005 21:38:48 -0800, Michael Spencer wrote:
[color=blue]
> string.translat e is a good idea. Note you can handle upper-casing and
> translation in one operation by adding a mapping from lower case to the
> complement i.e.,
>
> table = string.maketran s('ACBDGHK\nMNS RUTWVYacbdghkmn srutwvy',
> 'TGVHCDM\nKNSYA AWBRTGVHCDMKNSY AAWBR')
>[/color]
Good call.
[color=blue]
> This looks unwieldy - especially writing to sys.stdout oe character at a
> time. I may not have understood the spec exactly, but isn't this the
> same as:
>
> for line in sys.stdin:
> if line and (line[0] == ">" or line[0] == ";"):
> print line
> else:
> print line.translate( table)
>
>[/color]
That's the immediately obvious solution, but it doesn't actually fulfill
the problem requirements. What if your last line is less than 60
characters long? You no longer will be displaying the input in reverse
order. Otherwise you'd be right - my solution would be unnecessarily
unwieldy (and the problem would be much simpler...) .

--
Jacob Lee
jelee2@uiuc.edu | www.nearestneighbor.net

[Jacob Lee]

Re: code for Computer Language Shootout

On Tue, 15 Mar 2005 22:45:48 -0700, Steven Bethard wrote:
[color=blue]
> # table as default argument value so you don't have to do
> # a global lookup each time it's used
>
> def show(seq, table=string.ma ketrans('ACBDGH K\nMNSRUTWVY',
> 'TGVHCDM\nKNSYA AWBR')
> seq = seq.upper().tra nslate(table)[::-1]
> # print string in slices of length 60
> for i in range(0, len(seq), 60):
> print seq[i:i+60]
>
> def main():
> seq = []
> # alias methods to avoid repeated lookup
> join = ''.join
> append = seq.append
> for line in sys.stdin:
> # note only one "line[0]" by using "in" test
> if line[0] in ';>':
> # note no need to check if seq is empty; show now prints
> # nothing for an empty string
> show(join(seq))
> print line,
> del seq[:]
> else:
> append(line[:-1])
>[/color]

Wow - that ran about 10 times faster on a 10MB input file. The significant
change was the for loop inside the show function: your method avoids the
increment and if statement and of course has 60x fewer iterations total.
[color=blue]
> reversed() won't save you any memory -- you're already loading the
> entire string into memory anyway.
>
>
> Interesting tidbit:
> del seq[:]
> tests faster than
> seq = []
>
> $ python -m timeit -s "lst = range(1000)" "lst = []"
> 10000000 loops, best of 3: 0.159 usec per loop
>
> $ python -m timeit -s "lst = range(1000)" "del lst[:]"
> 10000000 loops, best of 3: 0.134 usec per loop
>
> It's probably the right way to go in this case anyway -- no need to
> create a new empty list each time.[/color]

Fascinating - I hadn't thought about that.

Besides redoing that loop, the remaining optimizations produce less than a
10% speed-up; in particular, adding the function aliases increases the
number of lines of code (another benchmark in the shootout), and I would
imagine that the organizers don't really want that type of special
optimization (no developer is going to write that in their programs
unless they have really time-critical code, so this is the sort of hit
that Python really should take in the contest as penalty for being so
dynamically nifty ;)). So here's a tentative contest version of the code:

import sys
import string

def show(seq, table=string.ma ketrans('ACBDGH K\nMNSRUTWVYacb dghkmnsrutwvy',
'TGVHCDM\nKNSYA AWBRTGVHCDMKNSY AAWBR')):
seq = seq.translate(t able)[::-1]
for i in range(0, len(seq), 60):
print seq[i:i+60]

def main():
seq = []
for line in sys.stdin:
if line[0] in ';>':
show(''.join(se q))
print line,
del seq[:]
else:
seq.append(line[:-1])
show(''.join(se q))

main()

--
Jacob Lee
jelee2@uiuc.edu | www.nearestneighbor.net

[Steven Bethard]

Re: code for Computer Language Shootout

Jacob Lee wrote:[color=blue]
> So here's a tentative contest version of the code:
>
> import sys
> import string
>
> def show(seq, table=string.ma ketrans('ACBDGH K\nMNSRUTWVYacb dghkmnsrutwvy',
> 'TGVHCDM\nKNSYA AWBRTGVHCDMKNSY AAWBR')):
> seq = seq.translate(t able)[::-1]
> for i in range(0, len(seq), 60):
> print seq[i:i+60]
>
> def main():
> seq = []
> for line in sys.stdin:
> if line[0] in ';>':
> show(''.join(se q))
> print line,
> del seq[:]
> else:
> seq.append(line[:-1])
> show(''.join(se q))
>
> main()[/color]

Looks pretty good. (And yes, I definitely prefer the unaliased ''.join
and seq.append for readability's sake. Glad to know they try to grade
on that too.) =)

Only one other suggestion: "range" in the show function should probably
be "xrange". "range" is going to create an actual list of however many
integers, while "xrange" will just create the integers as needed.
"xrange" thus will be more memory friendly. (It's also occasionally
faster, though this depends a lot on the rest of the code).

STeVe

[Michael Spencer]

Re: code for Computer Language Shootout

Jacob Lee wrote:[color=blue]
> On Tue, 15 Mar 2005 21:38:48 -0800, Michael Spencer wrote:
>
>[color=green]
>>string.transl ate is a good idea. Note you can handle upper-casing and
>>translation in one operation by adding a mapping from lower case to the
>>complement i.e.,
>>
>>table = string.maketran s('ACBDGHK\nMNS RUTWVYacbdghkmn srutwvy',
>> 'TGVHCDM\nKNSYA AWBRTGVHCDMKNSY AAWBR')
>>[/color]
>
> Good call.
>
>[color=green]
>>This looks unwieldy - especially writing to sys.stdout oe character at a
>>time. I may not have understood the spec exactly, but isn't this the
>>same as:
>>
>>for line in sys.stdin:
>> if line and (line[0] == ">" or line[0] == ";"):
>> print line
>> else:
>> print line.translate( table)
>>
>>[/color]
>
> That's the immediately obvious solution, but it doesn't actually fulfill
> the problem requirements. What if your last line is less than 60
> characters long? You no longer will be displaying the input in reverse
> order. Otherwise you'd be right - my solution would be unnecessarily
> unwieldy (and the problem would be much simpler...) .
>[/color]
yes it would be, wouldn't it ;-)

How about this then:

basetable = string.maketran s('ACBDGHKMNSRU TWVYacbdghkmnsr utwvy',
'TGVHCDMKNSYAAW BRTGVHCDMKNSYAA WBR')

from collections import deque
from itertools import islice

def output(seq, linelength = 60):
if seq:
iterseq = iter(seq)
while iterseq:
print "".join(islice( iterseq,linelen gth))

def revcomp(input = sys.stdin):
seqlines = deque()
for line in input:
if line[0] in ">;":
output(seqlines )
print line,
seqlines.clear( )
else:
seqlines.extend left(line.trans late(basetable, "\n\r"))
output(seqlines )


It would be nice to inline the output function, and re-arrange the iteration so
that EOF triggers the same suite as line[0] in ">;"

Michael

[F. Petitjean]

Re: code for Computer Language Shootout

Le Tue, 15 Mar 2005 23:21:02 -0800, Michael Spencer a écrit :[color=blue]
> Jacob Lee wrote:[color=green]
>> On Tue, 15 Mar 2005 21:38:48 -0800, Michael Spencer wrote:
>>
>> Good call.
>>
>>[/color]
>
> How about this then:
>
> basetable = string.maketran s('ACBDGHKMNSRU TWVYacbdghkmnsr utwvy',
> 'TGVHCDMKNSYAAW BRTGVHCDMKNSYAA WBR')
>
> from collections import deque
> from itertools import islice
>
> def output(seq, linelength = 60):
> if seq:
> iterseq = iter(seq)
> while iterseq:
> print "".join(islice( iterseq,linelen gth))[/color]
I suppose you mean :
print "".join( str(item) for item in islice(iterseq, linelength) )
# using python 2.4 genexp[color=blue]
>
> def revcomp(input = sys.stdin):
> seqlines = deque()
> for line in input:
> if line[0] in ">;":
> output(seqlines )
> print line,
> seqlines.clear( )
> else:
> seqlines.extend left(line.trans late(basetable, "\n\r"))
> output(seqlines )
>
>
> It would be nice to inline the output function, and re-arrange the iteration so
> that EOF triggers the same suite as line[0] in ">;"
>
> Michael
>[/color]

[Raymond Hettinger]

Re: code for Computer Language Shootout

Consider keeping the alias for append because it occurs in the
innermost loop. For maximum readability, write: addline = seq.append

Move the ''.join() to the show() function. That eliminates a little
redundancy.

The test dataset doesn't use the semi-colon comment field. So,
consider reversing ';>' to '>;'.


Raymond Hettinger

[Michael Spencer]

Re: code for Computer Language Shootout

F. Petitjean wrote:[color=blue]
> Le Tue, 15 Mar 2005 23:21:02 -0800, Michael Spencer a écrit :
>[/color]
[color=blue][color=green]
>>
>>def output(seq, linelength = 60):
>> if seq:
>> iterseq = iter(seq)
>> while iterseq:
>> print "".join(islice( iterseq,linelen gth))[/color]
>
> I suppose you mean :
> print "".join( str(item) for item in islice(iterseq, linelength) )
> # using python 2.4 genexp
>[/color]
No, as written, given the seq is a sequence of single character strings already
(changing the signature might clarify that):

def output(charseq, linelength = 60):
if charseq:
iterseq = iter(charseq)
while iterseq:
print "".join(islice( iterseq,linelen gth))
[color=blue][color=green][color=darkred]
>>> output("*" * 120, 40)[/color][/color][/color]
*************** *************** **********
*************** *************** **********
*************** *************** **********[color=blue][color=green][color=darkred]
>>> output(['*'] * 120, 40)[/color][/color][/color]
*************** *************** **********
*************** *************** **********
*************** *************** **********[color=blue][color=green][color=darkred]
>>>[/color][/color][/color]

Cheers
Michael

[Steven Bethard]

Re: code for Computer Language Shootout

Michael Spencer wrote:[color=blue]
> def output(seq, linelength = 60):
> if seq:
> iterseq = iter(seq)
> while iterseq:
> print "".join(islice( iterseq,linelen gth))[/color]

Worth noting: "while iterseq" only works because for this case, you have
a list iterator, which provides a __len__ method. This approach will
not work when you have an iterator that does not provide a __len__
method. For a nice infinite printing loop, try:

def gen():
yield '+'*100
yield '*'*100

output(gen())

STeVe

[Michael Spencer]

Re: code for Computer Language Shootout

Steven Bethard wrote:[color=blue]
> Michael Spencer wrote:
>[color=green]
>> def output(seq, linelength = 60):
>> if seq:
>> iterseq = iter(seq)
>> while iterseq:
>> print "".join(islice( iterseq,linelen gth))[/color]
>
>
> Worth noting: "while iterseq" only works because for this case, you have
> a list iterator, which provides a __len__ method.[/color]

Thanks! I had noted that the file iterator didn't behave like this, but I hadn't
deduced the reason. Unfortunately, the above construct, while cute, is also
not terribly speedy.
[color=blue][color=green][color=darkred]
>>> print "\n".join(b ody[-index:-index-linelength:-1][/color][/color][/color]
... for index in xrange(1, len(body), linelength))

is ugly but much faster with an already-existing string

So, my second attempt is:

from itertools import groupby

def revcomp2(input = sys.stdin, linelength = 60):
basetable = string.maketran s('ACBDGHKMNSRU TWVYacbdghkmnsr utwvy',
'TGVHCDMKNSYAAW BRTGVHCDMKNSYAA WBR')

def record(item):
return item[0] in ">;"

for header, body in groupby(input, record):
body = "".join(bod y)
if header:
print body,
else:
body = body.translate( basetable, "\n\r")
print "\n".join(b ody[-index:-index-linelength:-1]
for index in xrange(1, len(body), linelength))


Michael

[igouy@yahoo.com]

Re: code for Computer Language Shootout

We've made it somewhat easier to contribute programs.

No need to subscribe to the mailing-list.
No need for a user-id or login.

See the FAQ "How can I contribute a program?"

http://shootout.alioth.debian.org/faq.php