To count number of quadruplets with sum = 0

[mark.dufour at gmail.com]

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")

n = int(f.readline())

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!)