觀察你的 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
: 請問要怎麼解決這種問題？