1

insertSortRightはinsert（）の引数の1つとしてList.last（O（n））を呼び出す必要があるため、insertSortRightはinsertSortLeftよりも効率が悪いと感じます。ここで、insertSortLeftはList.head（O（1））を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は1回の関数呼び出しで達成されるのに対し、flattenLeftはn個の関数呼び出しで達成されるためだと思いますか？

4

1 に答える 1

4

したがって、Listヘッド操作が必要なため、 afoldLeftは自然な選択です。このようにして、リストを左から右に処理し、常に頭を取ります。ご覧のとおり、その実装 ( on LinearSeqOptimized) は、単純に while ループを使用して 1 回トラバースします。

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 に答える