To count number of quadruplets with sum = 0

[n00m]

http://www.spoj.pl/problems/SUMFOUR/

3
0 0 0 0
0 0 0 0
-1 -1 1 1
Answer for this input data is 33.

My solution for the problem is
=============== =============== =============== =============== ==========

import time
t = time.clock()

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

f = open("D:/m4000.txt","rt" )

n = int(f.readline( ))

for o in range(n):
row = map(long, f.readline().sp lit())
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)

q,w,e,r,h = None,None,None, None,None

print sch
print time.clock() - t

=============== =============== =============== =============== ===

Alas it gets "time limit exceeded".
On my home PC (1.6 GHz, 512 MB RAM) and for 4000 input rows it
executes ~1.5 min.
Any ideas to speed it up say 10 times? Or the problem only for C-like
langs?

[Matimus]

Any ideas to speed it up say 10 times? Or the problem only for C-like

langs?

I dout this will speed it up by a factor of 10, but in your solution
you are mapping the values in the input file to longs. The problem
statement states that the maximum value for any of the numbers is
2**28. I assume the reason for this is precisely to allow you to use
32-bit integers. So, you can safely use int instead, and it _might_
speed up a little.

[n00m]

Your suggestion speeded it up 1.5 times (on my 4000 test input rows)!

[Steven Bethard]

n00m wrote:

http://www.spoj.pl/problems/SUMFOUR/

3
0 0 0 0
0 0 0 0
-1 -1 1 1
Answer for this input data is 33.

My solution for the problem is
=============== =============== =============== =============== ==========

import time
t = time.clock()

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

f = open("D:/m4000.txt","rt" )

n = int(f.readline( ))

for o in range(n):
row = map(long, f.readline().sp lit())
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

This won't help much, but you can rewrite the above as::

x_y = x + y
h[x_y] = h.get(x_y, 1)

Or if you're using Python 2.5, try::

h = collections.def aultdict(iterto ols.repeat(0).n ext)

...
for x in q:
for y in w:
h[x + y] += 1
...

Not likely to get you an order of magnitude though.

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

If you use the collections.def aultdict approach above, this becomes::

for x in e:
for y in r:
sch += h[-(x + y)]

Note that you should also probably put all your code into a function --
looking up function locals is quicker than looking up module globals.

STeVe

[Paul Rubin]

"n00m" <n0**@narod.ruw rites:

http://www.spoj.pl/problems/SUMFOUR/
3
0 0 0 0
0 0 0 0
-1 -1 1 1
Answer for this input data is 33.

f = open('input1')
npairs = int(f.readline( ))

quads = [map(int, f.readline().sp lit()) for i in xrange(npairs)]
assert len(quads) == npairs

da = {}

for p in quads:
for q in quads:
z = p[2] + q[3]
da[z] = da.get(z,0) + 1

print sum([da.get(-(p[0]+q[1]), 0) for p in quads for q in quads])

[Paul Rubin]

Paul Rubin <http://ph****@NOSPAM.i nvalidwrites:

print sum([da.get(-(p[0]+q[1]), 0) for p in quads for q in quads])

The above should say:

print sum(da.get(-(p[0]+q[1]), 0) for p in quads for q in quads)

I had to use a listcomp instead of a genexp for testing, since I'm
still using python 2.3, and I forgot to patch that before pasting to
the newsgroup. But the listcomp will burn a lot of memory when the
list is large.

I'd be interested in the running time of the above for your large data set.
Note that it still uses potentially O(n**2) space.

[n00m]

Steven, I ran this:

import time, collections, itertools
t = time.clock()

q,w,e,r,sch = [],[],[],[],0

h = collections.def aultdict(iterto ols.repeat(0).n ext)

f = open("D:/m4000.txt","rt" )

for o in range(int(f.rea dline())):
row = map(int, f.readline().sp lit())
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:
h[x+y] += 1

for x in e:
for y in r:
sch += h[-(x + y)]

q,w,e,r,h = None,None,None, None,None

print sch
print time.clock() - t
========= and it almost froze my PC...
=== but it was faster than my code on input file with 1000 rows:
====== 2.00864607094s VS 3.14631077413s

[Paul Rubin]

"n00m" <n0**@narod.ruw rites:

h = collections.def aultdict(iterto ols.repeat(0).n ext)

Something wrong with
h = collections.def aultdict(int)
?????

for x in e:
for y in r:
sch += h[-(x + y)]

That scares me a little: I think it makes a new entry in h, for the
cases where -(x+y) is not already in h. You want:

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

[Paul Rubin]

"n00m" <n0**@narod.ruw rites:

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.

[Michael Spencer]

n00m wrote:

http://www.spoj.pl/problems/SUMFOUR/

3
0 0 0 0
0 0 0 0
-1 -1 1 1
Answer for this input data is 33.

My solution for the problem is
=============== =============== =============== =============== ==========

import time
t = time.clock()

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

f = open("D:/m4000.txt","rt" )

n = int(f.readline( ))

for o in range(n):
row = map(long, f.readline().sp lit())
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)

q,w,e,r,h = None,None,None, None,None

print sch
print time.clock() - t

=============== =============== =============== =============== ===

Alas it gets "time limit exceeded".
On my home PC (1.6 GHz, 512 MB RAM) and for 4000 input rows it
executes ~1.5 min.
Any ideas to speed it up say 10 times? Or the problem only for C-like
langs?

Perhaps a bit faster using slicing to get the lists and avoiding dict.get:

def sumfour(src):
l = map(int, src.split())
dct={}
s=0
A, B, C, D = l[1::4], l[2::4], l[3::4], l[4::4]
for a in A:
for b in B:
if a+b in dct:
dct[a+b] += 1
else:
dct[a+b] = 1
for c in C:
for d in D:
if -c-d in dct:
s+= dct[-c-d]
return s
if __name__ == '__main__':
import sys
print sumfour(sys.std in.read())
Michael