Scala - 获取 List 的只读子列表视图

Question

我希望能够获得一个List，Seq或者是一个只读的Iterable，它们都是List的部分视图。在我的特定情况下，这个视图总是从第一个元素开始。 List.slice 和 filter 都是O(n)的，有没有比这更好的方法 - 我不需要任何像+，-等操作。只需要apply，map，flatMap等来提供子列表的列表推导语法。

答案是编写自己的类，其迭代器保持计数以知道结束位置吗？

- daveb

Answer 1

Stream（流）是Scala的一种延迟计算方式。由于Stream的惰性，Stream.take()在这种情况下所需的时间复杂度为O(1)。唯一需要注意的是，如果你想在对Stream进行列表推导之后获得一个List，你需要将其转换回List。List.projection可以让你得到一个Stream，它拥有大多数List的操作。

scala> val l = List(1, 2, 3, 4, 5)
l: List[Int] = List(1, 2, 3, 4, 5)

scala> val s = l.projection.take(3)
s: Stream[Int] = Stream(1, ?)

scala> s.map(_ * 2).toList
res0: List[Int] = List(2, 4, 6)

scala> (for (i <- s) yield i * 2).toList
res1: List[Int] = List(2, 4, 6)

- Walter Chang

Answer 2

List.slice和List.filter都返回列表--根据定义，列表是不可变的。+和-方法返回一个不同的列表，它们不会改变原始列表。此外，要做到更好的时间复杂度比O（N）难。一个列表不是随机访问的，而是一个链接的列表。所以想象一下，如果你想要的子列表是列表的最后一个元素，那么访问该元素的唯一方法是遍历整个列表。

- michaelg

Answer 3

对于List的drop操作，O(n)是最优解。至于其他操作：

def constantSlice[T](l: List[T], start: Int, end: Int): Iterator[T] =
  l.drop(start).elements.take(end - start)

无论是元素还是在迭代器上的take操作，时间复杂度都为O(1)。

当然，迭代器不是一个可迭代对象，因为它不能被重复使用。在Scala 2.8中更倾向于返回可迭代对象而非迭代器。如果你需要在Scala 2.7上重复使用，那么Stream可能是最好的选择。

- Daniel C. Sobral