作者yjc1 (.来而色月踏我.)
看板Python
标题Re: [问题] Almost Pi, 记忆体问题
时间Sun Jul 13 22:19:18 2014
观察你的 code, 造 two sum dict d 的目的是想在最後一步 fn(k) 反查回平方和。
而且多一组 lst 的目的是要对 d.keys() 排序以利 binary search 。
不想大改演算法的话，建议就直接合在一起，
用一组 tuple list 来达成以上的效果，
在 64bit 环境下实测 g(1000) 大概会花到将近 9GB memory，
DRAM 不够的话，过程中会因为吃 swap I/O 而变得很慢...
(在我的旧nb上跑了八分钟)
另外，python 有处理 binary search/insert 的 bisect module，
可以直接拿来使用。
pseudo code:
lst = []
for i in xrange(length):
n = bisect.bisect(f, pi - f[i], i)
# print "progress 1: {0}/{1}".format(i, length)
lst.extend([(f[i]+f[j], i*i+j*j) for j in range(i, n)])
lst.sort()
ans = (4, 0)
for i in xrange(len(lst)/2):
# print "progress 2: {0}/{1}".format(i, len(lst)/2)
v, s = lst[i]
j = bisect.bisect(lst, (pi-v, 0), i)
if j >= len(lst):
continue
ans = min(ans,
(abs(pi-v-lst[j][0]), s + lst[j][1]),
(abs(pi-v-lst[j-1][0]), s + lst[j-1][1]))
print ans[1]
※ 引述《Azusa (梓)》之铭言：
: Problem: http://projecteuler.net/problem=461
: Code: https://gist.github.com/anonymous/967924f40bb3345d466f
: 我的演算法大概是
: 1. 找出最大的 k, 使 f_n(k) 不超过 pi (depend on n)
: 2. 造 dictionary f,使 f = f_n(k)|k=0,..,l
: 3. 造 two sum dictionary d, 过程中如果碰到两个的和 >= pi 就丢掉
: 4. lst = list(d) 抓出来 sort
: 5. 前半 lst 的每一个元素和pi的差做 binary search & 找 minimal value
: n = 200 的话没什麽问题
: 但是 n = 10000 实在是太大了
: 会在 line 31~33 出现 MemoryError
: 请问要怎麽解决这种问题？
--
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 123.195.48.122
※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Python/M.1405261161.A.B6F.html
※ 编辑: yjc1 (111.235.242.72), 07/14/2014 13:55:31