Salah satu fitur hebat Kotlin adalah mendukung pemrograman fungsional. Mari kita lihat dan bahas beberapa fungsi sederhana namun ekspresif yang ditulis dalam Kotlin.
Bekerja dengan koleksi
Kotlin mendukung pekerjaan yang mudah dengan koleksi. Ada banyak fitur berbeda. Misalkan kita membuat beberapa sistem untuk universitas. Kita perlu menemukan siswa terbaik yang berhak mendapatkan beasiswa. Kami memiliki model Student berikut:
class Student( val name: String, val surname: String, val passing: Boolean, val averageGrade: Double )
Sekarang kita dapat memanggil fungsi berikut untuk mendapatkan daftar sepuluh siswa terbaik yang memenuhi semua kriteria:
students.filter { it.passing && it.averageGrade > 4.0 } // 1 .sortedBy { it.averageGrade } // 2 .take(10) // 3 .sortedWith(compareBy({ it.surname }, { it.name })) // 4
- Kami hanya menyisakan siswa yang telah lulus ujian, skor rata-rata lebih dari 4.0.
- Urutkan berdasarkan skor rata-rata.
- Kami meninggalkan sepuluh siswa pertama.
- Urutkan berdasarkan abjad. Pembanding pertama membandingkan nama belakang, dan jika mereka sama, maka itu membandingkan nama-nama.
Bagaimana jika, alih-alih urutan abjad, kita perlu mempertahankan urutan asli siswa? Kita dapat melakukan ini menggunakan indeks:
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
- Ikatkan indeks iterasi saat ini untuk setiap elemen.
- Urutkan berdasarkan skor rata-rata dan tinggalkan sepuluh siswa pertama.
- Sortir lagi, tetapi sekarang dengan indeks.
- Kami menghapus indeks dan hanya menyisakan siswa.
Contoh ini menunjukkan betapa sederhana dan intuitifnya pekerjaan dengan koleksi di Kotlin.
Jika Anda belajar aljabar di universitas, Anda mungkin ingat apa itu superset. Untuk set apa pun, supersetnya adalah himpunan semua himpunan bagiannya, termasuk himpunan asli itu sendiri dan himpunan kosong. Misalnya, jika kita memiliki set berikut:
{1,2,3}
Itulah supersetnya:
{{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}
Dalam aljabar, fungsi seperti itu sangat berguna. Bagaimana kita menerapkannya?
Jika Anda ingin menantang diri sendiri, berhentilah membaca sekarang dan cobalah untuk menyelesaikan masalah ini sendiri.
Mari kita mulai analisis kita dengan pengamatan sederhana. Jika kita mengambil beberapa elemen dari himpunan (misalnya, 1), maka super-set akan memiliki jumlah set yang sama dengan elemen ini ({1}, {1,2}, {1,3}, {1,2,3}) dan tanpanya ({}, {2}, {3}, {2,3}).
Perhatikan bahwa set kedua adalah set super ({2,3}), dan set pertama adalah set super ({2,3}) dengan elemen tambahan kami (1) untuk setiap set. Dengan demikian, kita dapat menghitung superset dengan mengambil elemen pertama, menghitung superset untuk yang lainnya dan mengembalikan jumlah hasil dan hasilnya dengan menambahkan elemen pertama ke setiap set:
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 }
Tetapi metode ini tidak akan berhasil. Masalahnya adalah set kosong: first akan melempar kesalahan ketika set kosong. Di sini definisi superset datang untuk menyelamatkan - superset dari set kosong adalah set kosong: powerset ({}) = {{}}. Seperti apa algoritma yang dikoreksi:
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() } }
Mari kita lihat cara kerjanya. Misalkan kita perlu menghitung powerset ({1,2,3}). Algoritme akan bertindak sebagai berikut:
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}}
Tetapi kita dapat meningkatkan fungsi kita lebih jauh. Mari kita gunakan fungsi let untuk membuat notasi lebih pendek dan lebih kompak:
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() }
Kita juga dapat mendefinisikan fungsi ini sebagai fungsi ekstensi untuk Collection , sehingga kita dapat menggunakan fungsi ini seolah-olah itu adalah metode Set ( setOf(1,2,3).powerset() alih-alih 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() }
Kami juga dapat mengurangi efek negatif dari rekursi yang dibuat. Dalam implementasi di atas, keadaan superset tumbuh dengan setiap iterasi (dengan setiap panggilan rekursif), karena keadaan iterasi sebelumnya harus disimpan dalam memori.
Sebagai gantinya, kita bisa menggunakan tailrec fungsi loop atau tailrec . Kami akan menggunakan opsi kedua untuk menjaga keterbacaan fungsi. Pengubah tailrec hanya memungkinkan satu panggilan rekursif di baris fungsi terakhir yang dijalankan. Inilah cara kami dapat mengubah fungsi kami untuk menggunakannya secara lebih efisien:
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() })
Implementasi ini adalah bagian dari perpustakaan KotlinDiscreteMathToolkit , yang mendefinisikan banyak fungsi lain yang digunakan dalam matematika diskrit.
Saatnya untuk contoh paling menarik. Anda akan melihat bagaimana masalah yang rumit dapat disederhanakan dan dibuat dapat dibaca menggunakan alat pemrograman gaya dan fungsional.
Kami menerapkan algoritma pengurutan cepat. Algoritma ini sederhana: kami memilih beberapa elemen (pivot ( bilah Rusia)) dan mendistribusikan semua elemen lainnya ke dalam dua daftar: daftar dengan elemen lebih besar dari bilah dan lebih kecil. Kemudian kami secara rekursif menyortir subarrays ini. Akhirnya, kami menggabungkan daftar elemen yang lebih kecil, bar, dan daftar yang diurutkan dari elemen yang lebih besar. Untuk menyederhanakan, ambil elemen pertama sebagai bilah. Berikut ini adalah implementasi lengkapnya:
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() }
Terlihat cantik, bukan? Inilah keindahan pemrograman fungsional.
Masalah pertama dengan fungsi seperti itu adalah waktu pelaksanaannya. Dia benar-benar tidak dioptimalkan. Tapi itu pendek dan mudah dibaca.
Jika Anda membutuhkan fungsi yang dioptimalkan, Anda dapat menggunakan fungsi dari perpustakaan Java standar. Ini didasarkan pada berbagai algoritma tergantung pada kondisi tertentu, dan ditulis secara asli. Ini harus jauh lebih efisien. Tapi seberapa tepatnya? Mari kita bandingkan dua fungsi ini. Mari kita mengurutkan beberapa array berbeda dengan elemen acak dan membandingkan 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() }}") }
Inilah hasil yang kami dapatkan:
Pengurutan stdlib Java dari 100.000 elemen mengambil 83
penyortiran quickSort dari 100.000 elemen mengambil 163
Pengurutan stdlib Java dari 1.000.000 elemen mengambil 558
penyortiran quickSort dari 1.000.000 elemen membutuhkan 859
Pengurutan stdlib Java dari 10.000.000 elemen mengambil 6182
penyortiran quickSort dari 10.000.000 elemen membutuhkan 1.2133
Seperti yang Anda lihat, fungsi quickSort hampir 2 kali lebih lambat. Bahkan untuk daftar besar. Dalam kasus normal, perbedaannya biasanya dari 0,1 ms ke 0,2 ms. Ini menjelaskan mengapa dalam beberapa kasus kita dapat menggunakan fungsi yang sedikit kurang dioptimalkan, tetapi mudah dibaca dan sederhana.