Como os Conjuntos Funcionam Diferentemente

Conjuntos: Feitos para Perguntas de Membro

Um conjunto armazena itens únicos usando uma técnica chamada hashing. Quando você adiciona um item, o computador calcula um hash (uma impressão digital numérica) que diz a ele exatamente onde armazenar esse item.

Quando você verifica o membro, o computador calcula o mesmo hash e pula diretamente para o lugar certo. Sem escaneamento.

# Um conjunto de pets
pets = {"gato", "cão", "gato", "peixe", "cão"}

print(pets)      # {"gato", "cão", "peixe"} — duplicatas removidas
print(len(pets)) # 3 — apenas itens únicos

Observe três diferenças das listas:

1. Sem duplicatas. "gato" apareceu duas vezes na entrada, mas o conjunto mantém apenas uma cópia.

2. Sem ordem garantida. O conjunto pode imprimir itens em qualquer arranjo.

3. Sem acesso por índice. Você não pode escrever pets[0] - conjuntos não têm posições.

O trade-off: você perde a ordem e duplicatas. Ganha O(1) teste de membro - verificar se um item existe leva o mesmo tempo, independentemente de o conjunto ter 5 itens ou 5 milhões.

# Verificação de membro - o "peixe" está no conjunto?
if "peixe" in pets:    # hash("peixe") → salto para o bucket → encontrado
    print("encontrado!")   # verificado exatamente 1 lugar, não 4

Conjunto vs Lista de Membros

Você tem 500 nomes de estudantes armazenados em um conjunto em vez de uma lista.

students = {"Alex", "Maria", ..., "Zara", ...}  # 500 nomes
se "Zara" está na lista de alunos:
    print("matriculado")

Comparação Lado a Lado

Cartão de Operações

Use uma lista quando você precisar:

- Itens em um determinado order (uma playlist, uma receita, uma fila)

- Acesso por posição (items[3])

- Duplicatas preservadas ("gato" aparece 3 vezes = 3 gatos)

Use um conjunto quando você precisar:

- Verificações rápidas de membro ("eu já vi isso antes?")

- Remoção automática de duplicatas

- Sem preocupação com a ordem

Use ambos quando precisar de order E busca rápida:

seen = set()     # O(1) verificações de membro
result = []      # preserva a ordem de inserção
for item in data:
    if item not in seen:  # O(1) verificação
        seen.add(item)    # O(1) adicionar
        result.append(item)  # O(1) anexar
# Total: O(N) - uma passagem, cada etapa O(1)

Este "conjunto + lista" padrão dá a você o melhor de ambos: resultados ordenados com detecção rápida de duplicatas.

Escolha a Estrutura Correta

Três problemas. Para cada um, decida: lista, conjunto ou ambos?

1. Você precisa armazenar uma playlist de músicas na ordem que o usuário adicionou.

2. Você precisa verificar rapidamente se um nome de usuário já foi utilizado.

3. Você precisa remover emails duplicados de uma lista de correio, mas mantê-los na ordem em que se cadastraram.

The Deduplication Problem

Problema: Remover Duplicatas, Manter a Ordem

Você recebe uma lista de inscrições de email. Algumas pessoas se cadastraram duas vezes. Você precisa enviar um email por pessoa, na ordem em que se cadastraram pela primeira vez.

Tentativa 1: somente lista (lenta)

signups = ["alice@a.com", "bob@b.com", "alice@a.com", "carol@c.com"]
unique = []
for email in signups:
    if email not in unique:  # O(N) escaneamento da lista única
        unique.append(email)
# Funciona! Mas: O(N) verificação × N itens = O(N²)

Com 100 inscrições, isso faz ~5.000 verificações. Com 10.000 inscrições: ~50.000.000 verificações.

Tentativa 2: conjunto + lista (rápida)

signups = ["alice@a.com", "bob@b.com", "alice@a.com", "carol@c.com"]
seen = set()
unique = []
for email in signups:
    if email not in seen:   # O(1) busca hash
        seen.add(email)     # O(1) adicionar ao conjunto
        unique.append(email) # O(1) adicionar à lista
# O(1) verificação × N itens = O(N)

Mesmo resultado. Mesma ordem. Mas: 10.000 inscrições agora requerem ~10.000 verificações em vez de ~50.000.000.

Calculate the Speedup

A versão apenas com lista tem complexidade de O(N²). A versão set+list tem complexidade de O(N).

You have 10,000 email signups to deduplicate.

Encontrando Elementos Comuns

Problema: Encontrar Itens em Duas Listas

Você tem duas listas de alunos. Precisa encontrar os estudantes matriculados em ambas as classes.

Abordagem Lenta: laços aninhados O(N × M)

class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b = ["Bob", "Diana", "Eve", "Frank"]
both = []
for student in class_a:        # N iterações
    if student in class_b:     # M scans cada vez
        both.append(student)
# O(N × M) — cada aluno escaneado contra todos de class_b

Abordagem Rápida: converta uma lista em um conjunto O(N + M)

class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b_set = set(class_b)     # O(M) para construir
both = []
for student in class_a:        # N iterações
    if student in class_b_set: # O(1) cada vez
        both.append(student)
# O(N + M) — construa o conjunto uma vez, verifique N vezes com O(1) cada

Ou mesmo mais simples usando a interseção de conjuntos do Python:

both = set(class_a) & set(class_b)  # O(N + M)

O operador & encontra todos os itens que aparecem em ambos os conjuntos.

Escreva para a Velocidade

Uma escola tem dois clubes com 200 membros cada. Este código encontra estudantes em ambos os clubes:

chess_club = [...]   # 200 names
art_club = [...]     # 200 names
both_clubs = []
for student in chess_club:
    if student in art_club:
        both_clubs.append(student)

O quadro de decisão

Seu quadro de decisão de estrutura de dados

Toda vez que você escrever código que armazena uma coleção de itens, pergunte:

1. Eu preciso dos itens em ordem? → lista

2. Eu preciso de verificações de associação rápidas? → conjunto

3. Eu preciso de ambos, ordem E verificações rápidas? → conjunto + lista juntos

4. Eu preciso de duplicatas? → lista (conjuntos descartam duplicatas)

---

A chave de insight desta lição: o mesmo programa, resolvendo o mesmo problema, pode correr 1.000× a 1.000.000× mais rápido apenas escolhendo a estrutura de dados certa. Nenhuma trapaça. Nenhuma matemática complicada. Só perguntar: o que operações meu código faz com mais frequência? Então escolher a estrutura onde essas operações custam O(1) em vez de O(N).

Esta lição cobriu listas e conjuntos. Existem outras estruturas de dados (dicionários, árvores, pilhas) que resolvem outros problemas. O framework de decisão permanece o mesmo: entenda suas operações e então escolha a estrutura que as torna baratas.

---

Quer ir mais fundo? A nossa aula sobre Big O aborda taxas de crescimento e cálculos de escalonamento em detalhes. Confira [Big O: Quanto É O Suficiente?](/en/nu/cs_algorithms_big_o_notation). O nosso curso Unhamming cobre o defeito real-world (MOAD-0001) onde essa exata correção de lista-conjunto produziu uma aceleração de velocidade de 1.000× em softwares de produção. Confira [O Capítulo Faltante: Complexidade Algorítmica](/en/un/unhamming_algorithmic_complexity).

Depure Este Código

Um aluno escreveu esse código para contar quantas palavras únicas aparecem em um livro:

words = book.split()           # lista de todas as palavras
unique_count = 0
checked = []
for word in words:             # N palavras
    if word not in checked:    # escaneia a lista checked
        checked.append(word)
        unique_count += 1
print(unique_count)

O livro tem 100.000 palavras.