1

Scalaで解決しようとしている別のcodechefの問題に遭遇しました。問題文は次のとおりです。

ステップフォード通りは行き止まりの通りでした。ステップフォード ストリートの家は、裕福な億万長者によって購入されました。彼らは、通りに沿って進むにつれて、建物の高さが急速に増加するように、それらを大幅に変更しました。ただし、すべての億万長者が平等に作成されたわけではありません。この傾向に従うことを拒否し、家を元の高さに保つ人もいました。結果として生じる高さの進行はかくして妨げられた。ビバリーヒルズ市営企業は、最も注文の多い通りを特定するコンテストを発表しました。最も秩序のある通りの基準は次のように設定されました: 検討中の家よ​​りも通りの後ろに高さが低い家が存在する場合、そのペア (現在の家、後の家) は無秩序指数の 1 点としてカウントされます。ストリート。後の家が現在の家に隣接している必要はありません。注: 通りにある 2 つの家が同じ高さになることはありません。たとえば、入力の場合: 1 2 4 5 3 6 ペア (4,3)、(5,3) は無秩序なペアを形成します。したがって、この配列の無秩序性指数は 2 です。無秩序性を判断するための基準は複雑であるため、BHMC はプロセスを自動化するためにあなたの助けを求めています。道路の無秩序指数を計算する効率的なプログラムを作成する必要があります。

入力出力の例は次のとおりです。

入力: 1 2 4 5 3 6

出力: 2

(4,3) と (5,3) の 2 つのペアのため、出力は 2 です。

この問題を解決するには、MergeSort のバリアントを使用する必要があると考えました。左の要素が右の要素よりも大きい場合は 1 ずつ増加します。

私のscalaコードは次のとおりです。

    def dysfunctionCalc(input:List[Int]):Int = {
        val leftHalf = input.size/2
        println("HalfSize:"+leftHalf)

        val isOdd = input.size%2
        println("Is odd:"+isOdd)

        val leftList = input.take(leftHalf+isOdd)
        println("LeftList:"+leftList)

        val rightList = input.drop(leftHalf+isOdd)
        println("RightList:"+rightList)

        if ((leftList.size <= 1) && (rightList.size <= 1)){
                println("Entering input where both lists are <= 1")
                             if(leftList.size == 0 || rightList.size == 0){
                                      println("One of the lists is less than 0")
                                        0
                                }
                             else if(leftList.head > rightList.head)1 else 0
     }       
     else{
             println("Both lists are greater than 1")
             dysfunctionCalc(leftList) + dysfunctionCalc(rightList)
     }
   }

まず、私のロジックが間違っています。マージ段階がなく、ベースケースの結果をスタックに浸透させて他の値と比較する最良の方法が何であるかわかりません。また、この問題を解決するために再帰を使用することは、最適な方法ではない可能性があります。大きなリストの場合、スタックを爆破する可能性があるからです。また、私のコードにもスタイル上の問題がある可能性があります。

誰かが他の欠陥とこの問題を解決する正しい方法を指摘できれば幸いです.

ありがとう

4

5 に答える 5

2

リストを3つの部分に分割するとします。検討しているアイテム、左側のアイテム、右側のアイテムです。さらに、左側のものがソートされたセットにあると仮定します。ここで、リストをウォークスルーして、アイテムを「右」から「検討済み」に、「検討済み」から「左」に移動する必要があります。各ポイントで、アイテムよりも大きい、ソートされたセットのサブセットのサイズを確認します。一般に、サイズのルックアップはO(log(N))、add-elementと同様に実行できます（たとえば、Red-BlackまたはAVLツリーを使用）。だからあなたはO(N log N)パフォーマンスを持っています。

ここで問題となるのは、これをScalaで効率的に実装する方法です。Scalaには、TreeSetソートされたセットに使用される赤黒木があり、実装は実際には非常に単純です（ここでは末尾再帰形式）。

import collection.immutable.TreeSet
final def calcDisorder(xs: List[Int], left: TreeSet[Int] = TreeSet.empty, n: Int = 0): Int = xs match {
  case Nil => n
  case x :: rest => calcDisorder(rest, left + x, n + left.from(x).size)
}

残念ながら、left.from(x).size時間がかかりO(N)（私は信じています）、2次実行時間が発生します。それは良くありません-あなたが必要とするのはIndexedTreeSetでできることですindexOf(x)（O(log(n))そしてそれから反復しn + left.size - left.indexOf(x) - 1ます）。独自の実装を構築することも、Webで見つけることもできます。たとえば、Java用に正確に正しいことを行うもの（ここではAPI ）を見つけました。

ちなみに、マージソートを行う際の問題は、累積的に簡単に作業できないことです。ペアをマージすると、それがどの程度故障しているかを追跡できます。しかし、3番目のリストにマージするときは、他の両方のリストに対してどのように順序が狂っているのかを確認する必要があります。これにより、分割統治戦略が台無しになります。（追跡していれば直接計算できる不変条件があるかどうかはわかりません。）

于 2012-04-26T00:51:23.773 に答える
2

ここに私の試みがあります.MergeSortを使用していませんが、問題を解決しているようです:

def calcDisorderness(myList:List[Int]):Int = myList match{
  case Nil => 0
  case t::q => q.count(_<t) + calcDisorderness(q)
}

scala> val 入力 = List(1,2,4,5,3,6)

入力: List[Int] = List(1, 2, 4, 5, 3, 6)

scala> calcDisorderness(入力)

res1: 整数 = 2

問題は、複雑さを軽減する方法があるかどうかです。

編集：同じ関数の末尾再帰バージョンと、関数引数のデフォルト値のクールな使用法。

def calcDisorderness(myList:List[Int], disorder:Int=0):Int = myList match{
  case Nil => disorder
  case t::q => calcDisorderness(q, disorder + q.count(_<t))
}
于 2012-04-25T19:13:53.247 に答える
1

Merge Sort に基づく別のソリューション。非常に高速: FP や for ループはありません。

def countSwaps(a: Array[Int]): Count = {
    var swaps: Count = 0

    def mergeRun(begin: Int, run_len: Int, src: Array[Int], dst: Array[Int]) = {
        var li = begin
        val lend = math.min(begin + run_len, src.length)
        var ri = begin + run_len
        val rend = math.min(begin + run_len * 2, src.length)

        var ti = begin
        while (ti < rend) {
            if (ri >= rend) {
                dst(ti) = src(li); li += 1
                swaps += ri - begin - run_len
            } else if (li >= lend) {
                dst(ti) = src(ri); ri += 1
            } else if (a(li) <= a(ri)) {
                dst(ti) = src(li); li += 1
                swaps += ri - begin - run_len
            } else {
                dst(ti) = src(ri); ri += 1
            }
            ti += 1
        }
    }

    val b = new Array[Int](a.length)
    var run = 0
    var run_len = 1
    while (run_len < a.length) {
        var begin = 0
        while (begin < a.length) {
            val (src, dst) = if (run % 2 == 0) (a, b) else (b, a)
            mergeRun(begin, run_len, src, dst)
            begin += run_len * 2
        }
        run += 1
        run_len *= 2
    }

    swaps
}

上記のコードを関数型スタイルに変換します: 可変変数なし、ループなし。すべての再帰は末尾呼び出しであるため、パフォーマンスは良好です。

def countSwaps(a: Array[Int]): Count = {
    def mergeRun(li: Int, lend: Int, rb: Int, ri: Int, rend: Int, di: Int, src: Array[Int], dst: Array[Int], swaps: Count): Count = {
        if (ri >= rend && li >= lend) {
            swaps
        } else if (ri >= rend) {
            dst(di) = src(li)
            mergeRun(li + 1, lend, rb, ri, rend, di + 1, src, dst, ri - rb + swaps)
        } else if (li >= lend) {
            dst(di) = src(ri)
            mergeRun(li, lend, rb, ri + 1, rend, di + 1, src, dst, swaps)
        } else if (src(li) <= src(ri)) {
            dst(di) = src(li)
            mergeRun(li + 1, lend, rb, ri, rend, di + 1, src, dst, ri - rb + swaps)
        } else {
            dst(di) = src(ri)
            mergeRun(li, lend, rb, ri + 1, rend, di + 1, src, dst, swaps)
        }
    }

    val b = new Array[Int](a.length)

    def merge(run: Int, run_len: Int, lb: Int, swaps: Count): Count = {
        if (run_len >= a.length) {
            swaps
        } else if (lb >= a.length) {
            merge(run + 1, run_len * 2, 0, swaps)
        } else {
            val lend = math.min(lb + run_len, a.length)
            val rb = lb + run_len
            val rend = math.min(rb + run_len, a.length)
            val (src, dst) = if (run % 2 == 0) (a, b) else (b, a)
            val inc_swaps = mergeRun(lb, lend, rb, rb, rend, lb, src, dst, 0)
            merge(run, run_len, lb + run_len * 2, inc_swaps + swaps)
        }
    }

    merge(0, 1, 0, 0)
}
于 2012-06-24T22:48:41.090 に答える
1

マージソートに基づくソリューション。超高速ではなく、潜在的な速度低下は「xs.length」にある可能性があります。

def countSwaps(a: Array[Int]): Long = {
    var disorder: Long = 0

    def msort(xs: List[Int]): List[Int] = { 
        import Stream._
        def merge(left: List[Int], right: List[Int], inc: Int): Stream[Int] = {
            (left, right) match {
                case (x :: xs, y :: ys) if x > y =>
                    cons(y, merge(left, ys, inc + 1))
                case (x :: xs, _) => {
                    disorder += inc
                    cons(x, merge(xs, right, inc))
                }
                case _ => right.toStream
            }
        }

        val n = xs.length / 2 
        if (n == 0)
            xs 
        else { 
            val (ys, zs) = xs splitAt n 
            merge(msort(ys), msort(zs), 0).toList
        } 
    }

    msort(a.toList)
    disorder
}
于 2012-06-22T19:29:51.667 に答える
0

キーは、リストを一連の昇順シーケンスに分割することだと私には思えます。たとえば、例は (1 2 4 5)(3 6) に分割されます。最初のリストのどの項目もペアを終了できません。次に、これら 2 つのリストを逆方向にマージします。

  • 6 > 5 なので、6 はどのペアにもなりません。
  • 3 < 5 なのでペア
  • 3 < 4 なのでペア
  • 3 > 2 なので、これで完了です

このようなシーケンスを 2 つ以上処理する方法の定義からは明確ではありません。

于 2012-04-25T18:23:27.827 に答える