再帰プログラム設計と注釈プログラム設計

再帰はプログラミングにおいて重要な役割を果たす.そこでデータを格納するアルゴリズムを用いることで性能を向上させることができる.コトリンはアノテーションの構築をサポートしていないが,これまで学んだ技術を用いて,表現力の強いアノテーション機能を容易に作成できる.
📌 再回帰のメリットとリスク
再帰を使用すると分割征服テクニックを使用できます.
クイックソート

fun sort(numbers: List<Int>): List<Int> =
    if (numbers.isEmpty())
        numbers
    else {
        val pivot = numbers.first()
        val tail = numbers.drop(1)
        val lessOrEqual = tail.filter { e -> e <= pivot }
        val larger = tail.filter { e -> e > pivot }
       
        sort(lessOrEqual) + pivot + sort(larger)
    }

println(sort(listOf(12, 5, 15, 12, 8, 19)))

sort()関数は,与えられた入力を2つの部分に分離し,それぞれ2つの部分を並べ替える.次に、最後に2つのソリューションを統合してソリューション全体を作成します.
再帰ソリューションの作成には努力が必要ですが、再帰は非常に表現力があります.
✍ factorialRec()

fun factorialRec(n: Int): BigInteger =
    if (n <= 0) 1.toBigInteger() else n.toBigInteger() * factorialRec(n - 1)
println(factorialRec(5))

factorialRec()関数は0より小さい値を受け入れると1を返し、0より大きい値を受け入れると所与の入力の自己再帰呼び出しの結果を返します.
次のように繰り返し文を使って実現することもできます.

fun factorialRec(n: Int) =
    (1..n).fold(BigInteger("1")) { product, e -> product * e.toBigInteger() }

fold()関数は「内部繰返し」のreduce()に類似した関数であり、アキメントロムダとともに初期値を受け入れる.
複雑な問題を解決する場合、可能であれば、再帰的な解決策を使用することは、重複した解決策を使用するよりも理解しやすい.しかし、再帰的には、重複ソリューションでは解決できない問題が発生します.再帰的にスタックが増加し、スタックが危険なレベルに達するとプログラムが展開されます.
✍ ERROR

println(factorialRec(500000)) //java.lang.StackOverflowError

これらの問題を解決するには、テールコール最適化が必要です.
📌 末尾呼び出しの最適化
factorialRec()は、再帰プロセスとしてコンパイルおよび実行される再帰プロセスです.再帰プロシージャを繰り返しプロシージャにコンパイルできる場合、スタックオーバーフローエラーを低減できます.
✍ tailrec

tailrec fun factorialRec(n: Int): BigInteger =
    if (n <= 0) 1.toBigInteger() else n.toBigInteger() * factorialRec(n - 1)

println(factorialRec(50000))

💻 しゅつりょく

factorial.kts:5:1: warning: a function is marked as tail-recursive but no tail calls are found
tailrec fun factorialRec(n: Int): BigInteger =
factorial.kts:6:58: warning: recursive call is not a tail call
    if (n <= 0) 1.toBigInteger() else n.toBigInteger() * factorialRec(n - 1)

taircキーワードを追加しましたが、まだ動作していません.
コールが最後の位置である場合にのみ、コトリンの復帰を繰り返し最適化することができる.

n.toBigInteger() * factorialRec(n - 1)

factorialRec(n-1)が最後に実行されると思うかもしれませんが、関数が戻る前に実行される演算は乗算です.この演算はfactorialRecの完了を待つ.したがって,各再帰呼び出しのスタックサイズが大きくなる.
最適化

tailrec fun factorial(n: Int, result: BigInteger = 1.toBigInteger()): BigInteger =
    if (n <= 0) result else factorial(n - 1, result * n.toBigInteger())
println(factorial(50000))

tairec最適化は、耳尾コール時にのみ機能します.tairecを使用するためにfactorial()の再帰呼び出しが最後に現れるfactorial()を書き換えた.
📌 注釈
アルゴリズムテクニック動的プログラミングでは,サブ問題を解決する解決策を再帰的に用いて問題全体を解決する.しかし、一般的な再帰とは異なり、ダイナミックプログラミングは再帰を使用するとサブ問題の結果を保存して再使用します.
くりかえしえんざん
フィボナッチ数列

fun fib(n: Int): Long = when (n) {
    0, 1 -> 1L
    else -> fib(n - 1) + fib(n - 2)
}

println(measureNanoTime { fib(40) }) // Abount 3 milliseconds
println(measureNanoTime { fib(45) }) //Abount than 4 seconds

fib()関数は、与えられた値が2未満の場合に1を返し、他の場合には2つの再帰関数呼び出しの結果を計算することによって結果を返す.
nが45の場合、実行時間はさらに増加する.以前の結果を覚えておけば、演算時間を大幅に減らすことができます.
Groovyの注記モード
メモを処理するには動的な動作が必要です.関数を呼び出すときは、キャッシュにデータがあるかどうかを確認し、データがない場合は関数を呼び出す必要があります.
これらの論理はRamda式を用いて実現できる.
関数にメソッドを入力する方法を用いてRamdaにmemoize()メソッドを作成する.
✍ memoize()

fun <T, R> ((T) -> (R)).memoize(): ((T) -> R) {
    val original = this
    val cache = mutableMapOf<T, R>()
    return { n: T -> cache.getOrPut(n) { original(n) } }
}

memoize()メソッドはjenericramda式に入力された.Jeneric Ramda式はT型のパラメータを受け入れ,R型の戻りを与える.memoize()関数の戻りタイプは、memoize()が入力されるメソッドのタイプと同じタイプのramda式です.
memorize()関数では、元の関数の参照を保存するためにローカル変数originに割り当てることができます.次に空のcaseを初期化します.
返される関数は、結果が存在するかどうかを確認するためにキャッシュをチェックします.キャッシュに結果がない場合は、演算を行い、結果を生成し、戻る前に保存します.結果が既に存在する場合は、保存した値を返します.

lateinit var fib: (Int) -> Long
fib = { n: Int ->
    when (n) {
        0, 1 -> 1L
        else -> fib(n - 1) + fib(n - 2)
    }
}.memoize()

println(measureTimeMillis { fib(40) })
println(measureTimeMillis { fib(15) })
println(measureTimeMillis { fib(500) })

lateinitを使用して、後でfib変数を初期化することをコトリンに通知します.memoiz()関数は、与えられたramda式を受け入れ、grandaをmemoiz()関数の変数の元に格納します.新しいRamda式を返します.
💻 しゅつりょく

0
0
0

演算時間が著しく短縮された.
memoiz()関数は、1つのパラメータのみを使用するすべての関数に使用できます.このソリューションにはメリットとデメリットがあります.その利点は,Ramda式を注釈に用いるため,コードがより簡潔であることである.ただし、fibを定義し、fibにramda式を割り当てる必要があります.
インクリメンタルゲートウェイを使用したコメント
水門

class Memoize<T, R>(val func: (T) -> (R)) {
    val cache = mutableMapOf<T, R>()
    operator fun getValue(thisRef: Any?, property: KProperty<*>) = { n: T ->
        cache.getOrPut(n) { func(n) }
    }
}

Dengit内部にはキャッシュがあり、元の関数にはfunc propertyがあります.その後、getValue()関数の値がキャッシュに含まれていない場合は、元の関数を実行するramda式を返します.

val fib: (Int) -> Long by Memoize { n: Int ->
    when (n) {
        0, 1 -> 1L
        else -> fib(n - 1) * (n - 2)
    }
}

メモ現在、アプリケーションはDelegateを使用するときにずっときれいになります.

println(measureTimeMillis { fib(40) })
println(measureTimeMillis { fib(15) })
println(measureTimeMillis { fib(500) })

💻 しゅつりょく

0
0
1

注記モードをダイナミックプログラミングに適用する
ダイナミックプログラミングは,メモ帳を用いて再帰呼び出しを非常に効率的にするアルゴリズムテクニックである.関数呼び出しのキャッシュと再利用の結果,動的プログラミングにより重複する再帰関数呼び出しが除去される.
動的プログラミングは、問題を最適化するために可能な解決策を再帰的に探すために使用される.
たとえば、長さは1.2...7日時点の価格は2、4、5、6、10、17、17ドル.最大収益を得る方法は何ですか?
✍ max price

val prices = mapOf(1 to 2, 2 to 4, 3 to 6, 4 to 7, 5 to 10, 6 to 17, 7 to 17)
val maxPrice: (Int) -> Int by Fibdelegate.Memoize { length: Int ->
    val priceAtLength = prices.getOrDefault(length, 0)
    (1 until length).fold(priceAtLength) { max, cutLength ->
        val cutPrice = maxPrice(cutLength) + maxPrice(length - cutLength)
        Math.max(cutPrice, max)
    }
}

価格変数はこの長さと価格を持つMULTABLE図です.maxPrice変数はランダを参照し、ランダはIntの長さを受け入れ、その長さの最高価格をIntに返します.maxprice変数呼び出しを中断したdelegateはfold()メソッドを使用して最大値を計算します.
1からlength-1までの範囲内のすべての切断長さのうち、以前に計算した最高値と棒を2つに切断することを選択し、切断長さとlength-cutlengthの場合の価格が高い.
長さが1～7の場合、maxPrice()関数を使用して各長さの最高価格を探します.
💻 しゅつりょく

For length 1 max price is 2
For length 2 max price is 4
For length 3 max price is 6
For length 4 max price is 8
For length 5 max price is 10
For length 6 max price is 17
For length 7 max price is 19

ソース:マルチファンクションエラープログラミング