Solution: Prime access list
This is what the solution that requires iterating over entries to find the searched user id could look like:
class PrimeAccessRepository(
private val primeAccessList: PrimeAccessList,
) {
fun isOnAllowList(userId: String): Boolean =
primeAccessList.entries
.find { it.userId == userId }
?.allowList
?: false
fun isOnDenyList(userId: String): Boolean =
primeAccessList.entries
.find { it.userId == userId }
?.denyList
?: false
}
On my machine (Apple M2 Pro), performance measurement gives the following results:
Class creation took 0 ms
Operation took 2926 ms
Operation took 2831 msThe optimized solution that associates entries to a map by user id in the class body and finds the entry by user id in the methods could look like this:
class PrimeAccessRepository(
primeAccessList: PrimeAccessList,
) {
private val entries = primeAccessList.entries
.associateBy { it.userId }
fun isOnAllowList(userId: String): Boolean =
entries[userId]?.allowList ?: false
fun isOnDenyList(userId: String): Boolean =
entries[userId]?.denyList ?: false
}
On my machine (Apple M2 Pro), performance measurement gives the following results:
Class creation took 32 ms
Operation took 2 ms
Operation took 2 msThis means that class creation is slightly slower (it requires one iteration over entries to create the map), but operations are much faster (they require only one map access).
Example solution in playground
import kotlin.random.Random
import kotlin.system.measureTimeMillis
class PrimeAccessRepository(
primeAccessList: PrimeAccessList,
) {
private val entries = primeAccessList.entries
.associateBy { it.userId }
fun isOnAllowList(userId: String): Boolean =
entries[userId]?.allowList ?: false
fun isOnDenyList(userId: String): Boolean =
entries[userId]?.denyList ?: false
}
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") }
}
