Eine der großartigen Eigenschaften von Kotlin ist, dass es funktionale Programmierung unterstützt. Lassen Sie uns einen Blick darauf werfen und einige einfache, aber ausdrucksstarke Funktionen diskutieren, die in Kotlin geschrieben wurden.
Arbeiten Sie mit Sammlungen
Kotlin unterstützt die bequeme Arbeit mit Sammlungen. Es gibt viele verschiedene Funktionen. Angenommen, wir schaffen ein System für eine Universität. Wir müssen die besten Studenten finden, die ein Stipendium verdienen. Wir haben das folgende Student :
class Student( val name: String, val surname: String, val passing: Boolean, val averageGrade: Double )
Jetzt können wir die folgende Funktion aufrufen, um eine Liste der zehn besten Schüler zu erhalten, die alle Kriterien erfüllen:
students.filter { it.passing && it.averageGrade > 4.0 } // 1 .sortedBy { it.averageGrade } // 2 .take(10) // 3 .sortedWith(compareBy({ it.surname }, { it.name })) // 4
- Wir lassen nur Studenten, die die Prüfung bestanden haben, deren durchschnittliche Punktzahl mehr als 4,0 beträgt.
- Sortieren Sie sie nach der durchschnittlichen Punktzahl.
- Wir verlassen die ersten zehn Schüler.
- Sortieren Sie sie alphabetisch. Der Komparator vergleicht zuerst die Nachnamen, und wenn sie gleich sind, vergleicht er die Namen.
Was ist, wenn wir anstelle der alphabetischen Reihenfolge die ursprüngliche Reihenfolge der Schüler beibehalten müssen? Wir können dies mithilfe von Indizes tun:
students.filter { it.passing && it.averageGrade > 4.0 } .withIndex() // 1 .sortedBy { (i, s) -> s.averageGrade } // 2 .take(10) .sortedBy { (i, s) -> i } // 3 .map { (i, s) -> s } // 4
- Binden Sie den aktuellen Iterationsindex an jedes Element.
- Sortieren Sie nach der durchschnittlichen Punktzahl und lassen Sie die ersten zehn Schüler.
- Nochmals sortieren, aber jetzt nach Index.
- Wir löschen Indizes und lassen nur Studenten.
Dieses Beispiel zeigt, wie einfach und intuitiv die Arbeit mit Sammlungen in Kotlin ist.
Wenn Sie an einer Universität Algebra studiert haben, können Sie sich daran erinnern, was eine Obermenge ist. Für jede Menge ist ihre Obermenge die Menge aller ihrer Teilmengen, einschließlich der ursprünglichen Menge selbst und der leeren Menge. Zum Beispiel, wenn wir den folgenden Satz haben:
{1,2,3}
Das ist seine Obermenge:
{{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}
In der Algebra ist eine solche Funktion sehr nützlich. Wie setzen wir es um?
Wenn Sie sich selbst herausfordern möchten, hören Sie sofort auf zu lesen und versuchen Sie, dieses Problem selbst zu lösen.
Beginnen wir unsere Analyse mit einer einfachen Beobachtung. Wenn wir ein Element der Menge nehmen (zum Beispiel 1), hat die Supermenge eine gleiche Anzahl von Mengen mit diesem Element ({1}, {1,2}, {1,3}, {1,2,3}) und ohne es ({}, {2}, {3}, {2,3}).
Beachten Sie, dass die zweite Menge eine Supermenge ({2,3}) ist und die erste eine Supermenge ({2,3}) mit unserem hinzugefügten Element (1) zu jeder Menge. Somit können wir die Obermenge berechnen, indem wir das erste Element nehmen, die Obermenge für alle anderen berechnen und die Summe des Ergebnisses und des Ergebnisses mit der Hinzufügung des ersten Elements zu jeder Menge zurückgeben:
fun <T> powerset(set: Set<T>): Set<Set<T>> { val first = set.first() val powersetOfRest = powerset(set.drop(1)) return powersetOfRest.map { it + first } + powersetOfRest }
Diese Methode funktioniert jedoch nicht. Das Problem ist ein leerer Satz: first wird ein Fehler ausgegeben, wenn der Satz leer ist. Hier kommt die Definition einer Obermenge zur Rettung - die Obermenge einer leeren Menge ist eine leere Menge: Powerset ({}) = {{}}. So sieht der korrigierte Algorithmus aus:
fun <T> powerset(set: Set<T>): Set<Set<T>> = if (set.isEmpty()) setOf(emptySet()) else { val powersetOfRest = powerset(set.drop(1)) powersetOfRest + powersetOfRest.map { it + set.first() } }
Mal sehen, wie es funktioniert. Angenommen, wir müssen das Powerset ({1,2,3}) berechnen. Der Algorithmus funktioniert wie folgt:
Powerset ({1,2,3}) = Powerset ({2,3}) + Powerset ({2,3}). map {it + 1}
Powerset ({2,3}) = Powerset ({3}) + Powerset ({3}). map {it + 2}
Powerset ({3}) = Powerset ({}) + Powerset ({}). map {it + 3}
Powerset ({}) = {{}}
Powerset ({3}) = {{}, {3}}
Powerset ({2,3}) = {{}, {3}} + {{2}, {2, 3}} = {{}, {2}, {3}, {2, 3}}
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}}
Aber wir können unsere Funktion noch weiter verbessern. Verwenden wir die let-Funktion, um die Notation kürzer und kompakter zu machen:
fun <T> powerset(set: Set<T>): Set<Set<T>> = if (set.isEmpty()) setOf(emptySet()) else powerset(set.drop(1)) .let { it+ it.map { it + set.first() }
Wir können diese Funktion auch als Erweiterungsfunktion für Collection , sodass wir diese Funktion so verwenden können, als wäre es die Set ( setOf(1,2,3).powerset() powerset(setOf(1,2,3)) anstelle des powerset(setOf(1,2,3)) ):
fun <T> Collection<T>.powerset(): Set<Set<T>> = if (isEmpty()) setOf(emptySet()) else drop(1) .powerset() .let { it+ it.map { it + first() }
Wir können auch die negativen Auswirkungen der erstellten Rekursion reduzieren. In der obigen Implementierung wächst der Status der Obermenge mit jeder Iteration (mit jedem rekursiven Aufruf), da der Status der vorherigen Iteration im Speicher gespeichert werden muss.
Stattdessen könnten wir einen regulären Loop- oder tailrec Funktionsmodifikator verwenden. Wir werden die zweite Option verwenden, um die Lesbarkeit der Funktion zu gewährleisten. Der Modifikator tailrec erlaubt nur einen rekursiven Aufruf in der zuletzt ausgeführten Funktionszeile. So können wir unsere Funktion ändern, um sie effizienter zu nutzen:
fun <T> Collection<T>.powerset(): Set<Set<T>> = powerset(this, setOf(emptySet())) 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() })
Diese Implementierung ist Teil der KotlinDiscreteMathToolkit- Bibliothek, die viele andere Funktionen definiert, die in der diskreten Mathematik verwendet werden.
Zeit für das interessanteste Beispiel. Sie werden sehen, wie ein komplexes Problem mithilfe der Stil- und Funktionsprogrammierwerkzeuge vereinfacht und lesbar gemacht werden kann.
Wir implementieren einen schnellen Sortieralgorithmus. Der Algorithmus ist einfach: Wir wählen ein Element aus (Pivot (russischer Balken )) und verteilen alle anderen Elemente auf zwei Listen: eine Liste mit Elementen, die größer als der Balken und kleiner sind. Dann sortieren wir diese Subarrays rekursiv. Schließlich kombinieren wir eine sortierte Liste kleinerer Elemente, einen Balken und eine sortierte Liste größerer Elemente. Nehmen Sie zur Vereinfachung das erste Element als Balken. Hier ist die vollständige Implementierung:
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() }
Sieht wunderschön aus, oder? Das ist das Schöne an der funktionalen Programmierung.
Das erste Problem bei einer solchen Funktion ist ihre Ausführungszeit. Sie ist völlig unoptimiert. Aber es ist kurz und leicht zu lesen.
Wenn Sie eine optimierte Funktion benötigen, können Sie die Funktion aus der Standard-Java-Bibliothek verwenden. Es basiert auf verschiedenen Algorithmen in Abhängigkeit von bestimmten Bedingungen und ist nativ geschrieben. Dies sollte viel effizienter sein. Aber wie viel genau? Vergleichen wir diese beiden Funktionen. Lassen Sie uns mehrere verschiedene Arrays mit zufälligen Elementen sortieren und die Laufzeit vergleichen:
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() }}") }
Hier sind die Ergebnisse, die wir erhalten haben:
Die Java-Stdlib-Sortierung von 100000 Elementen dauerte 83
Die QuickSort-Sortierung von 100000 Elementen dauerte 163
Die Java-Stdlib-Sortierung von 1.000.000 Elementen dauerte 558
Die QuickSort-Sortierung von 1.000.000 Elementen dauerte 859
Die Java-Stdlib-Sortierung von 10.000.000 Elementen dauerte 6182
Die QuickSort-Sortierung von 10.000.000 Elementen dauerte 12133
Wie Sie sehen können, ist die quickSort Funktion fast zweimal langsamer. Auch für große Listen. In normalen Fällen beträgt der Unterschied typischerweise 0,1 ms bis 0,2 ms. Dies erklärt, warum wir in einigen Fällen eine Funktion verwenden können, die etwas weniger optimiert, aber gut lesbar und einfach ist.