Sets em Python: Desvendando O(1) com Operações de Conjunto

Se você já usou um set em Python apenas para remover duplicatas com um .add() aqui e ali, está deixando na mesa uma das estruturas de dados mais poderosas e mal compreendidas da linguagem. Sets não são apenas listas sem duplicatas — são implementações de conjuntos matemáticos otimizadas para operações de associate arrays com tempo constante O(1), suportando operações que vão de interseção até diferença simétrica com performance que impressiona.

Este artigo explora sets além do básico: como eles funcionam por baixo (hashing e tabelas de hash), quando escolhê-los em vez de listas, como frozenset resolve problemas de mutabilidade, e como operações de conjunto transformam algoritmos lentos em máquinas de performance.

Por que Sets e Não Listas? A Verdade Sobre O(1)

Comece com uma verdade simples: quando você precisa verificar se um elemento existe em uma coleção, uma lista força um loop sobre todos os itens.

1
2
3
4
# ❌ LENTO: O(n)
numeros = [1, 2, 3, 4, 5, 1000000]
if 1000000 in numeros:  # Precisa comparar com cada elemento até encontrar
    print("Achei!")

Um set, por outro lado, usa hashing: transforma o valor em um índice de tabela de hash, pulando direto para a posição certa.

1
2
3
4
# ✅ RÁPIDO: O(1)
numeros_set = {1, 2, 3, 4, 5, 1000000}
if 1000000 in numeros_set:  # Hash calcula o índice, acesso direto
    print("Achei!")

A diferença não é teórica. Em uma coleção com 1 milhão de elementos, a verificação em lista faz até 1 milhão de comparações. O set faz uma. O código é idêntico em aparência; o desempenho é um abismo.

Eis o trade-off: sets usam mais memória (por causa da tabela de hash) e seus elementos precisam ser hashable (imutáveis ou ao menos implementar __hash__ corretamente). Mas quando você precisa de busca ou verificação de existência, esse investimento volta multiplicado.

Operações de Conjunto: Matemática Aplicada

Sets implementam as operações da teoria de conjuntos. Se você aprendeu sobre união, interseção e diferença em aulas de matemática, prepare-se para usá-las em produção.

União: Combinar Sem Duplicatas

1
2
3
4
5
6
7
8
admins = {'alice', 'bob', 'charlie'}
moderadores = {'charlie', 'diana', 'eve'}

todos_gerentes = admins | moderadores
# {'alice', 'bob', 'charlie', 'diana', 'eve'}

# Método alternativo
todos_gerentes = admins.union(moderadores)

Prático? Combine IDs de dois bancos de dados sem duplicatas com uma linha. Em código tradicional, você faria um for loop com verificações manuais.

Interseção: O que Está em Ambos

1
2
3
4
5
6
7
8
usuarios_ativos_hoje = {'alice', 'bob', 'diana'}
usuarios_com_assinatura = {'bob', 'charlie', 'diana', 'eve'}

clientes_pagos_ativos = usuarios_ativos_hoje & usuarios_com_assinatura
# {'bob', 'diana'}

# Método alternativo
clientes_pagos_ativos = usuarios_ativos_hoje.intersection(usuarios_com_assinatura)

Exemplo real: encontrar usuários que fizeram login e têm conta premium — em uma linha, sem loops aninhados.

Diferença: O que Está em Um Mas Não no Outro

1
2
3
4
5
6
7
8
todos_usuarios = {'alice', 'bob', 'charlie', 'diana'}
usuarios_inativos = {'charlie', 'eve'}  # eve não está em todos_usuarios mesmo

usuarios_ativos = todos_usuarios - usuarios_inativos
# {'alice', 'bob', 'diana'}

# Método alternativo
usuarios_ativos = todos_usuarios.difference(usuarios_inativos)

Remova spam de uma lista em uma operação. Encontre transações que não aparecem em um relatório anterior. Diferença é sua ferramenta para problemas de “exclusão condicional”.

Diferença Simétrica: O que Está em Um OU no Outro, Mas Não em Ambos

1
2
3
4
5
6
changes_branch_a = {'feature_1', 'bugfix_3', 'refactor_2'}
changes_branch_b = {'feature_1', 'docs_5', 'perf_1'}

conflitos_potenciais = changes_branch_a ^ changes_branch_b
# {'bugfix_3', 'refactor_2', 'docs_5', 'perf_1'}
# feature_1 está em ambos, então não aparece

Encontre o que divergiu entre duas versões sem sobreposição. Identifique mudanças únicas em duas branches de git em uma operação.

Frozenset: Imutabilidade Como Feature, Não Acidente

Sets são mutáveis. Você pode adicionar, remover, modificar. Mas isso traz um problema grave: você não pode usar sets como chaves em dicionários ou elementos de outros sets.

1
2
3
4
# ❌ ERRO: TypeError
usuarios_unicos = {
    {'alice', 'bob'}: "grupo_1",  # set não é hashable
}

Aqui entra frozenset — um set imutável que pode ser hashable.

1
2
3
4
5
6
7
# ✅ CORRETO
usuarios_unicos = {
    frozenset(['alice', 'bob']): "grupo_1",
    frozenset(['charlie', 'diana']): "grupo_2",
}

print(usuarios_unicos[frozenset(['alice', 'bob'])])  # "grupo_1"

Ainda melhor: use frozenset como chave quando precisa agrupar por combinações de valores.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
def agrupar_usuarios_por_permissoes(usuarios):
    grupos = {}
    for usuario in usuarios:
        perms = frozenset(usuario['permissions'])
        if perms not in grupos:
            grupos[perms] = []
        grupos[perms].append(usuario['name'])
    return grupos

usuarios = [
    {'name': 'alice', 'permissions': ['read', 'write']},
    {'name': 'bob', 'permissions': ['read', 'write']},
    {'name': 'charlie', 'permissions': ['read']},
]

resultado = agrupar_usuarios_por_permissoes(usuarios)
# {
#     frozenset({'read', 'write'}): ['alice', 'bob'],
#     frozenset({'read'}): ['charlie']
# }

Frozensets também funcionam em cache keys quando você precisa de estruturas complexas como argumentos — com sets mutáveis, você não conseguiria porque o hash mudaria.

Deduplicação em Grande Escala: Quando Ordem Não Importa

Remover duplicatas é a operação mais óbvia com sets, mas muitos engenheiros subestimam o impacto de usar a estrutura errada.

Imagine um pipeline processando 10 milhões de eventos. Precisa garantir que IDs duplicados sejam processados apenas uma vez.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
# ❌ LENTO: O(n²)
def remover_duplicatas_lista(ids):
    resultado = []
    for id in ids:
        if id not in resultado:  # O(n) para cada iteração
            resultado.append(id)
    return resultado

# ✅ RÁPIDO: O(n)
def remover_duplicatas_set(ids):
    return list(set(ids))  # O(1) para cada inserção em set

Em 10 milhões de IDs com 50% de duplicação:

Lista: ~5 bilhões de comparações
Set: ~5 milhões de operações de hash

A diferença é medida em horas vs. segundos.

Mas há uma nuance: sets não mantêm ordem. Se a ordem importa (e frequentemente importa), você tem opções:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
# Opção 1: dict (Python 3.7+) mantém ordem e tem O(1) de lookup
def remover_duplicatas_ordenado(ids):
    return list(dict.fromkeys(ids))

# Opção 2: Combinar set com lista original
ids_originais = [1, 2, 3, 2, 1, 4]
vistos = set()
resultado = []
for id in ids_originais:
    if id not in vistos:
        vistos.add(id)
        resultado.append(id)
# resultado: [1, 2, 3, 4]

A segunda opção é verbose, mas comum em streaming de dados onde você não pode carregar tudo em memória — processa uma vez, usa set para rastrear.

Operações Comparativas: Subconjunto, Superconjunto e Igualdade

Além de operadores matemáticos, sets suportam comparações que simplificam lógica complexa.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
permissoes_alice = {'read', 'write', 'delete'}
permissoes_requeridas = {'read', 'write'}

# Alice tem todas as permissões requeridas?
if permissoes_requeridas <= permissoes_alice:  # issubset
    print("Acesso concedido")

# Há sobreposição?
if permissoes_alice & {'delete', 'admin'}:  # intersecção não vazia
    print("Alice pode deletar ou é admin")

# São iguais?
if permissoes_alice == permissoes_requeridas:  # Comparação direta
    print("Permissões idênticas")

Comparações em sets são otimizadas internamente. <= em um set é mais rápido que verificar manualmente cada elemento.

Casos de Uso Reais: Otimizando Algoritmos

Cache de Palavras-Chave

1
2
3
4
5
6
7
8
palavras_proibidas = {'spam', 'ofensivo', 'malware', 'phishing', ...}  # 100k palavras

def validar_conteudo(texto):
    palavras = set(texto.lower().split())
    return not (palavras & palavras_proibidas)  # Interseção: há overlap?

# O(n) para split + O(k) para interseção de sets
# Muito mais rápido que loop manual em 100k palavras para cada texto

Rastrear Relacionamentos em Grafos

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Grafo:
    def __init__(self):
        self.adjacencia = {}
    
    def adicionar_aresta(self, u, v):
        if u not in self.adjacencia:
            self.adjacencia[u] = set()
        self.adjacencia[u].add(v)
    
    def encontrar_amigos_comuns(self, u, v):
        # Interseção de adjacentes
        amigos_u = self.adjacencia.get(u, set())
        amigos_v = self.adjacencia.get(v, set())
        return amigos_u & amigos_v

grafo = Grafo()
grafo.adicionar_aresta('alice', 'bob')
grafo.adicionar_aresta('alice', 'charlie')
grafo.adicionar_aresta('diana', 'bob')
grafo.adicionar_aresta('diana', 'charlie')

amigos_comuns = grafo.encontrar_amigos_comuns('alice', 'diana')
# {'bob', 'charlie'}

Detecção de Anomalias

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def detectar_ips_suspeitos(logs):
    ips_conhecidos = {'192.168.1.0/24', '10.0.0.0/8', ...}  # whitelist
    ips_log = set()
    
    for log in logs:
        ips_log.add(log['ip'])
    
    suspeitos = ips_log - ips_conhecidos  # Diferença: o que não está no whitelist
    return suspeitos

# Uma linha remove 99% do tráfego legítimo

Armadilhas Comuns

1. Confundir Set com Dict por Causa da Sintaxe

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
# ❌ Isso é um dict vazio, não um set!
x = {}
print(type(x))  # <class 'dict'>

# ✅ Use set() para set vazio
x = set()
print(type(x))  # <class 'set'>

# Ou use sintaxe com elementos
x = {1, 2, 3}  # Isso é um set

2. Tentar Adicionar Elementos Mutáveis

1
2
3
4
5
# ❌ ERRO: TypeError
conjunto = {[1, 2], [3, 4]}  # lists não são hashable

# ✅ CORRETO
conjunto = {(1, 2), (3, 4)}  # tuples são hashable

3. Esquecer que Sets Não Têm Ordem Garantida

1
2
3
s = {3, 1, 2}
print(s)  # Pode ser {1, 2, 3} ou {3, 1, 2} ou qualquer ordem
# Ordem é implementação dependente (hash function)

Se ordem importa, use list(sorted(set(...))) ou mantenha dados em dict (Python 3.7+).

Performance: Quando Usar Cada Uma

Operação	List	Dict	Set
Busca	O(n)	O(1)	O(1)
Inserção	O(1) amortizado*	O(1)	O(1)
Remoção	O(n)	O(1)	O(1)
Duplicatas	Permite	Chaves únicas	Único sempre
Hashable	Sim	Não (como valores)	Não
Operações Conjunto	—	—	Otimizado

*Inserção em lista é O(1) no final, O(n) no meio.

Conclusão: O Poder Silencioso dos Conjuntos

Sets em Python não são um detalhe — são um alicerce de algoritmos eficientes. Quando você compreende que if x in meu_set é O(1) e if x in minha_lista é O(n), começa a reescrever código com consciência de performance.

Operações de conjunto (união, interseção, diferença) não são apenas notação matemática bonita — são operações otimizadas que consolidam lógica complexa em uma linha legível e rápida.

E frozensets desbloqueiam caching, agrupamento por chaves complexas, e estruturas de dados imutáveis que os algoritmos modernos exigem.

A próxima vez que escrever um for loop para verificar existência ou remover duplicatas, pergunte-se: será que um set torna isso mais rápido, mais legível e mais pythônico?

Na maioria das vezes, a resposta é sim.

Dúvidas, sugestões ou quer discutir algum aspecto de sets e performance em Python? Encontre-me no Fediverso: @riverfount@bolha.us

Por que Sets e Não Listas? A Verdade Sobre O(1)#

Operações de Conjunto: Matemática Aplicada#

União: Combinar Sem Duplicatas#

Interseção: O que Está em Ambos#

Diferença: O que Está em Um Mas Não no Outro#

Diferença Simétrica: O que Está em Um OU no Outro, Mas Não em Ambos#

Frozenset: Imutabilidade Como Feature, Não Acidente#

Deduplicação em Grande Escala: Quando Ordem Não Importa#

Operações Comparativas: Subconjunto, Superconjunto e Igualdade#

Casos de Uso Reais: Otimizando Algoritmos#

Cache de Palavras-Chave#

Rastrear Relacionamentos em Grafos#

Detecção de Anomalias#

Armadilhas Comuns#

1. Confundir Set com Dict por Causa da Sintaxe#

2. Tentar Adicionar Elementos Mutáveis#

3. Esquecer que Sets Não Têm Ordem Garantida#

Performance: Quando Usar Cada Uma#

Conclusão: O Poder Silencioso dos Conjuntos#