0

Scalaでマージソートを使用して反転カウントを試みていますが、メソッドの1つがパラメーターとして空のリストを渡すためにIndexOutOfBoundsExceptionをスローしているため、進行できません。

def sortAndCountInv(il: List[Int]): Int = {

def mergeAndCountInv(ll: List[Int], rl: List[Int]): (List[Int], Int) = {
  println("mergeAndCountInv : ")
  if (ll.isEmpty && !rl.isEmpty) (rl, 0)
  if (rl.isEmpty && !ll.isEmpty) (ll, 0)
  if (ll.isEmpty && rl.isEmpty) (List(), 0)
  if (ll(0) <= rl(0)) {

    val x = mergeAndCountInv(ll.tail, rl)//*passing empty list, ll.tail invoking IndexOutOfBoundsException*//


    (ll(0) :: x._1, x._2)
  } else {
    val y = mergeAndCountInv(ll, rl.tail)
    (rl(0) :: y._1, 1 + y._2)
  }
}

def sortAndCountInv(l: List[Int], n: Int): (List[Int], Int) = {
  if (n <= 1) (l, 0)
  else {
    val two_lists = l.splitAt(n / 2)
    val x = sortAndCountInv(two_lists._1, n / 2)
    val y = sortAndCountInv(two_lists._2, n / 2)
    val z = mergeAndCountInv(x._1, y._1)
    (z._1, x._2 + y._2 + z._2)
  }
}

val r = sortAndCountInv(il, il.length)
println(r._1.take(100))
r._2

}

4

2 に答える 2

2

この種のことは、多くの場合、パターンマッチングを使用してより明確に表現されます。

  def mergeAndCountInv(ll: List[Int], rl: List[Int]): (List[Int], Int) =
    (ll, rl) match {
      case (Nil, Nil) => (Nil, 0)

      case (Nil, _)   => (rl, 0)

      case (_, Nil)   => (ll, 0)

      case (ll0 :: moreL, rl0 :: moreR) =>
        if (ll0 <= rl0) {
          val x = mergeAndCountInv(moreL, rl)
          (ll0 :: x._1, x._2)
        }
        else {
          val y = mergeAndCountInv(ll, moreR)
          (rl0 :: y._1, 1 + y._2)
        }
    }
于 2013-01-31T04:30:11.263 に答える
1

else左または右、あるいは両方のリストが空であるかどうかを確認するmergeAndCountInvときに、を使用することをお勧めします。戻る代わりに、計算でタプルを無視するためです。

于 2013-01-31T01:34:00.333 に答える