article banner (priority)

Challenge: Prime access list

Today I have for you this exercise that I already presented in the Functional Kotlin book and online course, but that captures the core idea of the Effective Kotlin book Item 55: Consider associating elements to a map. It is especially an important exercise for backend development, where I found this optimization useful in many services, but it has its applications in frontend development as well. So without further ado, here is the exercise in its original form:

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 differentce, 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.

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 main function I defined in the playground below:

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") } }

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.

Starting code and the code to measure implementation performance can be also found in the kotlin-exercises project on GitHub in the file effective/collections/PrimeAccess.kt. You can clone this project and solve this exercise locally.

I decided I wouldn't feel good showing you the solution. It can be found at the end of the book Functional Kotlin, and in the course Functional Kotlin, but here it would be just too easy to see it and copy it. I want you to try to solve it yourself. If you have any questions, feel free to ask them in the comments below. You can also send a Tweet to me @marcinmoskala. I will be happy to help you. If you managed to solve this exercise, feel free to share it with others. I will be happy to see your solutions. Good luck and have fun!

Know that this optimization can also be applied on other cases. Even in a local code, if you need to find if a list includes elements, it might be worth to transform it into Set, and if you need to find what a key is associated with, it might be worth to transform it into Map.

To learn more about transforming collections to Map, see this article from the Functional Kotlin book. To learn more about associating elements, see this article from the Effective Kotlin book.