Exercise: Prime access list
Associating elements to a map can be an important performance optimization. Finding an element by key in a map is a lot faster than iterating over a list and comparing each element to the searched value. To see the difference, implement methods for the PrimeAccessRepository class:
isOnAllowList should return true if the user is on the allowlist (the entry with this user id has allowList set to true); otherwise, it should return false,isOnDenyList should return true if the user is on the denylist (the entry with this user id has denyList set to true); otherwise, it should return false.
class PrimeAccessRepository(
private val primeAccessList: PrimeAccessList
) {
fun isOnAllowList(userId: String): Boolean = TODO()
fun isOnDenyList(userId: String): Boolean = TODO()
}
class PrimeAccessList(
val entries: List<PrimeAccessEntry>
)
class PrimeAccessEntry(
val userId: String,
val allowList: Boolean,
val denyList: Boolean,
)
Implement two kinds of solutions:
- iterate over entries to find the desired user id,
- associate entries to a map by user id in the class body, and find the entry by user id in the methods.
Check the efficiency of each of these solutions using the following code:
val entries = List(200_000) {
PrimeAccessEntry(
userId = it.toString(),
allowList = Random.nextBoolean(),
denyList = Random.nextBoolean()
)
}.shuffled()
val accessList = PrimeAccessList(entries)
val repo: PrimeAccessRepository
measureTimeMillis {
repo = PrimeAccessRepository(accessList)
}.also { println("Class creation took $it ms") }
measureTimeMillis {
for (userId in 1L..10_000L) {
repo.isOnAllowList(userId.toString())
}
}.also { println("Operation took $it ms") }
measureTimeMillis {
for (userId in 1L..10_000L) {
repo.isOnDenyList(userId.toString())
}
}.also { println("Operation took $it ms") }
Beware! Such measurements are not precise. They are only to show the difference between the two solutions. For precise measurements, you should use a benchmarking library, like JMH.
This problem can either be solved in the below playground or you can clone kotlin-exercises project and solve it locally. In the project, you can find code template for this exercise in effective/collections/PrimeAccess.kt. You can find there starting code and example usage.
import kotlin.random.Random
import kotlin.system.measureTimeMillis
class PrimeAccessRepository(
private val primeAccessList: PrimeAccessList
) {
fun isOnAllowList(userId: String): Boolean = TODO()
fun isOnDenyList(userId: String): Boolean = TODO()
}
class PrimeAccessList(
val entries: List<PrimeAccessEntry>
)
class PrimeAccessEntry(
val userId: String,
val allowList: Boolean,
val denyList: Boolean,
)
fun main() {
val entries = List(200_000) {
PrimeAccessEntry(
userId = it.toString(),
allowList = Random.nextBoolean(),
denyList = Random.nextBoolean()
)
}.shuffled()
val accessList = PrimeAccessList(entries)
val repo: PrimeAccessRepository
measureTimeMillis {
repo = PrimeAccessRepository(accessList)
}.also { println("Class creation took $it ms") }
measureTimeMillis {
for (userId in 1L..10_000L) {
repo.isOnAllowList(userId.toString())
}
}.also { println("Operation took $it ms") }
measureTimeMillis {
for (userId in 1L..10_000L) {
repo.isOnDenyList(userId.toString())
}
}.also { println("Operation took $it ms") }
}
Marcin Moskala is a highly experienced developer and Kotlin instructor as the founder of Kt. Academy, an official JetBrains partner specializing in Kotlin training, Google Developers Expert, known for his significant contributions to the Kotlin community. Moskala is the author of several widely recognized books, including "Effective Kotlin," "Kotlin Coroutines," "Functional Kotlin," "Advanced Kotlin," "Kotlin Essentials," and "Android Development with Kotlin."
Beyond his literary achievements, Moskala is the author of the largest Medium publication dedicated to Kotlin. As a respected speaker, he has been invited to share his insights at numerous programming conferences, including events such as Droidcon and the prestigious Kotlin Conf, the premier conference dedicated to the Kotlin programming language.
