【Kotlin】計測：シーザー暗号の実装の違いによる速度

記事「Kotlin でシーザー暗号をつくってみた」へのコメントで、
シーザー暗号を次の2つの実装方針で実装してみた。

• 実装のしやすさ重視
• 実行効率も考慮

しかし実際にどれくらい違いがあるのか。
計測してみた。

計測対象

前述したコメントでの2実装に、

• Sequence を使うとどうか
• joinToString と fold だけを比較するとどうか

をするための2実装を加えた、次の4関数を計測対象とした。

const val SHIFT_COUNT = 13

fun encrypt_map_join(plainText: String): String =
    plainText.map { it - SHIFT_COUNT }.joinToString("")

fun encrypt_seq_map_join(plainText: String): String =
    plainText.asSequence().map { it - SHIFT_COUNT }.joinToString("")

fun encrypt_map_fold(plainText: String): String =
    plainText.map { it - SHIFT_COUNT }.fold(StringBuilder()) { acc, c ->
        acc.append(c)
    }.toString()

fun encrypt_fold(plainText: String): String =
    plainText.fold(StringBuilder()) { acc, c ->
        acc.append(c - SHIFT_COUNT)
    }.toString()

なお簡単のためシフト量は固定値とした。

計測方法

各関数を1000回繰り返す所要時間を計測。
それを計測対象である4関数に対して順番に行う。
その計測を1000回行い、
その中央値を結果とする。

計測に用いたコード

import kotlin.reflect.KCallable
import kotlin.system.measureTimeMillis

fun main() {
    printMeasuredMedian(
        encryptList = listOf(
            ::encrypt_map_join,
            ::encrypt_seq_map_join,
            ::encrypt_map_fold,
            ::encrypt_fold
        ),
        plainText = createPlainText(1000),
        repeatCount = 1000,
        measureCount = 100
    )
}

/**
 * 指定された長さの文字列を生成する。
 *
 * @param length 生成する文字列の長さ。
 * @return 生成された文字列。
 */
fun createPlainText(length: Int): String {
    return (0 until length).map {
        (it % Char.MAX_VALUE.toInt())
            .toChar()
    }.toString()
}

/**
 * 指定された各関数の名前と、
 * 各関数の処理時間の中央値を
 * 標準出力する。
 *
 * @param encryptList 処理時間を計測したい関数のリスト。
 * @param plainText 各関数の引数とする文字列。
 * @param repeatCount 一回の処理で関数を呼び出す回数。
 * @param measureCount 計測回数。
 */
fun <T> printMeasuredMedian(
    encryptList: List<T>,
    plainText: String,
    repeatCount: Int,
    measureCount: Int
) where T : (String) -> String,
        T : KCallable<String> {
    encryptList.map { it.name }.also {
        println(it)
    }
    measureMedian(encryptList, plainText, repeatCount, measureCount).also {
        println(it)
    }
}

fun measureMedian(
    encryptList: List<(String) -> String>,
    plainText: String,
    repeatCount: Int,
    measureCount: Int
): List<Long> {
    val measuredTimeList: List<MutableList<Long>> = encryptList.map { mutableListOf<Long>() }
    repeat(measureCount) {
        measure(encryptList, plainText, repeatCount)
            .forEachIndexed { index, time ->
                measuredTimeList[index] += time
            }
    }
    return measuredTimeList.map {
        it.median()
    }
}

fun Iterable<Long>.median(): Long =
    sorted().let { it[(it.size - 1) / 2] + it[it.size / 2] }.let { it / 2 }

fun measure(
    encryptList: List<(String) -> String>,
    plainText: String,
    repeatCount: Int
): List<Long> {
    return encryptList.map {
        measure(plainText, repeatCount, it)
    }
}

fun measure(
    plainText: String,
    repeatCount: Int,
    encrypt: (String) -> String
): Long {
    return measureTimeMillis {
        repeat(repeatCount) {
            encrypt(plainText)
        }
    }
}

計測結果

関数名	encrypt_map_join	encrypt_seq_map_join	encrypt_map_fold	encrypt_fold
処理時間	139	136	38	17

結論

• この程度の関数チェイン数であれば Sequence にしても効果がない。
• joinToString は遅い。
  fold に変えるだけで3倍以上高速化した。
• map を使わないようにすることでも2倍ほど高速化した。