如何在Scala中修复部分和的实现？

发布时间：2020-12-16 18:07:44 所属栏目：安全来源：网络整理

导读：这是我 previous question的后续内容.我想自己实现s.scanLeft(0)(_ _)(就像练习一样) 也就是说,我想写函数partial_sums,它接收流s = s1,s2,s3,…并产生一个新流s1,s1 s2,s1 s2 s3,… 我实现如下： def add_streams(s1:Stream[Int],s2:Stream[Int]) = (s1 zip

这是我 previous question的后续内容.我想自己实现s.scanLeft(0)(_ _)(就像练习一样)

也就是说,我想写函数partial_sums,它接收流s = s1,s2,s3,…并产生一个新流s1,s1 s2,s1 s2 s3,…

我实现如下：

def add_streams(s1:Stream[Int],s2:Stream[Int]) =
  (s1 zip s2) map {case (x,y) => x + y}

def partial_sums(s:Stream[Int]):Stream[Int] =
  Stream.cons(s.head,add_streams(partial_sums(s),s.tail))

这段代码工作正常.然而,看起来需要O(n)来获得partial_sums的第n个元素. (即s [1] s [2] s [3] … s [n]).我想编写partial_sums [n] = partial_sums [n-1] s [n],它采用O(1)来计算第n个元素.

这是对的吗？你会如何修复代码？

解决方法

基本思路是保持运行总量,而不是批量添加流

def partialSums(s:Stream[Int]) = if(s.isEmpty) new Stream[Int]() else partialSums(s,0)

def partialSums(s:Stream[Int],runningTotal:Int)= Stream.cons(s.head+runningTotal,partialSums(s.tail,s.head+runningTotal)

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!