Re: [問題] Almost Pi, 記憶體問題

看板Python作者yjc1 (.來而色月踏我.)時間11年前 (2014/07/13 22:19)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串2/2 (看更多)

觀察你的 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://www.ptt.cc/bbs/Python/M.1405261161.A.B6F.html ※ 編輯: yjc1 (111.235.242.72), 07/14/2014 13:55:31