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 different, implement methods of the PrimeAccessRepository class:
isOnAllowList should return true if the user is on the allowlist (entry with this user id has allowList set to true), and false otherwise,isOnDenyList should return true if the user is on the denylist (entry with this user id has denyList set to true), and false otherwise.
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:
- iterating over entries to find the searched user id,
- associating entries to a map by user id in the class body, and in methods finding the entry by user id.
For each of those solutions, check its efficiency 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.
Once you are done with the exercise, you can check your solution here.
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, is 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.
