To count number of quadruplets with sum = 0

mark.dufour at mark.dufour at
Sat Mar 17 20:00:02 CET 2007

Paul Rubin wrote:
> "n00m" <n00m at> writes:
> > Two first outputs is of above (your) code; next two - of my code:
> Yeah, I see now that we both used the same algorithm.  At first glance
> I thought you had done something much slower.  The 10 second limit
> they gave looks like they intended to do it about this way, but with a
> compiled language.  68 seconds isn't so bad for 4000 entries in pure
> CPython.  Next thing to do I think is use psyco or pyrex.

FWIW, the original program can also be compiled with Shed Skin (http://, an experimental (static-)Python-to-C++
compiler, resulting in a speedup of about 8 times for a single test
with 500 tuples. here's a slightly modified version that works with
Shed Skin CVS at least:

import time
t = time.clock()

q,w,e,r,sch,h = [],[],[],[],0,{}

f = open("m33.txt","rt")

n = int(f.readline())

for o in range(n):
   row = [int(x) for x in f.readline().split()]


for x in q:
   for y in w:
     if h.has_key(x+y):
       h[x+y] += 1
       h[x+y] = 1

for x in e:
   for y in r:
     sch += h.get(-(x+y),0)

print sch
print time.clock() - t

Mark Dufour (Shed Skin author - send me bug reports!)

More information about the Python-list mailing list