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.

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