作者Azusa (梓)
看板Python
标题[问题] Almost Pi, 记忆体问题
时间Sat Jul 12 00:57:10 2014
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://webptt.com/cn.aspx?n=bbs/Python/M.1405097833.A.8A6.html
1F：推 ya790206:三种解法，越上面的越好 07/12 21:51
2F：→ ya790206:1. 使用Banyan 的 SortedDict 取代内建的 dict 07/12 21:54
3F：→ ya790206:2. 自己实作一个类似 dict ，其特性能够将资料暂存到硬碟 07/12 21:54
4F：→ ya790206:3. 将 dict 的资料存到 redis（其他或nosql) 07/12 21:56
5F：→ ya790206:python 的内建 dict 实作方式是 hashtable，太吃记忆体。 07/12 21:57
6F：→ ya790206:1.5 找其他不是使用 hashtable 来实作dict 的 library 07/12 22:18
7F：→ Azusa:谢谢 07/13 11:05