如何修复 Scala 中部分求和的实现？
这是我的上一个问题的后续问题。我想自己实现 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 个元素。
正确吗？您将如何修复代码？
This is a follow-up to my previous question. I would like to implement s.scanLeft(0)(_ + _) by myself (just as an exercise)
That is, I would like to write function partial_sums, which receives stream s = s1, s2, s3, ... and produces a new stream s1, s1 + s2, s1 + s2 + s3, ...
I implement it as follows:
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))
This code works ok. However it looks like it takes O(n) to get the n-th element of partial_sums. (i.e. s[1] + s[2] + s[3] ... + s[n]). I would like to code partial_sums[n] = partial_sums[n-1] + s[n], which takes O(1) to calculate the n-th element.
Is it correct? How would you fix the code?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
基本思想是保持运行总计，而不是批量添加流
The basic idea is to keep a running total, rather than adding streams in bulk