# Ruby [更新方法] 怎么样用比较优美的方法得到某一数组的累加数组，例如 [1,3,5,7] => [1,4,9,16]

FarFar · 2012年11月30日 · 最后由 nil 回复于 2012年12月02日 · 4713 次阅读

``````#测试用例：
[]  =>  []
[0, -3, 5, 7]  =>  [0, -3, 2, 9]
[1, 3, 5, 7]   =>  [1, 4, 9, 16]
``````

``````a = [1,3,5,7]

# Method 1 from @fredwu @abitno  => O(n)
a.inject([]) { |sum,e| sum << (sum[-1] || 0) + e }

# Method 2 from @luikore => O(n)
sum = 0
a.map {|e| sum += e }

# Method 3 from @nil => O(n^2)
a.length.times.map {|i| a[0..i].inject(:+)}

# Update Method 3 => O(n)
temp = 0
a.length.times.map {|i| temp = [temp, a[i]].inject(:+)}

``````

//////////////////// 更新 /////////////////////// 第三种方法的好处是可以扩展为其他运算符号，这样累加或者累乘都可以解决了。

``````def acum(a, init, &oper)
a.length.times.map {|i| a[0..i].inject(init, &oper)}
end

#测试用例
a = [1,3,5,7]

#累加（注意init应设为0）
p acum(a, 0, &:+)  => [1, 4, 9, 16]

#累乘（注意init应设为1）
p acum(a, 1, &:*)  => [1, 3, 15, 105]
``````

``````a = %w[r u b y]
#字符串的累积合并
p acum(a, "", &:+)  => ["r", "ru", "rub", "ruby"]
``````

//////////////////// 更新 /////////////////////// 简单测试了下，对大数组，两种方法区别还是挺大的

``````class Array
sum = 0
self.map {|e| sum += e }
end

def acum(init=0, &oper)
self.length.times.map {|i| self[0..i].inject(init, &oper)}
end
end

(1..100).to_a.acum_add     #  => [Finished in 0.2-0.3s]
(1..100).to_a.acum(&:+)     #  => [Finished in 0.2-0.3s]

(1..10000).to_a.acum_add  #  => [Finished in 0.2-0.4s]
(1..10000).to_a.acum(&:+)  #  => [Finished in 8.8s] !!!!!
``````

//////////////////// 更新 /////////////////////// 把 Method 3 改进了下，现在也是 O(n) 了, 各取所长, 不知道有没有到 O(logn) 的

``````class Array
def acum(init=0, &oper)
temp = init
self.length.times.map {|i| temp = [temp, self[i]].inject(init, &oper)}
end
end

(1..10000).to_a.acum(&:+)  #  => [Finished in 0.2-0.4s]

``````

1 + 3 + 5 等于 10？还是我根本没理解累加数组的意思？

``````a = [1,3,5,7]
b=[]; a.inject(0){ |r, e| b << r+e; b[-1] }; b #=> [1, 4, 9, 16]
``````

``````[1,3,5,7].inject([]) { |l,e| l << (l.last || 0) + e }
``````
``````[1,3,5,7].inject([]) {|result, el| result << el + (result[-1] || 0) }
[1,2,4].inject([]) {|result, el| result << el + (result[-1] || 0) }
``````

#6 楼 @abitno 好缩写，好.last

``````def memoize(f)
cache = {}
lambda {|*args| cache[args] ||= f.call(*args)  }
end

sum_to_index = lambda do |array, index|
if index == 0
array[index]
else
array[index] + sum_to_index.call(array, index - 1)
end
end

sum_to_index = memoize(sum_to_index)

array = [1, 3, 5, 7]

array.map.with_index {|entry, index| sum_to_index.call(array, index)  }
``````
``````a = [1, 3, 5, 7]
sum = 0
b = a.map {|e| sum += e }
``````

#9 楼 @pongyo 我觉得你这个阅读有困难，哈哈

#11 楼 @fresh_fish 也许吧，哈哈

#12 楼 @pongyo 想得很美... 不过经常的情况是本来只有一行看不懂, 写成一堆变成好多行看不懂, 本来维护代码只用改一个地方, 写成一堆却要改很多个地方, 本来 debug 栈很浅很容易, 写成一堆 debug 栈很深搞半天...

#13 楼 @luikore 如果写成一堆还看不懂，那要改的是把这一堆改成看得懂的，而不是留着一行看不懂需要猜的代码。

#13 楼 @luikore 就本帖这个题目来说，我的写法是夸张手法，目的是举个例子。我觉得你在 10 楼的很好，再往前的代码不是那么一目了然。

#13 楼 @luikore 用 collect 也可以，不过一直搞不清楚 collect 和 map 有什么本质区别

``````a = [1, 3, 5, 7]
sum = 0
b = a.collect {|e| sum += e }
``````

a = [1,3,5,7] b=[] a.reduce([]){|result,element| b << (result.last || 0) + element} 不知道 reduce 和 inject 他们的具体实现那个更好

#16 楼 @FarFar collect 就是 map , 它们是一个函数两个名。 #17 楼 @qinjker reduce 就是 inject , 它们是一个函数两个名。

#17 楼 @qinjker 看了一篇文章有关 map 与 collect，reduce 与 inject 区别和历史由来 http://www.rubycc.com/bbs/topic_detail/125

#19 楼 @FarFar 它们在 Ruby 内部的实现上没有任何区别。

``````rb_define_method(rb_cArray, "collect", rb_ary_collect, 0);
rb_define_method(rb_cArray, "map", rb_ary_collect, 0);
``````

#21 楼 @skandhas 恩，在 ruby 中的确是相同的。只是历史由来不同，最初的实现方式也不同，map 和 reduce 的由来是 Lisp，collect 和 inject 的由来是 Smalltalk。

#22 楼 @FarFar 这与 Ruby 在设计之初就参考了 Smalltalk 和 Lisp 的部分特点有关。

``````[1,3,5,7].sum
``````
``````
class Array
def sum
self.reduce([]) { |sum,e| sum << (sum[-1] || 0) + e }
end
end
``````

``````
class Array
def accum
(0...self.count).map {|i| self.sum_for_range(0..i)}
end

def sum_for_range(range)
self[range].reduce(0, :+)
end
end
``````

#25 楼 @nil 可以叫 accumulation 或者简称 accum / acum，而且 acum 对应 sum 挺配的。的确，一个简单合适的名字是一个方法生命力的重要因素

#25 楼 @nil 修改了下，把你的方法改进为 O(n)，见帖子

#28 楼 @FarFar 嗯嗯，不错；我编码几乎不考虑时间空间复杂度的，呵呵~