List.reverse的复杂性？

Question

在Scala中,有reverse列表方法.这种方法的复杂性是什么？简单地使用原始列表是否更好,并始终记住列表与我们期望的相反,或者reverse在操作之前明确使用.

编辑:我真正感兴趣的是获取原始列表的最后两个元素(或反向列表的前两个).

所以我会这样做:

val myList = origList.reverse
val a = myList(0)
val b = myList(1)

这不是一个循环,只是我的库中的一次性事物......但如果其他人使用该库并将其置于循环中,则不在我的控制之下.

Answer 1

看看来源,O(n)就像你可能合理期望的那样:

override def reverse: List[A] = {
  var result: List[A] = Nil
  var these = this
  while (!these.isEmpty) {
    result = these.head :: result
    these = these.tail
  }
  result
}

如果在您的代码中,您能够以相反的顺序以相反的顺序迭代列表,那么执行此操作而不是反转List 会更有效.

事实上,如果其中包括使用原有清单的替代操作的工作少比O(n)时间,那么就与该去一个真正的说法.如果你更依赖它(特别是如果在其他循环中使用,正如oxbow_lakes指出的那样),使算法渐近更快将产生巨大的差异.

总的来说,虽然我希望你反转列表的任何东西都意味着你关心的是一个非平凡数量的元素的相对排序,所以无论你做什么,本质上都是O(n).(对于其他数据结构,例如二叉树,这可能不是这样;但是列表是线性的,在极端情况下甚至reverse . head不能在O(1)时间内使用单链表进行.)

因此,如果您在两个O(n)选项之间进行选择 - 对于绝大多数应用程序而言,在迭代时间内缩短几纳秒并不会真正获得任何东西.因此,使代码尽可能可读是"最好的" - 这意味着调用reverse然后迭代,如果这与您的意图最接近.

(如果您的应用程序太慢,并且分析显示此列表操作是一个热点,那么您可以考虑如何使其更有效.到那时,哪个可能会涉及到您当前的候选人的不同选项,给定你在那时得到的额外背景.)