计算sum = 0的四元组数 [英] To count number of quadruplets with sum = 0

问题描述

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


3

0 0 0 0

0 0 0 0

-1 - 1 1 1

这个输入数据的答案是33.


我的问题解决方案是

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

导入时间

t = time.clock（）

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


f = open（" D ：/m4000.txt"，" rt"）


n = int（f.readline（））


范围内的o（ n）：

row = map（long，f.readline（）。split（））

q.append（row [0]）

w.append（row [1]）

e.append（row [2]）

r.append（row [3]）


f.close（）

$ q $ b for q in：

for y in w：

如果h.has_key（x + y）：

h [x + y] + = 1

else：

h [x + y] = 1


for e：

为r中的y：

sch + = h.get（ - （x + y），0）


q，w， e，r，h =无，无，无，无，无


print sch

print time.clock（） - t


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


唉它超出了时间限制。

在我的家用电脑（1.6 GHz，512 MB RAM）和4000输入行它

执行~1.5分钟。

任何加速它的想法说10次？或者问题只适用于类似C的

langs？

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().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)

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?

推荐答案

任何加快速度的想法都说10倍？或者问题只适用于C-like

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

langs？

langs?

我这会将它加速10倍，但是在你的解决方案中你需要映射输入文件中的值
多头。问题

声明声明任何数字的最大值是

2 ** 28。我假设这样做的原因恰恰是允许你使用

32位整数。所以，你可以安全地使用int，而_might_

加速一点。

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.

你的建议加快了它的速度1.5次（在我的4000个测试输入行上）！

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

n00m写道：

n00m wrote:

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

>
3

0 0 0 0

0 0 0 0

-1 -1 1 1

这个输入数据的答案是33.


我解决这个问题的方法是

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


导入时间

t = time.clock（）


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


f = open（" D：/m4000.txt"，" rt）


n = int（f.readline（））


范围内的o（n）：

row = map（long，f.readline（）。split（））

q.append（row [0]）

w.append（row [1]）

e.append（row [2]）

r.append（row [3]）

>
f.close（）

$ q $ b for x in the：

for y in w：

if h .has_key（x + y）：

h [x + y] + = 1

else：

h [x + y] = 1

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().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

这不会有多大帮助，但你可以重写上面的内容::


x_y = x + y

h [x_y] = h.get（x_y，1）


或者如果您使用的是Python 2.5，请尝试::


h = collections.defaultdict（itertools.repeat（0）.next）


...

for x in q：

for y in w：

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.defaultdict(itertools.repeat(0).next)

...
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）

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

如果使用上面的collections.defaultdict方法，则变为::


for x in e：
$ b中的b $ b：

sch + = h [ - （x + y）]


请注意，您也应该放置所有代码进入函数 -

查找函数本地函数比查找模块全局变量更快。


STeVe

If you use the collections.defaultdict 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

这篇关于计算sum = 0的四元组数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！