t*s 发帖数: 1504 | 1 计算2的10000次方所有数字之和
-- 2的0次方是1
initial = 1:[0,0..]
tworaise :: Int -> [Int]
tworaise 0 = initial
tworaise x = double.tworaise $ x-1
double :: [Int] -> [Int]
double l = zipWith (+) [t*2 `mod` 10 | t<-l] (0:[t*2 `quot` 10 | t<-l])
main=do
print.sum.take 10000 $ tworaise 10000
1000次方很快能算出来。10000就不行了。这都搞不定还搞屁啊。 |
t*s 发帖数: 1504 | 2 take其实不用10000, 可以减小到例如3000,但也是out of memory |
a*****e 发帖数: 1700 | 3 你这个算法写得不是特别好,造成最后要 take N, 然后还要预估一个 N
为什么不从 most significant digit 开始排呢?这样也用不着 [0,0..]
我给你改了一下
initial = [1]
tworaise :: [[Int]]
tworaise = initial : map double tworaise
double :: [Int] -> [Int]
double = dropWhile (==0) . foldr f [0]
where
f !d ((!x):xs) =
let (q, r) = (d * 2) `quotRem` 10
in q:r+x:xs
main = print $ sum $ tworaise !! 10000
运行起来是这样的:
bash-4.2$ ghc -XBangPatterns -O2 test.hs
[1 of 1] Compiling Main ( test.hs, test.o )
Linking test ...
bash-4.2$ time ./test
13561
real 0m0.766s
user 0m0.468s
sys 0m0.271s
注意上面算 double 的时候要确保严格求值才快,不然会累积整个 tworaise 的列表,
消耗空间。但是即使你把上面的 ! 去掉,也是可以在 30 秒内返回值,不会出现 out
of memory。你原来的代码则不容易做成 strict,因为不好判断什么时候到达了 most
significant digit。
最后,此程序如果用 Integer 可以一句话表达,算得也最快:
print $ sum $ map ((-48+) . fromEnum) $ show $ 2 ^ 10000
【在 t*s 的大作中提到】 : take其实不用10000, 可以减小到例如3000,但也是out of memory
|
A*******t 发帖数: 443 | 4 这么写haskell真是纯属有病
【在 t*s 的大作中提到】 : 计算2的10000次方所有数字之和 : -- 2的0次方是1 : initial = 1:[0,0..] : tworaise :: Int -> [Int] : tworaise 0 = initial : tworaise x = double.tworaise $ x-1 : double :: [Int] -> [Int] : double l = zipWith (+) [t*2 `mod` 10 | t<-l] (0:[t*2 `quot` 10 | t<-l]) : main=do : print.sum.take 10000 $ tworaise 10000
|
a*****e 发帖数: 1700 | 5 不要这样嘛,人没准儿就是找个题目练练手,目的不是题目的本身
【在 A*******t 的大作中提到】 : 这么写haskell真是纯属有病
|
t*s 发帖数: 1504 | 6 测试了一下,应该是对的。
但还真看不懂,俺再接着去读tutorial
关键是这题对于imperative的语言来说简直trivial
同样的傻算法python
N=10000
result=[1]+[0]*(N-1)
for i in range(N):
carry=0
for j in range(N):
temp=result[j]*2+carry
result[j]=temp%10
carry=temp//10
print(sum(result))
写花了30秒,运算花了大概也是30秒。
【在 a*****e 的大作中提到】 : 你这个算法写得不是特别好,造成最后要 take N, 然后还要预估一个 N : 为什么不从 most significant digit 开始排呢?这样也用不着 [0,0..] : 我给你改了一下 : initial = [1] : tworaise :: [[Int]] : tworaise = initial : map double tworaise : double :: [Int] -> [Int] : double = dropWhile (==0) . foldr f [0] : where : f !d ((!x):xs) =
|
t*s 发帖数: 1504 | 7 对,就是
俺写的第一个Haskell程序
用imperative的话,用我的傻算法,从头到尾就是10000个int
但fp, 因为不让改值,10000次循环就成了1000000000个int
Haskell也不智能,不知道garbage collection
【在 a*****e 的大作中提到】 : 不要这样嘛,人没准儿就是找个题目练练手,目的不是题目的本身
|
a*****e 发帖数: 1700 | 8 你仔细看我写的那个 double,和你这个 inner loop 没有大区别
你这个是从左往右,我写的是从右往左 (foldr)
你要是用 Haskell 里面的 Vector,或者是 Mutable Vector,都能写出和你那个
Python 基本一样的程序。
不过你既然选择了用 List,难免会遇到 strictness 的问题。
【在 t*s 的大作中提到】 : 测试了一下,应该是对的。 : 但还真看不懂,俺再接着去读tutorial : 关键是这题对于imperative的语言来说简直trivial : 同样的傻算法python : N=10000 : result=[1]+[0]*(N-1) : for i in range(N): : carry=0 : for j in range(N): : temp=result[j]*2+carry
|
a*****e 发帖数: 1700 | 9 不是因为不让改值,是你还不太理解 laziness 和 data dependency。你看我写的就没
有内存问题。
如果你画一个图,每一行是数字 2^n 的数字列
然后下一行是根据上一行算出来的,如果把每个数字和计算它所需的上一行的数字之间
画一条线
那么你最后得到的是一个斜三角,计算最后一行的最后一个数字(如果按你的写法
most significant digit 在最后)所需要的 dependency 可以一直追溯到第一行第一
个数字。
所以这时候你用 lazy 的方式按需来算,就必须保证所需的 dependecies 在那里。这
就是为什么会消耗内存。
注意了 strictness 之后就没有内存消耗问题了,只是你这个算法本身是 quadratic,
所 n 越大越慢。
【在 t*s 的大作中提到】 : 对,就是 : 俺写的第一个Haskell程序 : 用imperative的话,用我的傻算法,从头到尾就是10000个int : 但fp, 因为不让改值,10000次循环就成了1000000000个int : Haskell也不智能,不知道garbage collection
|
a*****e 发帖数: 1700 | 10 我又想了一下,你原程序是从左往右算 sum 的话,那么实际上任意时刻的 dependecy
是左上到目前所访问的位置的斜线,之前访问过的已经被 GC 掉了。所以也不应该
有内存问题。
我试验了一下,你的原程序算 5000 和 10000 的内存 profile 显示内存用量分别是 0
.6-1M 和 1.2-2M,属于 linear 增长。所以实际上并没有内存问题,就是算得慢而已
,你需要用 ghc -O2 来编译运行。
【在 a*****e 的大作中提到】 : 不是因为不让改值,是你还不太理解 laziness 和 data dependency。你看我写的就没 : 有内存问题。 : 如果你画一个图,每一行是数字 2^n 的数字列 : 然后下一行是根据上一行算出来的,如果把每个数字和计算它所需的上一行的数字之间 : 画一条线 : 那么你最后得到的是一个斜三角,计算最后一行的最后一个数字(如果按你的写法 : most significant digit 在最后)所需要的 dependency 可以一直追溯到第一行第一 : 个数字。 : 所以这时候你用 lazy 的方式按需来算,就必须保证所需的 dependecies 在那里。这 : 就是为什么会消耗内存。
|
t*s 发帖数: 1504 | 11 果然是大神
O2加了就可以了,不加就out of memory (用的最新版windows ghc)
你算的是三角形,我算的是正方形
两者内存速度差距应该就是最多一倍。
网上查了一下,似乎O2有些时候会让Haskell程序产生数量级的变化,比如从O(n)到O(1
)啥的。
dependecy
0
【在 a*****e 的大作中提到】 : 我又想了一下,你原程序是从左往右算 sum 的话,那么实际上任意时刻的 dependecy : 是左上到目前所访问的位置的斜线,之前访问过的已经被 GC 掉了。所以也不应该 : 有内存问题。 : 我试验了一下,你的原程序算 5000 和 10000 的内存 profile 显示内存用量分别是 0 : .6-1M 和 1.2-2M,属于 linear 增长。所以实际上并没有内存问题,就是算得慢而已 : ,你需要用 ghc -O2 来编译运行。
|