4

KotlinでO(n)時間で純粋関数型プログラミングスタイルの数値配列のすべてのプレフィックス合計を計算することは可能ですか?

純粋な関数型プログラミングとは、 _Collections,ktmapで、reduce、fold、sumなどのコレクションのみに関数型プログラミング拡張関数を使用できるようにすることを意味しますが、通常のループ、可変変数別名などの状態と可変データの変更を含む従来の命令型プログラミング方法を使用できます。s、および変更可能な配列は許可されていません。(これはウィキペディアの定義に準拠していると思います)var

より具体的に言うと、O(n) 時間で実行される命令型プログラミングで書かれた達成したいことの一例と、O(n^2) 時間で実行される関数型プログラミングで書かれた別の例があります。

fun prefixSumsImperative(numbers: IntArray): IntArray {
    val prefixSums = IntArray(numbers.size)
    var prefixSum = 0
    for ((i, number) in numbers.withIndex()) {
        prefixSum += number
        prefixSums[i] = prefixSum
    }
    return prefixSums
}

fun prefixSumsFunctionalONSquared(numbers: IntArray): IntArray =
    (0 until numbers.size).map { numbers.take(it).sum() }.toIntArray()
4

3 に答える 3