Similmente a quanto abbiamo fatto con Python, vogliamo scrivere un algoritmo in Kotlin che, dato un lato n-esimo arbitrario, disegni una matrice di valori concentrici. Il risultato che vogliamo ottenere è il seguente:
Anche in questo caso vogliamo misurare il tempo di calcolo per ognuno dei metodi adottati. L’algoritmo può essere affrontato in molti modi, similmente a quanto abbiamo fatto con Python, quindi in questo caso mi limiterò a due casi soltanto, con le relative valutazioni di velocità.
Cominciamo con il primo metodo, che è anche quello più semplice e meno efficiente.
Definiamo quindi una funzione che ci permetta di scegliere se acquisire l’input dall’utente oppure passarlo noi programmaticamente (e analogamente che consenta di scegliere se stamparlo o meno a video).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
fun metodo1(stampa: Boolean = true, ndefault: Int = 0) : Double { println("-- disegna quadrato concentrico --") if( ndefault == 0 ) print("Lato quadrato: ") val n = if( ndefault == 0 ) readln().toInt() else ndefault val dim = n * 2 - 1 val quadrato = Array(dim) { IntArray(dim) } val inizio = System.nanoTime() // tempo in nanosecondi for( k in 0 .. n-1 ) { for( i in k .. dim - k - 1 ) { for( j in k .. dim - k - 1 ) { quadrato[i][j] = n - k } } } val fine = System.nanoTime() println("Tempo metodo1: ${(fine - inizio) / 1_000_000.0} ms") // stampa del quadrato if( stampa ) { for (i in quadrato.indices) { for (j in quadrato[i].indices) { print("${quadrato[i][j]} ") } println() } } return (fine - inizio) / 1_000_000.0 } |
Per eseguirlo lo chiamiamo dentro il main.
|
1 2 3 4 5 |
fun main() { metodo1() } |
Nel secondo metodo avremo bisogno di definire un oggetto di appoggio per le variabili che vogliamo usare globalmente:
|
1 2 3 4 |
object Globale { var dim: Int = 0 var n: Int = 0 } |
E creiamo una funzione di calcolo dei valori:
|
1 2 3 4 5 |
fun calcolaValore(i: Int, j: Int) : Int { val ni = if( i < Globale.dim / 2.0 ) i else Globale.dim - i - 1 val nj = if( j < Globale.dim / 2.0 ) j else Globale.dim - j - 1 return Globale.n - ( if( nj <= ni ) nj else ni ) } |
Procediamo alla creazione della seconda funzione:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
fun metodo2(stampa : Boolean = true, ndefault : Int = 0) : Double { println("-- disegna quadrato concentrico --") if( ndefault == 0 ) print("Lato quadrato: ") val n = if( ndefault == 0 ) readln().toInt() else ndefault val dim = n * 2 - 1 Globale.dim = dim Globale.n = n val quadrato = Array(dim) { IntArray(dim) } val inizio = System.nanoTime() // tempo in nanosecondi for( i in quadrato.indices ) { for( j in quadrato[i].indices ) { quadrato[i][j] = calcolaValore(i, j) } } val fine = System.nanoTime() println("Tempo metodo2: ${(fine - inizio) / 1_000_000.0} ms") // stampa del quadrato if( stampa ) { for (i in quadrato.indices) { for (j in quadrato[i].indices) { print("${quadrato[i][j]} ") } println() } } return (fine - inizio) / 1_000_000.0 } |
Mettiamo alla prova entrambi i metodi:
|
1 2 3 4 5 6 |
fun main() { metodo1(false, 10) metodo2(false, 10) } |
Su un quadrato con n = 10 il primo metodo risulta più efficiente del secondo:
|
1 2 3 4 |
-- disegna quadrato concentrico -- Tempo metodo1: 0.0121 ms -- disegna quadrato concentrico -- Tempo metodo2: 0.0553 ms |
Proviamo ad alzare il tiro impostando n = 1000
|
1 2 3 4 |
-- disegna quadrato concentrico -- Tempo metodo1: 425.644 ms -- disegna quadrato concentrico -- Tempo metodo2: 10.637 ms |
Raccogliamo un po’ di dati per valori di n rispettivamente impostati a 10, 100, 1.000, 10.000 e 20.000:
|
1 2 3 4 5 6 7 8 9 |
fun main() { for( i in listOf(10,100,1_000,10_000,20_000) ) { val r1 = metodo1(false, i) val r2 = metodo2(false, i) println("$i;$r1;$r2") } } |
Nel caso in si dovesse incorrere nell’errore Exception in thread "main" java.lang.OutOfMemoryError: Java heap space aumentare lo spazio del Shared heap size in Settings -> Build, Execution, Deployment -> Compiler
Oppure creare una configurazione personalizzata per il compilatore come per esempio questa:
Comunque sia otterremo così i seguenti dati:
| n | metodo1 | metodo2 |
| 10 | 0,0103 | 0,0558 |
| 100 | 2,608 | 1,032 |
| 1000 | 368,7968 | 7,4704 |
| 10000 | 324428,347 | 206,1374 |
| 20000 | 2797371,15 | 1589,187 |
Al crescere della complessità del sistema vediamo come cresce il rapporto tra il metodo1 e il metodo2
