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.

Playground

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