Chinaunix

标题: [已解决] haskell 如何高效地计算部分和？ [打印本页]
作者: drunkedcat    时间: 2009-03-29 19:42
标题: [已解决] haskell 如何高效地计算部分和？
对于一个整数数组 x，现在要计算它其中每个元素所在位置之前的各个元素的和，
例如，
x = [1,2,3,4,5,6,7]
要得到如下的结果
s = [0,1,3,6,10,15,21]

用 c 的方法，只要计算 6 次加法就可以得到以上结果。
用 haskell， 能这样高效地做吗？

我想到的很直接的做法是，

subsum x = map sum $ init $ inits x

但是觉得可能做会多余的计算。

不知道各位以为如何。谢谢了先。

[ 本帖最后由 drunkedcat 于 2009-3-29 20:52 编辑 ]
作者: win_hate    时间: 2009-03-29 19:59
这个怎么样？


  2. Prelude> let s=0:[x+y|x<-[1..7]|y<-s]
  3. Prelude> s
  4. [0,1,3,6,10,15,21,28]
  5. Prelude>
复制代码


要带这个参数

-XParallelListComp
作者: izhier    时间: 2009-03-29 20:03
c 中可以优化算法，进而提高程序运行效率
haskell 中需要考虑优化算法吗？
编译器会优化吧？
作者: drunkedcat    时间: 2009-03-29 20:33
原帖由 win_hate 于 2009-3-29 19:59 发表
这个怎么样？


Prelude> let s=0:[x+y|x


要带这个参数

-XParallelListComp


win_hate  兄说的正是，我也刚好想到这里了。

subsum xs = 0 : [x+y | (x,y) <- zip xs $ subsum xs]
作者: MMMIX    时间: 2009-03-29 20:40
原帖由 drunkedcat 于 2009-3-29 19:42 发表
对于一个整数数组 x，现在要计算它其中每个元素所在位置之前的各个元素的和，
例如，
x = [1,2,3,4,5,6,7]
要得到如下的结果
s = [0,1,3,6,10,15,21]

  2. Prelude> scanl (+) 0 [1..7]
  3. [0,1,3,6,10,15,21,28]
复制代码
作者: drunkedcat    时间: 2009-03-29 20:47
原帖由 MMMIX 于 2009-3-29 20:40 发表


Prelude> scanl (+) 0 [1..7]
[0,1,3,6,10,15,21,28]


MMMIX 一出手，更加简练，佩服，学习ing。只是要加上一个 init。
作者: MMMIX    时间: 2009-03-29 21:04
原帖由 drunkedcat 于 2009-3-29 20:47 发表


MMMIX 一出手，更加简练，佩服，学习ing。只是要加上一个 init。

嫌那个 0？那用 scanl1 吧

  2. Prelude> scanl1 (+) [0..7]
  3. [0,1,3,6,10,15,21,28]
复制代码
作者: drunkedcat    时间: 2009-03-29 21:37
标题: 回复 #7 MMMIX 的帖子
不是第一个零，是最后一个数，也就是全体元素的和，这个是不需要的。
作者: flw    时间: 2009-03-29 23:07
原帖由 drunkedcat 于 2009-3-29 21:37 发表
不是第一个零，是最后一个数，也就是全体元素的和，这个是不需要的。

需要多少就 take 多少不就得了。
作者: DQP    时间: 2009-03-30 10:04
大家的方法都很绚。
我来个笨的。
先写成scheme 一会再来翻译。。。。

  2. (define (accumulated-sum lon)
  3.   (cond
  4.    [(empty? (cdr lon)) lon]
  5.    [else (accumulated-add
  6.           (car lon)
  7.           (accumulated-sum (cdr lon)))]))

  9. (define (accumulated-add n los)
  10.   (cons (+ n (car los)) los))

  12. (accumulated-sum '(4 3 2 1))
  13. >(10 6 3 1)
复制代码
作者: win_hate    时间: 2009-03-30 10:22
我以前也用 scheme 写过一个类似的，在

http://bbs3.chinaunix.net/viewth ... p;extra=&page=2

第 12，13 楼。 是 SICP 的一个练习。
作者: x2    时间: 2009-03-30 11:40
来一个不用stream的。

  2. (use-modules (srfi srfi-1))

  4. (define (calc l v s)
  5.   (if (null? l)
  6.       v
  7.       (calc (cdr l) (append v (list s)) (+ (car l) s))))

复制代码


  2. > (calc (iota 7 1) '() 0)
  3. (0 1 3 6 10 15 21)
复制代码
作者: win_hate    时间: 2009-03-30 13:30
标题: 回复 #12 x2 的帖子
下面这段代码与你的很接近，使用了 fold


  2. f z@(x:xs) y = (x+y):z
复制代码


  2. *Main> (foldl f [0] [1..7])
  3. [28,21,15,10,6,3,1,0]
  4. *Main> reverse (foldl f [0] [1..7])
  5. [0,1,3,6,10,15,21,28]
复制代码
作者: x2    时间: 2009-04-04 12:30
使用了srfi-1的fold和iota, 令程序看起来简洁了很多。

  2. (use-modules (srfi srfi-1))

  4. (define (f y ls) (cons (+ y (car ls)) ls))
  5. (display
  6. (reverse (cdr (fold f '(0) (iota 7 1)))))
复制代码




欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2