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

[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), 來自: 61.231.60.18
※ 文章網址: http://www.ptt.cc/bbs/Python/M.1405097833.A.8A6.html
推 ya790206:三種解法，越上面的越好
→ ya790206:1. 使用Banyan 的 SortedDict 取代內建的 dict
→ ya790206:2. 自己實作一個類似 dict ，其特性能夠將資料暫存到硬碟
→ ya790206:3. 將 dict 的資料存到 redis（其他或nosql)
→ ya790206:python 的內建 dict 實作方式是 hashtable，太吃記憶體。
→ ya790206:1.5 找其他不是使用 hashtable 來實作dict 的 library
→ Azusa:謝謝