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

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

怎么样用一个比较优美的方法计算得到一个累加数组,如下

#测试用例:
[]  =>  []
[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(:+)}

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

不过缺点是计算效率好像不怎么高,每次都是从头开始算,前面两个算法都是O(n), 第三个方法是 O(n^2),对于一般的数组基本上没啥区别,如果是大数组,就要考虑下了。

给这个方法取个名字吧,想到了Accumulation这个单词,查了下webster词典,该词的英文意思是 Accumulation - increase or growth by addition especially when continuous or repeated 应该还算贴切,而且acum和sum还挺押韵的

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
  def acum_add
    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]

共收到 29 条回复

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

嗯,先看看你不优美的方法是什么样子的

不好意思,写错了,已经改正

我写的太丑陋了,就是最笨的办法,不好意思拿出来。有没有可以用collect或者inject一下子搞定的,谢谢

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

我觉得写成1行未必就是优美的,楼上几个都是用了动态规划,从底向上计算,日后阅读可能有困难。我写个罗嗦版本的memoization。

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 也许吧,哈哈

很多时候看legacy code,都是不知道代码在解决什么问题,需要猜才可以。 看到这些 one liner 我都是要想一下才知道是做什么的。 如果一定要写 one liner,最好也封装到一个方法里,这样看代码的人至少知道这是干嘛的。

#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

叫sum不太好,又不知道该叫什么~

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

查了下webster词典,该词的英文意思是 Accumulation - increase or growth by addition especially when continuous or repeated 还算贴切吧

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

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

需要 登录 后方可回复, 如果你还没有账号请点击这里 注册