Como Conjuntos Funcionam de Forma Diferente

Conjuntos: Construídos para Perguntas de Pertencimento

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

Quando você verifica pertencimento, o computador calcula o mesmo hash & salta diretamente para o local certo. Sem verificação.

# A set of pets
pets = {"cat", "dog", "cat", "fish", "dog"}

print(pets)      # {"cat", "dog", "fish"} — duplicates removed
print(len(pets)) # 3 — only unique items

Observe três diferenças em relação às listas:

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

2. Nenhuma 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.

A troca: você perde ordem & duplicatas. Você ganha O(1) para testar pertencimento — verificar se um item existe leva o mesmo tempo se o conjunto tem 5 itens ou 5 milhões.

# Membership check — is "fish" in the set?
if "fish" in pets:    # hash("fish") → jump to bucket → found
    print("found!")   # checked exactly 1 spot, not 4

Pertencimento em Conjunto vs Lista

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

students = {"Alex", "Maria", ..., "Zara", ...}  # 500 names
if "Zara" in students:
    print("enrolled")

Comparação Lado a Lado

Folha de Dicas de Operações

Use uma lista quando você precisa de:

- Itens em uma ordem específica (uma playlist, uma receita, uma fila)

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

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

Use um conjunto quando você precisa de:

- Verificações de pertencimento rápidas ("Já vi isso antes?")

- Remoção automática de duplicatas

- Sem preocupação com ordem

Use ambos quando você precisa de ordem E consulta rápida:

seen = set()     # O(1) membership checks
result = []      # preserves insertion order
for item in data:
    if item not in seen:  # O(1) check
        seen.add(item)    # O(1) add
        result.append(item)  # O(1) append
# Total: O(N) — one pass, each step O(1)

Este padrão "conjunto + lista" oferece o melhor dos dois: resultados ordenados com detecção rápida de duplicatas.

Escolha a Estrutura Certa

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

1. Você precisa armazenar uma playlist de músicas na ordem em 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 distribuição, mas mantê-los na ordem em que se inscreveram.

O Problema da Deduplicate

Problema: Remover Duplicatas, Manter Ordem

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

Tentativa 1: apenas 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) scan of unique list
        unique.append(email)
# Works! But: O(N) check × N items = 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ápido)

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) hash lookup
        seen.add(email)     # O(1) add to set
        unique.append(email) # O(1) append to list
# O(1) check × N items = O(N)

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

Calcular a Aceleração

A versão apenas lista é executada em O(N²). A versão conjunto+lista é executada em O(N).

Você tem 10.000 inscrições de email para deduplicate.

Encontrando Elementos Comuns

Problema: Encontrar Itens em Ambas as Listas

Você tem duas listas de classe. Você precisa encontrar alunos inscritos em ambas as classes.

Abordagem lenta: loops aninhados O(N × M)

class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b = ["Bob", "Diana", "Eve", "Frank"]
both = []
for student in class_a:        # N iterations
    if student in class_b:     # M scans each time
        both.append(student)
# O(N × M) — each student scanned against all of class_b

Abordagem rápida: converter uma lista para conjunto O(N + M)

class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b_set = set(class_b)     # O(M) to build
both = []
for student in class_a:        # N iterations
    if student in class_b_set: # O(1) each time
        both.append(student)
# O(N + M) — build the set once, check N times at O(1) each

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

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

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

Reescrever para Velocidade

Uma escola tem dois clubes com 200 membros cada. Este código encontra alunos 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)

Seu Framework de Decisão

Seu Framework de Decisão de Estrutura de Dados

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

1. Preciso que os itens estejam em ordem? → lista

2. Preciso de verificações de pertencimento rápidas? → conjunto

3. Preciso de ordem E verificações rápidas? → conjunto + lista juntos

4. Preciso de duplicatas? → lista (conjuntos descartam duplicatas)

---

A percepção principal desta lição: o mesmo programa, resolvendo o mesmo problema, pode rodar 1.000× a 1.000.000× mais rápido apenas escolhendo a estrutura de dados certa. Sem truques inteligentes. Sem matemática complicada. Apenas perguntando: que operações meu código faz com mais frequência? Depois escolhendo a estrutura onde essas operações custam O(1) em vez de O(N).

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

---

Quer aprofundar? Nossa lição de Big O cobre taxas de crescimento & cálculos de escala em detalhes. Veja Big O: How Fast Is Fast Enough?. Nosso curso unhamming cobre o defeit real (MOAD-0001) onde exatamente essa correção de lista para conjunto produziu uma aceleração de 1.000× em software de produção. Veja The Missing Chapter: Algorithmic Complexity.

Debugar Este Código

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

words = book.split()           # list of all words
unique_count = 0
checked = []
for word in words:             # N words
    if word not in checked:    # scans checked list
        checked.append(word)
        unique_count += 1
print(unique_count)

O livro tem 100.000 palavras.