Item: Considere agregar elementos a um mapa

Publicado em por
Tempo de leitura: 3 minutes

Não é incomum ter um conjunto maior de elementos que precisamos acessar muitas vezes. Pode ser:

  • Um cache – dados que baixamos de algum serviço e depois mantemos na memória local para acessá-los mais rapidamente
  • Um repositório com dados carregados de algum arquivo
  • Um repositório na memória usado para diferentes tipos de testes

Esses dados podem representar alguma lista de usuários, ids, configurações, etc. Eles geralmente são fornecidos a nós como uma lista, e é tentador representá-los em nossa memória da mesma maneira:

class NetworkUserRepo(val userService: UserService): UserRepo {
    private var users: List<User>? = null    override fun getUser(id: UserId): User? {
        if(users == null) {
            users = userService.getUsers()
        }
        return users?.firstOrNull { it.id == id }
    }
}

class ConfigurationsRepository(
    val configurations: List<Configuration>
) {
    fun getByName(name: String) = configurations
        .firstOrNull { it.name == name }
}class InMemoryUserRepo: UserRepo {
   private val users: MutableList<User> = mutableListOf()   override fun getUser(id: UserId): User?
      = users.firstOrNull { it.id == id }
   
   fun addUser(user: User) {
      user.add(user)
   }
}

Essa raramente é a melhor maneira de armazenar esses elementos. Observe como os dados que carregamos são usados. Na maioria das vezes, acessamos um elemento por algum identificador ou nome (ele está conectado à forma como projetamos os dados para ter chaves exclusivas em bancos de dados). Encontrar um elemento em uma lista tem complexidade O(n), onde n é o tamanho da lista. Mais concretamente, leva em média n/2 comparações para encontrar um elemento. É especialmente problemático para listas maiores. Uma boa solução para esse problema é usar um mapa em vez de uma lista. Por padrão, o Kotlin usa um Map hash (concretamente LinkedHashMap) e, conforme descrevemos no Item 41: Respeite o contrato de hashCode, o desempenho de encontrar um elemento quando usamos o mapa hash é muito melhor. Na verdade, na JVM, graças ao fato de que o tamanho do hash map usado é ajustado ao tamanho do próprio mapa, se o hashCode for implementado corretamente, encontrar um elemento deve levar apenas uma comparação.

Este é InMemoryRepo usando um mapa em vez de uma lista:

class InMemoryUserRepo: UserRepo {
   private val users: MutableMap<UserId, User> = mutableMapOf()   

   override fun getUser(id: UserId): User? = users[id]
   
   fun addUser(user: User) {
      user.put(user.id, user)
   }
}

A maioria das outras operações, como modificar ou iterar sobre esses dados (provavelmente usando métodos de processamento de coleção como filtro, mapa, flatMap, classificado, soma, etc.) têm mais ou menos o mesmo desempenho para a lista e mapa padrão.

A questão é como nos transformamos de uma lista em um mapa e vice-versa. Para isso usamos funções associadas. O mais comum é o associatedBy que constrói um mapa onde os valores são os elementos da lista e as chaves são produzidas na expressão lambda:

data class User(val id: Int, val name: String)
val users = listOf(User(1, "Michal"), User(2, "Marek"))

val byId = users.associateBy { it.id }
byId == mapOf(1 to User(1, "Michal"), 2 to User(2, "Marek")) 

val byName = users.associateBy { it.name }
byName == mapOf("Michal" to User(1, "Michal"), 
              "Marek" to User(2, "Marek"))

Observe que as chaves nos mapas devem ser exclusivas ou as duplicatas serão removidas. É por isso que devemos apenas associar por um identificador único (para agrupar por algo que não é único, use groupBy).

val users = listOf(User(1, "Michal"), User(2, "Michal"))

val byName = users.associateBy { it.name }
byName == mapOf("Michal" to User(2, "Michal"))

Para transformar o contrário, você pode usar valores:

val users = listOf(User(1, "Michal"), User(2, "Michal"))
val byId = users.associateBy { it.id }
users == byId.values

É assim que os outros repositórios podem ser implementados usando um mapa para melhorar o desempenho de acesso aos elementos:

class NetworkUserRepo(val userService: UserService): UserRepo {
    private var users: Map<UserId, User>? = null
    override fun getUser(id: UserId): User? {
        if(users == null) {
            users = userService.getUsers().associateBy { it.id }
        }
        return users?.get(id)
    }
}

class ConfigurationsRepository(
    configurations: List<Configuration>
) {
    val configurations: Map<String, Configuration> = 
        configurations.associateBy { it.name }
    
    fun getByName(name: String) = configurations[name]
}

Essa técnica é importante, mas não é para todos os casos. É mais útil quando frequentemente precisamos acessar esses elementos. É por isso que é especialmente importante no backend, onde essas coleções podem ser acessadas muitas vezes por segundo. Não é tão importante no frontend (com isso quero dizer também Android ou iOS), onde um usuário acessará este repositório no máximo algumas vezes. Também precisamos lembrar que o mapeamento de uma lista para um mapa também leva algum tempo, portanto, se o fizermos com frequência, pode prejudicar nosso desempenho também.

 

Obrigado por gastar seu tempo lendo este artigo. Compartilhe se você gostou!

Twittar
Compartilhar
Compartilhar
0 Compart.