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 来编译运行。
|
