我应该使用List [A]还是Seq [A]还是别的什么？

Question

我正在写一个包含一些功能性方法的类.首先,我使用List作为参数和返回类型编写它们.然后我想"嘿,你也可以使用更通用的类型!" 所以我用Seq取代了Lists,希望有一天我可以通过喂他们除了列表以外的东西来让我的东西变得更快.

那么我应该为哪些通用的堆栈式数据结构编写我的方法和算法？我能坚持一般的模式吗？所有这一切都是因为这些方法可能需要在将来进行优化,以防它们形成瓶颈.

更新

我会尝试更精确一点:假设您知道正在使用哪些操作,例如反转,.tail,直接元素访问或理解.我可以选择一个类型,这将迫使这些运营效率？

更新2

我非常了解各种任务的具体数据结构的性能.我不知道的是哪个数据结构可能显示为某种超类型的子类.

例如,我应该使用TraversableOnce或IndexedSeq而不是List或Array吗？它会给我买什么东西吗？

附加问题

什么是你的默认列表类似的数据结构的签名？你写的吗？

def a(b: List[A]): List[A] 

要么

def a(b: TraversableOnce[A]): TraversableOnce[A]

你能解释一下原因吗？

Answer 1

List是默认实现LinearSeq,而后者又是默认实现Seq,而默认实现是默认实现Iterable,而后者又是默认实现Traversable.

请参见此处的图表,并根据您的要求选择最常用的类型.

本文档也可能有所帮助.

Answer 2

我认为,一般来说,您应该使用Seq您的参数并设计您的方法以便有效地工作List.通过这种方式,您的方法可以在大多数Seq实现中正常运行,并且您无需在使用方法之前转换seq.

编辑

你的问题里面有很多问题.

1. 那么我应该为哪些通用的堆栈式数据结构编写我的方法和算法？
   • 我认为这里的答案是List.这是一个堆栈,它非常快
2. 我可以选择一种能够提高这些操作效率的类型吗？
   • 一般来说,你将不得不依赖于一个概念性的实现.性能特征在这里http://www.scala-lang.org/docu/files/collections-api/collections_40.html
3. For example shall I use TraversableOnce or IndexedSeq instead of List or Array? Will it buy me anything?
   • Some abstractions have performance characteristics defined, some others don't. For example IndexedSeq scaladoc says "Indexed sequences support constant-time or near constant-time element access and length computation". If you have an IndexedSeq parameter and someone passes an IndexedSeq implementation that does not have "near-constant time element access", then that someone is breaking the contract and it's not your problem.
4. What is your default List-like data-structure signature?
   • Seq

Answer 3

有关集合库的背景信息,请查看Scala 2.8 Collections API文章.

如果您有特定的操作,请特别注意性能特征部分.

关于是否使用特定类型的更一般特征的设计选择,我会说它取决于你在实现中做了什么.例如,如果一个方法接受一个List,它可以指望快速前置,并可以在其实现中使用它.因此,接受更一般的特征可能会产生不必要的性能结果.此外,你将不得不担心你得到什么类型.

scala> def a[A](t:TraversableOnce[A]): TraversableOnce[A] = t
a: [A](t: TraversableOnce[A])TraversableOnce[A]

scala> a(List(1,2))
res0: TraversableOnce[Int] = List(1, 2)

scala> res0.tail
<console>:8: error: value tail is not a member of TraversableOnce[Int]
       res0.tail

如果你想写一些通用的东西,你可能想要保留类型.请参阅具有良好变体类型的TraversableLike.map类似物"我可以使用我的库"吗？了解您将遇到的问题和一些解决方案.