# To count number of quadruplets with sum = 0

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

```Paul Rubin wrote:
> "n00m" <n00m at narod.ru> 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://
mark.dufour.googlepages.com), 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")

for o in range(n):
row = [int(x) for x in f.readline().split()]
q.append(row[0])
w.append(row[1])
e.append(row[2])
r.append(row[3])

f.close()

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

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

print sch
print time.clock() - t

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

```