Minhas estruturas de dados favoritas em python: dicionários e conjuntos

Photo by Faris Mohammed on Unsplash

Dicionários em python são estruturas que armazenam mapeamentos de chave e valor, como {“nome”: “Thiago”, “telefone”: “12345678”}.

Além disso, os dicionários são importantíssimos na linguagem python, já que são utilizados em diversas funções embutidas da linguagem (built-in). Por exemplo: os próprios atributos de classes e argumentos nomeados em funções (**kwargs).

Nesse artigo iremos:
- Entender o funcionamento dos dicionários e tabelas hash
- Ver alguns casos de uso para dicionários e conjuntos
- Dar alguns ponteiros de quando não devemos usar os dicionários

Tabela hash & performance

A tabela hash é o mecanismo por trás do funcionamento dos dicionários no python, mas também tem implementações similares em diversas outras linguagens (HashMap no Java ou object no JavaScript, por exemplo).

O objetivo da tabela hash é permitir que encontremos uma chave no dicionário de forma rápida. Quando falamos de “velocidade” em algoritmos, geralmente usamos a Notação Big O para definir exatamente o que queremos dizer com velocidade, conforme a imagem abaixo:

Para ilustrar a ideia, imagine que temos uma lista e queremos verificar a existência de um número na lista:

numbers = [1,2,3,4,5,6,7,8,9]
if 8 in numbers: # O(n)
   print("Número 8 está na lista!")

A operação acima terá uma complexidade de O(n), pois para a linguagem python determinar se um número está na lista, basicamente precisa percorrer toda a lista comparando se temos o número desejado. Isso não é um problema pra uma lista de 10 números, mas quanto maior o tamanho da lista (valor de n), mais demorada essa operação será.

Já os dicionários/tabelas hash possuem uma complexidade constante O(1), independentemente do tamanho do dicionário:

phone_book = {“nome”: “Thiago”, “numero”: “1234567”}
if “numero” in phone_book: # O(1)
 print(“Número está no dict!”)

Isso é possível pois tabelas hash são basicamente arrays “esparsos” em sua implementação. Isso quer dizer que entre um elemento e outro, sempre haverá espaço (ou elementos vazios). Tendo esses espaços vazios, a linguagem irá calcular um hash para cada chave no dicionário e com isso consegue identificar rapidamente onde uma chave está localizada, sem precisar percorrer todas as chaves disponíveis.

Vale mencionar que dicionários são uma troca de espaço por tempo: usamos mais memória em troca de operações mais rápidas e por isso os dicionários possuem um overhead de memória significativo. Mais detalhes sobre como contornar isso no final do artigo 👇

Alguns casos de uso com dicionários

Buscando chaves com valor default

Adoro python por conta de sua consistência e pela busca constante para evitar a ambiguidade. Quando buscamos por uma chave não existente em um dicionário, teremos um erro lançado:

phone_book[“address”]
# Raises KeyError: ‘address’

Porém, se precisarmos obter um valor default na chave pra evitar que um erro aconteça, podemos deixar isso bastante claro usando o método .get() do dicionário, onde o segundo parâmetro é o valor default que esperamos.

phone_book = {“nome”: “Thiago”, “numero”: “1234567”}
phone_book.get(“cep”, “<cep em branco>”)
# Retorna “<cep em branco>”, já que não temos essa chave no dicionário

Esse comportamento em outras linguagens pode não ser tão consistente, como por exemplo no javascript: se acesso uma chave que não existe no objeto, recebo `undefined` . Mas não sei se existe uma chave, com um valor `undefined`, ou se não existe a chave no objeto. Python evita toda essa ambiguidade por meio da sintaxe diferenciada para buscar chaves com default ✨

Simplificando condicionais

Outra forma elegante de se usar dicionários em python é simplificando condicionais. Vamos a um exemplo de fazer operações matemáticas:

def calculate(operation, x, y):
    if operation == "sum":
        return sum(x, y)
    elif operation == "subtract":
        return subtract(x, y)
    elif operation == "multiply":
        return multiply(x, y)
    elif operation == "":
        return divide(x, y)

O método acima poderia ser reescrito com dicionários, o que possui uma legibilidade consideravelmente melhor:

def calculate(operation, x, y):
    operations = {
        "sum": sum,
        "subtract": subtract,
        "multiply": multiply,
        "divide": divide,
    }
    return operations[operation](x, y)

Essa segunda forma é amplamente usada na comunidade python para simplificar condicionais e deixar nosso código mais limpo e legível ✨

Conjuntos (Sets)

Os conjuntos em python compartilham a mesma implementação da tabela hash por baixo dos panos. Dito isso, os detalhes de performance mencionados acima também são válidos e isso nos permite efetuar operações bastante sofisticadas de forma muito simples e rápida.

Lembram da teoria dos conjuntos da escola? Acontece que isso é algo bastante útil na computação em geral, tanto nas linguagens de programação quanto manipulação de dados (no SQL a teoria dos conjuntos é bem visível)

Seguem abaixo algumas operações:

set_1 = {1, 2, 3, 4, 5, 6}
set_2 = {4, 5, 6, 7, 8, 9}
print(set_1 | set_2)  # Join sets
# {1, 2, 3, 4, 5, 6, 7, 8, 9}
print(set_1 & set_2)  # Intersection
# {4, 5, 6}
print(set_1 ^ set_2)  # Symmetric Difference
# {1, 2, 3, 7, 8, 9}
print(set_1 - set_2)  # Difference
# {1, 2, 3}
print(set_1.issubset(set_2)) # checking if set_2 contains set_1
# False

Quando não usar dicionários?

Como mencionamos acima, os dicionários possuem um certo overhead de memória para que possamos encontrar itens no dicionário de forma rápida. Isso pode ser um problema ao lidar com muitos registros e nesses casos temos algumas alternativas:
- Puxando registros do banco de dados? Use tuplas ou namedtuples. Assim cada coluna do banco de dados estaria em uma posição da tupla e evitamos dois problemas: armazenar o nome da coluna várias vezes & evitamos ter os hash maps que consomem mais memória.
- Fazendo operações em conjuntos grandes de dados? Numpy & Pandas ao resgate. Essas ferramentas são amplamente usadas na ciência de dados por permitirem lidarmos com volumes grandes de dados com uma excelente performance.

Referências

- Livro Python Fluente, Luciano Ramalho. Capítulo 3 — Dicionários e conjuntos
- COMPLEXIDADE de ALGORITMOS I — Noção INTUITIVA, canal Programação Dinâmica
- Estruturas de dados na documentação python