To count number of quadruplets with sum = 0

Anton Vredegoor anton.vredegoor at gmail.com
Fri Mar 16 14:29:56 CET 2007


n00m wrote:

> 62.5030784639

Maybe this one could save a few seconds, it works best when there are 
multiple occurrences of the same value.

A.

from time import time

def freq(L):
      D = {}
      for x in L:
          D[x] = D.get(x,0)+1
      return D

def test():
     t = time()
     f = file('m4000.txt')
     f.readline()
     L = []
     for line in f:
         L.append(map(int,line.split()))

     q,w,e,r = map(freq,zip(*L))
     sch,h = 0,{}
     for xk,xv in q.iteritems():
       for yk,yv in w.iteritems():
         if h.has_key(xk+yk):
           h[xk+yk] += xv*yv
         else:
           h[xk+yk] = xv*yv

     for xk,xv in e.iteritems():
       for yk,yv in r.iteritems():
         if h.has_key(-(xk+yk)):
           sch += h[-(xk+yk)]*xv*yv

     print sch
     print time()-t

if __name__=='__main__':
     test()




More information about the Python-list mailing list