L'une des grandes fonctionnalités de Kotlin est qu'il prend en charge la programmation fonctionnelle. Jetons un coup d'œil et discutons de quelques fonctions simples mais expressives écrites en Kotlin.
Travailler avec des collections
Kotlin prend en charge le travail pratique avec les collections. Il existe de nombreuses fonctionnalités différentes. Supposons que nous créons un système pour une université. Nous devons trouver les meilleurs étudiants qui méritent une bourse. Nous avons le modèle Student suivant:
class Student( val name: String, val surname: String, val passing: Boolean, val averageGrade: Double )
Maintenant, nous pouvons appeler la fonction suivante pour obtenir une liste des dix meilleurs étudiants qui répondent à tous les critères:
students.filter { it.passing && it.averageGrade > 4.0 } // 1 .sortedBy { it.averageGrade } // 2 .take(10) // 3 .sortedWith(compareBy({ it.surname }, { it.name })) // 4
- Nous ne laissons que les étudiants qui ont réussi l'examen, dont le score moyen est supérieur à 4,0.
- Triez-les par le score moyen.
- Nous quittons les dix premiers étudiants.
- Triez-les par ordre alphabétique. Le comparateur compare d'abord les noms de famille, et s'ils sont égaux, il compare ensuite les noms.
Et si, au lieu de l'ordre alphabétique, nous devions maintenir l'ordre d'origine des élèves? Nous pouvons le faire en utilisant des index:
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
- Liez l'index d'itération actuel à chaque élément.
- Trier par le score moyen et laisser les dix premiers étudiants.
- Trier à nouveau, mais maintenant par index.
- Nous supprimons les index et ne laissons que les étudiants.
Cet exemple montre à quel point le travail avec les collections dans Kotlin est simple et intuitif.
Si vous avez étudié l'algèbre dans une université, vous vous souvenez peut-être de ce qu'est un surensemble. Pour tout ensemble, son sur-ensemble est l'ensemble de tous ses sous-ensembles, y compris l'ensemble d'origine lui-même et l'ensemble vide. Par exemple, si nous avons l'ensemble suivant:
{1,2,3}
C'est son surensemble:
{{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}
En algèbre, une telle fonction est très utile. Comment le mettons-nous en œuvre?
Si vous voulez vous mettre au défi, arrêtez de lire maintenant et essayez de résoudre ce problème vous-même.
Commençons notre analyse par une simple observation. Si nous prenons un élément de l'ensemble (par exemple, 1), alors le super-ensemble aura un nombre égal d'ensembles avec cet élément ({1}, {1,2}, {1,3}, {1,2,3}) et sans elle ({}, {2}, {3}, {2,3}).
Notez que le deuxième ensemble est un super-ensemble ({2,3}), et le premier est un super-ensemble ({2,3}) avec notre élément ajouté (1) à chaque ensemble. Ainsi, nous pouvons calculer le surensemble en prenant le premier élément, en calculant le surensemble pour tous les autres et en renvoyant la somme du résultat et du résultat avec l'ajout du premier élément à chaque ensemble:
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 }
Mais cette méthode ne fonctionnera pas. Le problème est un ensemble vide: le first générera une erreur lorsque l'ensemble sera vide. Ici, la définition d'un surensemble vient à la rescousse - le surensemble d'un ensemble vide est un ensemble vide: powerset ({}) = {{}}. Voici à quoi ressemble l'algorithme corrigé:
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() } }
Voyons comment cela fonctionne. Supposons que nous ayons besoin de calculer l'ensemble de puissance ({1,2,3}). L'algorithme agira comme suit:
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}}
Mais nous pouvons encore améliorer notre fonction. Utilisons la fonction let pour rendre la notation plus courte et plus compacte:
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() }
Nous pouvons également définir cette fonction comme une fonction d'extension pour Collection , afin que nous puissions utiliser cette fonction comme s'il s'agissait de la setOf(1,2,3).powerset() Set ( setOf(1,2,3).powerset() au lieu de 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() }
Nous pouvons également réduire les effets négatifs de la récursivité créée. Dans l'implémentation ci-dessus, l'état du sur-ensemble croît à chaque itération (à chaque appel récursif), car l'état de l'itération précédente doit être stocké en mémoire.
À la place, nous pourrions utiliser une boucle régulière ou tailrec fonction tailrec . Nous utiliserons la deuxième option pour maintenir la lisibilité de la fonction. Le modificateur tailrec n'autorise qu'un seul appel récursif dans la dernière ligne de fonction exécutée. Voici comment nous pouvons changer notre fonction pour l'utiliser plus efficacement:
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() })
Cette implémentation fait partie de la bibliothèque KotlinDiscreteMathToolkit , qui définit de nombreuses autres fonctions utilisées en mathématiques discrètes.
Il est temps pour l'exemple le plus intéressant. Vous verrez comment un problème complexe peut être simplifié et rendu lisible à l'aide des outils de programmation de style et fonctionnels.
Nous implémentons un algorithme de tri rapide. L'algorithme est simple: nous sélectionnons un élément (pivot ( barre russe)) et répartissons tous les autres éléments dans deux listes: une liste avec des éléments plus grands que la barre et plus petits. Ensuite, nous trions récursivement ces sous-réseaux. Enfin, nous combinons une liste triée d'éléments plus petits, une barre et une liste triée d'éléments plus grands. Pour simplifier, prenez le premier élément sous forme de barre. Voici l'implémentation complète:
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() }
C'est magnifique, non? C'est la beauté de la programmation fonctionnelle.
Le premier problème avec une telle fonction est son temps d'exécution. Elle n'est pas du tout optimisée. Mais il est court et facile à lire.
Si vous avez besoin d'une fonction optimisée, vous pouvez utiliser la fonction de la bibliothèque Java standard. Il est basé sur différents algorithmes en fonction de certaines conditions et est écrit en natif. Cela devrait être beaucoup plus efficace. Mais combien exactement? Comparons ces deux fonctions. Trions plusieurs tableaux différents avec des éléments aléatoires et comparons le runtime:
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() }}") }
Voici les résultats que nous avons obtenus:
Le tri Java stdlib de 100 000 éléments a pris 83
Le tri rapide de 100 000 éléments a nécessité 163
Le tri Java stdlib de 1000000 éléments a pris 558
Le tri quickSort de 1 000 000 d'éléments a pris 859
Le tri Java stdlib de 10 000 000 d'éléments a pris 6 182
Le tri quickSort de 10 000 000 d'éléments a pris 12133
Comme vous pouvez le voir, la fonction quickSort presque 2 fois plus lente. Même pour d'énormes listes. Dans des cas normaux, la différence sera généralement de 0,1 ms à 0,2 ms. Cela explique pourquoi dans certains cas, nous pouvons utiliser une fonction légèrement moins optimisée, mais bien lisible et simple.