望宸閣

Kotlin的一個(gè)很好的特性是支持函數(shù)式編程光坝，本文分為集合操作、冪集和排序三部分來(lái)分析下Kotlin函數(shù)式編程。

image.png

集合操作

假設(shè)我們有一個(gè)學(xué)生的模型類：

data class Student(
        val name: String,
        val surname: String,
        val passing: Boolean,
        val averageGrade: Double // > 4
)

包含姓糠惫、名、是否及格钉疫、平均成績(jī)四個(gè)屬性硼讽。我們從所有學(xué)生中篩選出成績(jī)最好的10個(gè)人：

var seleteTen = students.filter { it.passing && it.averageGrade > 4 }
            .sortedBy { it.averageGrade }
            .take(10)
            .sortedWith(compareBy({it.surname}, {it.name}))

1. 首先必須及格并且平均成績(jī) > 4
2. 根據(jù)平均成績(jī)排序(默認(rèn)從小到大)
3. 從排好序的學(xué)生中選擇前10個(gè)
4. 將這10個(gè)學(xué)生根據(jù)姓排序，姓一樣的話再根據(jù)名排序

如果我們不根據(jù)姓名排序陌选，而是保持原來(lái)的順序不變理郑，我們可以添加索引保持順序不變：

var obtainOrder = students.filter { it.passing && it.averageGrade > 4.0 }
            .withIndex() // 1
            .sortedBy { (_, s) -> s.averageGrade } // 2
            .take(10)
            .sortedBy { (i, _) -> i } // 3
            .map { (_, s) -> s } // 4

1. 為每個(gè)學(xué)生添加當(dāng)前的索引
2. 使用之前我們需要析構(gòu)值和索引
3. 根據(jù)索引排序
4. 刪除索引并僅保持值

完整代碼：

fun main(vararg args: String) {
    var zzh = Student("zzh", "zzh", true, 100.0)
    var zyw = Student("zyw", "zyw", true, 200.0)
    var lj = Student("lj", "lj", true, 120.0)
    var lcg = Student("lcg", "lcg", true, 110.0)
    var zzy = Student("zzy", "zzy", true, 400.0)
    var fgt = Student("fgt", "fgt", true, 123.0)
    var efr = Student("efr", "efr", true, 118.0)
    var lok = Student("lok", "lok", true, 191.0)
    var hgt = Student("hgt", "hgt", true, 864.0)
    var jnd = Student("jnd", "jnd", true, 765.0)
    var tpc = Student("tpc", "tpc", true, 491.0)
    var hpz = Student("hpz", "hpz", true, 691.0)

    var fhy = Student("fhy", "fhy", false, 1.0)
    var yly = Student("yly", "yly", false, 00.0)
    var weg = Student("weg", "weg", false, 2.2)
    var tyu = Student("tyu", "tyu", false, 2.5)
    var qwe = Student("qwe", "qwe", false, 3.2)
    var oiu = Student("oiu", "oiu", false, 1.6)
    var iuh = Student("iuh", "iuh", false, 3.1)
    var pnh = Student("pnh", "pnh", false, 1.9)

    var students = arrayListOf<Student>(zzh, zyw, lj, lcg, zzy, fgt, efr, lok, hgt, jnd, tpc, hpz,
            fhy, yly, weg, tyu, qwe, oiu, iuh, pnh)

    var seleteTen = students.filter { it.passing && it.averageGrade > 4 }
            .sortedBy { it.averageGrade }
            .take(10)
            .sortedWith(compareBy({it.surname}, {it.name}))
//            .toList()
    seleteTen.forEach {
        println(it)
    }

    println("----------------")
    var obtainOrder = students.filter { it.passing && it.averageGrade > 4.0 }
            .withIndex() // 1
            .sortedBy { (_, s) -> s.averageGrade } // 2
            .take(10)
            .sortedBy { (i, _) -> i } // 3
            .map { (_, s) -> s } // 4
    obtainOrder.forEach {
        println(it)
    }
}

data class Student(
        val name: String,
        val surname: String,
        val passing: Boolean,
        val averageGrade: Double // > 4
)

image.png

冪集

高中數(shù)學(xué)我們學(xué)習(xí)了集合的概念蹄溉，應(yīng)該還記得有個(gè)冪集(Powerset)的知識(shí)點(diǎn)：所謂冪集，就是原集合S中所有的子集(包括全集和空集)構(gòu)成的一個(gè)集合P(S)或者稱作2^S您炉，P(S) = { U | U ? S }柒爵。

假設(shè)我們有這樣的一個(gè)集合：S = {1,2,3}，那么S的冪集就是：P(S) = {{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}赚爵。

問(wèn)題來(lái)啦棉胀，怎么使用Kotlin代碼實(shí)現(xiàn)求冪集的算法呢？如果你想挑戰(zhàn)自己冀膝，那么請(qǐng)停止閱讀本文唁奢，自己實(shí)現(xiàn)這個(gè)算法之后再來(lái)繼續(xù)閱讀。

我們要通過(guò)觀察來(lái)發(fā)現(xiàn)規(guī)律窝剖，比如對(duì)于冪集P(S)的每一個(gè)不可拆分的元素比如1麻掸，所有包含這個(gè)元素的集合是{1}, {1,2}, {1,3}, {1,2,3}，不包含這個(gè)元素的集合是：{}, {2}, {3}, {2,3}赐纱。

注意第二個(gè)集合是集合{2,3}的冪集脊奋，第一個(gè)集合是這個(gè)冪集的每個(gè)元素加上1形成的集合。方法來(lái)了：先取出一個(gè)元素e疙描，計(jì)算出其余元素組成的集合的冪集A诚隙，將A內(nèi)的每個(gè)集合加上元素e形成集合B，集合A與B的并集就是最終我們要求的冪集起胰。

fun <T> powerset(set: Set<T>): Set<Set<T>> {
    val first = set.first()
    val powersetOfRest = powerset(set.drop(1).toSet())
    return powersetOfRest.map { it + first }.toSet() + powersetOfRest
}

上面的代碼還有個(gè)問(wèn)題久又，因?yàn)榈谝恍械膄irst()方法不允許空集合調(diào)用，否則會(huì)拋出異常效五，那么我們就定義空集合的冪集還是空集合：

fun <T> powerset(set: Set<T>): Set<Set<T>> {
    return if (set.isEmpty()) setOf(setOf())
    else {
        val first = set.first()
        val powersetOfRest = powerset(set.drop(1).toSet())
        powersetOfRest.map { it + first }.toSet() + powersetOfRest
    }
}

image.png

我們分析下算法流程地消，比如要計(jì)算集合{1,2,3}的冪集：

1. powerset({1,2,3}) = powerset({2,3}) + powerset({2,3}).map { it + 1 }
2. powerset({2,3}) = powerset({3}) + powerset({3}).map { it + 2}
3. powerset({3}) = powerset({}) + powerset({}).map { it + 3}
4. powerset({}) = {{}}
5. powerset({3}) = {{}, {3}}
6. powerset({2,3}) = {{}, {3}} + {{2}, {2, 3}} = {{}, {2}, {3}, {2, 3}}
7. powerset({1,2,3}) = {{}, {2}, {3}, {2, 3}} + {{1}, {1, 2}, {1, 3}, {1, 2, 3}} = {{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}

上面的代碼不夠kotlinc，什么叫做kotlinc火俄？我們使用Kotlin提供的操作符let進(jìn)行優(yōu)化犯建，不懂let操作符的同學(xué)可以看下這篇文章，下面優(yōu)化后的代碼就比較kotlinc瓜客，感受下：

fun <T> powerset(set: Set<T>): Set<Set<T>> {
    return if (set.isEmpty()) setOf(setOf())
    else {
        powerset(set.drop(1).toSet())
                .let { it + it.map { it + set.first() } }
    }
}

只能對(duì)集合才能求冪集适瓦，那么我們可以使用Kotlin的一個(gè)特性：擴(kuò)展函數(shù)，我們對(duì)集合類Set添加擴(kuò)展函數(shù)：

fun <T> Collection<T>.powerset(): Set<Set<T>> =
        if (isEmpty()) setOf(setOf())
        else drop(1)
                .powerset()
                .let { it + it.map { it + first() } }

眾所周知谱仪，上面的遞歸方法有很大的風(fēng)險(xiǎn)玻熙，因?yàn)槊看芜f歸的上一次遞歸都要保存在內(nèi)存中，對(duì)于很大的集合用遞歸的方法求其冪集的話肯定會(huì)出現(xiàn)堆棧溢出的問(wèn)題疯攒。

Kotlin支持一種叫做尾遞歸的編程風(fēng)格嗦随。這允許一些通常意義上的使用遞歸函數(shù)替代循環(huán)的算法，當(dāng)一個(gè)函數(shù)被tailrec修飾并遇到符合的形式，編譯器會(huì)優(yōu)化遞歸枚尼，替代為一個(gè)快速并有效率的基于循環(huán)的版本來(lái)避免堆棧溢出的風(fēng)險(xiǎn)贴浙。

因此，我們需要用尾遞歸進(jìn)行優(yōu)化署恍。tailrec要求函數(shù)調(diào)用自身必須是最后才能做的事情崎溃，否則tailrec這個(gè)關(guān)鍵字就形同虛設(shè)并會(huì)有語(yǔ)法警告，而且tailrec不能與 try/cathch/finally塊一起使用盯质，這樣的話其實(shí)內(nèi)存只保存最后一次的迭代袁串，不存在堆棧溢出的問(wèn)題：

fun <T> Collection<T>.powerset(): Set<Set<T>> =
        powerset(this, setOf(setOf()))

private tailrec fun <T> powerset(left: Collection<T>, acc: Set<Set<T>>): Set<Set<T>> =
        if (left.isEmpty()) acc
        else powerset(left.drop(1), acc + acc.map { it + left.first() })

求冪集還有第二種方法，利用冪集和二進(jìn)制之間的關(guān)系：

fun <T> Collection<T>.findPowersetByBinary(): Set<Set<T>> =
        mutableSetOf(setOf<T>()).apply {
            for (i in 0 until Math.pow(2.0, this@findPowersetByBinary.size.toDouble()).toInt()) {
                mutableSetOf<T>().run {
                    var temp = i
                    var index = 0
                    do {
                        takeIf { temp and 1 == 1 }?.run {
                            add(this@findPowersetByBinary.elementAt(index))
                        }
                        temp = temp shr 1
                        index++
                    } while (temp > 0)
                    this@apply.add(this)
                }
            }
        }

上面代碼由兩層循環(huán)完成呼巷。假設(shè)集合S的個(gè)數(shù)為n囱修，那么它的冪集元素的個(gè)數(shù)就是2ⁿ，在[0王悍，2ⁿ)的整數(shù)區(qū)間上任取一個(gè)值x破镰，x的二進(jìn)制表示可以用來(lái)表示S的一個(gè)子集：對(duì)于x的第i位，如果為1压储，則此子集包含S的第i個(gè)元素啤咽，否則不包含。因此渠脉，只要遍歷[0，2ⁿ)的整數(shù)區(qū)間瓶佳，就能列舉出S的所有子集芋膘，這些子集的集合就是S的冪集。

我們分析下算法流程霸饲，比如要計(jì)算集合{1,2,3}的冪集为朋，遍歷[0，2³)的整數(shù)區(qū)間：

• 0 ----> 對(duì)應(yīng)的二進(jìn)制0 ----> {}
• 1 ----> 對(duì)應(yīng)的二進(jìn)制1 ----> {1}
• 2 ----> 對(duì)應(yīng)的二進(jìn)制10 ----> {2}
• 3 ----> 對(duì)應(yīng)的二進(jìn)制11 ----> {1,2}
• 4 ----> 對(duì)應(yīng)的二進(jìn)制100 ----> {3}
• 5 ----> 對(duì)應(yīng)的二進(jìn)制101 ----> {1,3}
• 6 ----> 對(duì)應(yīng)的二進(jìn)制110 ----> {2,3}
• 7 ----> 對(duì)應(yīng)的二進(jìn)制111 ----> {1,2,3}

把這8個(gè)集合組合起來(lái)的結(jié)果{{}, {2}, {3}, {2, 3}} + {{1}, {1, 2}, {1, 3}, {1, 2, 3}} = {{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}就是最終的冪集厚脉。

代碼來(lái)自KotlinDiscreteMathToolkit庫(kù)习寸，它提供了離散數(shù)學(xué)很多有用的工具。

快速排序

我們將實(shí)現(xiàn)Quicksort(快速排序)算法傻工∠枷快排很簡(jiǎn)單：我們從源列表中挑選一個(gè)哨兵元素pivot，對(duì)元素小于pivot的列表A和元素不小于pivot的列表B這兩個(gè)列表分別進(jìn)行快排中捆，最后的A + povit + B就是排好序的列表：

fun <T : Comparable<T>> List<T>.quickSort(): List<T> =
        if(size < 2) this
        else {
            val pivot = first()
            val (smaller, greater) = drop(1).partition { it <= pivot}
            smaller.quickSort() + pivot + greater.quickSort()
        }
// Usage
listOf(2,5,1).quickSort() // [1,2,5]

image.png

這個(gè)方法的一個(gè)注意點(diǎn)是算法性能殴蓬，必須承認(rèn)算法性能需要優(yōu)化，但是算法很短而且易讀蟋滴。

如果你想要一個(gè)高度優(yōu)化的算法染厅，那么可以使用Java標(biāo)準(zhǔn)庫(kù)痘绎。它是根據(jù)不同情形使用不同的算法，效率更高肖粮。效率究竟有多高孤页？我們來(lái)比較兩個(gè)算法：

val r = Random()
listOf(100_000, 1_000_000, 10_000_000)
    .asSequence()
    .map { (1..it).map { r.nextInt(1000000000) } }
    .forEach { list: List<Int> ->
        println("Java stdlib sorting of ${list.size} elements took ${measureTimeMillis { list.sorted() }}")
        println("quickSort sorting of ${list.size} elements took ${measureTimeMillis { list.quickSort() }}")
    }

在我的機(jī)器得到以下結(jié)果：

Java stdlib sorting of 100000 elements took 83
quickSort sorting of 100000 elements took 163
Java stdlib sorting of 1000000 elements took 558
quickSort sorting of 1000000 elements took 859
Java stdlib sorting of 10000000 elements took 6182
quickSort sorting of 10000000 elements took 12133

可以看到quickSort方法慢了2倍。對(duì)大列表來(lái)說(shuō)尿赚，它有同樣的可伸縮性散庶。通常情況下，結(jié)果會(huì)有0.1ms到0.2ms的誤差凌净。算法更加簡(jiǎn)單易讀悲龟，因此在一些情況下我們可以使用簡(jiǎn)單易讀的算法，雖然性能可能不是最優(yōu)的冰寻。

如果你對(duì)Kotlin感興趣须教，可以參加Kotlin Academy。它是致力于Kotlin的開(kāi)放社區(qū)斩芭。我在我的Twitter也發(fā)布很多資源轻腺。我的聯(lián)系方式：@marcinmoskala。如果你需要我的幫助划乖，請(qǐng)記妆嵫：I am open for consultations。

翻譯自原文地址琴庵。