scala – List.reverse的复杂性？

发布时间：2020-12-16 19:09:18 所属栏目：安全来源：网络整理

导读：在 Scala中,列表有相反的方法.这种方法的复杂性是什么？最好简单地使用原始列表,并始终记住列表与我们期望的相反,或者在操作之前明确地使用反向. 编辑：我真正感兴趣的是获取原始列表的最后两个元素(或反向列表的前两个). 所以我会做一些像： val myList = o

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

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

所以我会做一些像：

val myList = origList.reverse
val a = myList(0)
val b = myList(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
}

如果在你的代码中,你可以按照相反的顺序遍历列表,并以相同的顺序迭代,那么执行此操作更有效,而不是反转列表.

事实上,如果您使用原始列表的替代操作在不到O(n)的时间内工作,那么有一个真正的参数.如果您更依赖它(特别是在其他循环中使用,如oxbow_lakes在下面指出),渐近地使算法更快地产生巨大的差异.

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

所以如果你在两个O(n)选项之间选择 – 绝大多数的应用程序,从迭代时间开始刮掉几纳秒就不会真的让你感到任何东西.因此,尽可能使您的代码可读,这将是最好的 – 这意味着调用反向然后迭代,如果最接近您的意图.

(如果你的应用程序太慢,并且分析表明这个列表操纵是一个热点,那么你可以考虑如何使它更有效率.在这一点上可能会涉及到两个当前候选人的不同选项,给定那个时候你会有额外的上下文)

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!