3

编写 Scala 代码时，我经常遇到这样的情况：我有“处理器”函数，这些函数对元素集合进行迭代操作，并且还需要知道集合的长度。

另一方面，我有生成集合的“提供者”函数，因此已经知道长度。生成的集合可能是List[T]、Array[T]或Set[T]等，但即使在 的情况下List[T]，我的生成器也知道大小（即使List类型不存储它）。

因此，我很自然地将“处理器”函数声明为采用似乎适合所有集合类型的最通用类型Iterable[T]，作为参数。然而，他们在内部需要以 O(N) 为代价通过迭代集合遍历来找出大小，这是不可取的。

所以我天真的解决方案是创建一个新类型IterableWithSize[T]，让提供者和处理器函数创建并采用这种类型。Seq[T]两者IndexedSeq[T]似乎都不符合要求。但这似乎是一个相对常见的用例，所以我怀疑有一种更惯用的方法来做到这一点。那会是什么？

4

5 回答 5

2

在 Scala 集合中，诸如性能敏感的方法size不是从特征继承的，而是在底部类型中被覆盖。例如查看以下实现immutable.HashSet：

https://lampsvn.epfl.ch/trac/scala/browser/scala/tags/R_2_9_0_1/src//library/scala/collection/immutable/HashSet.scala

所以你不需要关心它。只需定义一个高级通用特征，例如Traversableor Iterable，您就完成了。

于 2011-07-05T10:23:06.837 回答
2

实际上，没有惯用的方法。Scala 集合的真正意义在于以其他规定的方式（例如Set.contains或Map.get）进行遍历或使用。检查大小不是其中的一部分，其中一些甚至不是有限的。

现在，IndexedSeq这是一个相对安全的赌注——它保证了 O(logn) 索引访问，这只有在你有 O(logn) 大小的情况下才有可能。同样，出于类似的原因Set，Map也相当安全。但是，如果您正在寻找一种可以保证size速度的特征，那么没有。

于 2011-07-05T12:06:59.537 回答
1

怎么样Traversable？您提到的所有集合都继承自它（Array间接通过WrappedArray），它提供size和toIterable（或toIterator）用于遍历。

于 2011-07-05T10:34:53.240 回答
1

我认为没有一种惯用的方法可以做到这一点。但这里有两种选择：

(1) 扩展 Scala 的 List/Set/Array 集合并覆盖 size 方法。这并不像乍看起来那么困难。

(2) 将您的 List/Set/Array 集合与大小一起包装，并定义一个隐式解包器，例如：

class IterableWithSizeWrapper[E](private val c: Iterable[E], val size: Int)
object IterableWithSizeWrapper {
  implicit def unwrap[E](iws: IterableWithSizeWrapper[E]): Iterable[E] = iws.c
}

object ListWithSizeTest {

  def process[E](iws: IterableWithSizeWrapper[E]) {
        // iws.size uses your cached size value
        // iws.take(i) forces the unwrap to the original collect
        // so iws.take(i).size takes the calculated size
    for (i <- 0 to iws.size) assert(iws.take(i).size == i)
  }

  def main(args: Array[String]) {
    process(new IterableWithSizeWrapper(List(1,2,3), 3))
    process(new IterableWithSizeWrapper(Set(1,2,3), 3))
    process(new IterableWithSizeWrapper(Array(1,2,3), 3))
  }
}
于 2011-07-06T07:48:37.890 回答
0

您的处理器功能应该接受Seq[T]. ASeq正是Iterable“有长度”的一个。你剩下的唯一问题是提高length效率。AFAIK 它已经在所有情况下都有效，除了List. 为了List.length提高效率，就像其他人描述的那样：创建一个Seq包装 aList并存储其长度的实现。

于 2015-05-01T22:03:22.730 回答