1

我觉得 insertSortRight 比 insertSortLeft 效率低，因为 insertSortRight 需要调用 List.last（即 O(n)）作为 insert() 的参数之一，其中 insertSortLeft 调用 List.head（即 O(1)）作为一个参数insert() 的参数。

这种理解正确吗？谢谢。

def insertSortRight(unsorted: List[Int]) : List[Int] = {
  (unsorted :\ List[Int]()) ((a, b) => insert(a, b))
}

def insertSortLeft(unsorted: List[Int]) : List[Int] = {
  (List[Int]() /: unsorted) ((a, b) => insert(b, a))
}  

def insert(a: Int, list: List[Int]) : List[Int] = list match {
  case List() => List(a)
  case y::ys => if (a > y) y::insert(a, ys) else a::y::ys
}

DHG 回答“总是喜欢左折叠”。但是，Scala 中的编程有一个相反的例子。

def flattenLeft[T](xss: List[List[T]]) = (List[T]() /: xss) (_ ::: ) 

def flattenRight[T](xss: List[List[T]]) = (xss :~List[T]()) ( ::: _)

我想这是因为在这种情况下 flattenRight 是通过一个函数调用实现的，而 flattenLeft 是通过 n 个函数调用实现的？

4

1 回答 1

4

因此，对于 a List，由于需要进行头部操作，foldLeft因此是自然的选择。这样，您就可以从左到右处理列表，始终占据主导地位。如您所见，它的实现 (on LinearSeqOptimized) 只使用了一个 while 循环并遍历一次。

override /*TraversableLike*/
def foldLeft[B](z: B)(f: (B, A) => B): B = {
  var acc = z
  var these = this
  while (!these.isEmpty) {
    acc = f(acc, these.head)
    these = these.tail
  }
  acc
}

'foldRight' 似乎是 O(n^2) 因为，为了获取最后一个元素，你必须遍历n次的n 个元素，但库实际上为你优化了这个。在幕后，是这样实现的（也在）：List foldRightLinearSeqOptimized

def foldRight[B](z: B)(f: (A, B) => B): B =
  if (this.isEmpty) z
  else f(head, tail.foldRight(z)(f))

正如你所看到的，这个函数是通过递归调用foldRight尾部，将每个头部保持在堆栈中，并在到达最后一个元素后以相反的顺序将函数应用于每个头部来构造的。

于 2012-05-07T00:47:11.983 回答