Kotlin函數(shù)式編程經(jīng)典案例

望宸閣

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

image.png

集合操作

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

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

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

var seleteTen = students.filter { it.passing && it.averageGrade > 4 }
            .sortedBy { it.averageGrade }
            .take(10)
            .sortedWith(compareBy({it.surname}, {it.name}))
  1. 首先必須及格并且平均成績 > 4
  2. 根據(jù)平均成績排序(默認(rèn)從小到大)
  3. 從排好序的學(xué)生中選擇前10個(gè)
  4. 將這10個(gè)學(xué)生根據(jù)姓排序，姓一樣的話再根據(jù)名排序

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

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)或者稱作2S，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}}。

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

我們要通過觀察來發(fā)現(xiàn)規(guī)律，比如對于冪集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形成的集合。方法來了：先取出一個(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è)問題，因?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() } }
    }
}

只能對集合才能求冪集，那么我們可以使用Kotlin的一個(gè)特性：擴(kuò)展函數(shù)，我們對集合類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)存中，對于很大的集合用遞歸的方法求其冪集的話肯定會(huì)出現(xiàn)堆棧溢出的問題。

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

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

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ù)就是2n，在[0，2n)的整數(shù)區(qū)間上任取一個(gè)值x，x的二進(jìn)制表示可以用來表示S的一個(gè)子集：對于x的第i位，如果為1，則此子集包含S的第i個(gè)元素，否則不包含。因此，只要遍歷[0，2n)的整數(shù)區(qū)間，就能列舉出S的所有子集，這些子集的集合就是S的冪集。

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

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

把這8個(gè)集合組合起來的結(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}}就是最終的冪集。

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

快速排序

我們將實(shí)現(xiàn)Quicksort(快速排序)算法。快排很簡單：我們從源列表中挑選一個(gè)哨兵元素pivot，對元素小于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]

這代碼真是比java簡單太多了，而且易讀，這就是函數(shù)式編程的美。
image.png

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

如果你想要一個(gè)高度優(yōu)化的算法，那么可以使用Java標(biāo)準(zhǔn)庫。它是根據(jù)不同情形使用不同的算法，效率更高。效率究竟有多高？我們來比較兩個(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倍。對大列表來說，它有同樣的可伸縮性。通常情況下，結(jié)果會(huì)有0.1ms到0.2ms的誤差。算法更加簡單易讀，因此在一些情況下我們可以使用簡單易讀的算法，雖然性能可能不是最優(yōu)的。

如果你對Kotlin感興趣，可以參加Kotlin Academy。它是致力于Kotlin的開放社區(qū)。我在我的Twitter也發(fā)布很多資源。我的聯(lián)系方式：@marcinmoskala。如果你需要我的幫助，請記?。?a target="_blank" rel="nofollow">I am open for consultations。

翻譯自原文地址。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容