Explorando Algoritmos de Busca para Engenheiros de Redes: Linear Search vs. Binary Search
pDamasceno
Como engenheiros de redes, frequentemente lidamos com grandes conjuntos de dados, como endereços IP ou sub-redes. Realizar buscas eficientes nesses conjuntos é crucial para tarefas de automação, como encontrar uma sub-rede específica em um inventário de rede. Neste artigo, exploraremos dois algoritmos de busca fundamentais — linear search e binary search
Gerando os Dados
Para simular um inventário de rede, criaremos um conjunto de sub-redes /24 no range10.0.0.0/8 (por exemplo, 10.0.0.0, 10.0.1.0, ..., 10.255.255.0). O script Python a seguir gera três arquivos: uma lista ordenada, uma lista invertida e uma lista aleatória de sub-redes.
import ipaddress
import random
# Gera todas as sub-redes /24 de 10.0.0.0/8
subnets = list(ipaddress.ip_network("10.0.0.0/8").subnets(new_prefix=24))
networks = [str(n.network_address) for n in subnets]
# Sub-redes ordenadas
with open("ordered_ip.txt", "w") as f:
f.write("\n".join(networks))
# Sub-redes invertidas
with open("reverse_ip.txt", "w") as f:
f.write("\n".join(reversed(networks)))
# Sub-redes aleatórias
random.shuffle(networks)
with open("random_ip.txt", "w") as f:
f.write("\n".join(networks))
Este script produz:
ordered_ip.txt: Sub-redes em ordem crescente (10.0.0.0,10.0.1.0, ...).reverse_ip.txt: Sub-redes em ordem decrescente (10.255.255.0,10.255.254.0, ...).random_ip.txt: Sub-redes em ordem aleatória.
Cada arquivo contém 65.536 sub-redes (256 × 256), ideal para testar o desempenho das buscas.
Linear Search: A Abordagem Direta
O linear search é como verificar cada dispositivo em um rack, um a um, até encontrar o que você procura. Ele examina cada elemento de uma lista até encontrar uma correspondência ou chegar ao final.
Como Funciona
Imagine procurar pela sub-rede 10.0.5.0 em uma lista ordenada:
Sub-redes: 10.0.0.0 10.0.1.0 10.0.2.0 10.0.3.0 10.0.4.0 10.0.5.0
Índices: 0 1 2 3 4 5
Verifica
10.0.0.0→ Sem correspondência.Verifica
10.0.1.0→ Sem correspondência.Continua até encontrar
10.0.5.0(6 passos).
Desempenho:
Melhor caso: O alvo está no início (1 passo, O(1)).
Pior caso: O alvo está no final ou ausente (n passos, O(n), onde n é o tamanho da lista).
Para 65.536 sub-redes, o pior caso significa verificar todas as 65.536 entradas
Código do Linear Search
import sys
import time
from ipaddress import ip_address
# Lê as sub-redes e converte para inteiros para comparação
with open(sys.argv[1], "r") as file:
data = [str(ip_address(line.strip())) for line in file]
# Obtém a sub-rede alvo do usuário
target = str(ip_address(input("Digite uma sub-rede /24 (ex., 10.80.40.0): ")))
start_time = time.time()
for prefix in data:
if prefix == target:
print(f"Encontrado {ip_address(target)} com linear search")
break
print(f"Tempo: {time.time() - start_time:.4f} segundos")
Binary Search: Dividir e Conquistar
O binary search é como solucionar um problema de rede dividindo o espaço do problema ao meio repetidamente. Ele requer uma lista ordenada, mas é significativamente mais rápido para grandes conjuntos de dados.
Como Funciona
Na mesma lista, procurando por 10.0.5.0:
Sub-redes: 10.0.0.0 10.0.1.0 10.0.2.0 10.0.3.0 10.0.4.0 10.0.5.0
Índices: 0 1 2 3 4 5
Encontra o ponto médio:
(0 + 5) // 2 = 2(10.0.2.0).Compara:
10.0.2.0<10.0.5.0, então ignora a metade esquerda (índices 0–2).Nova lista:
10.0.3.0,10.0.4.0,10.0.5.0.Novo ponto médio:
(3 + 5) // 2 = 4(10.0.4.0).Compara:
10.0.4.0<10.0.5.0, ignora o índice 4.Verifica
10.0.5.0→ Encontrado em 3 passos!
Desempenho:
Melhor caso: O alvo está no ponto médio (1 passo, O(1)).
Pior caso: O(log n), onde n é o tamanho da lista. Para 65.536 sub-redes, são necessários no máximo ~16 passos (log₂(65.536) ≈ 16).
O binary search é exponencialmente mais rápido que o linear search para grandes conjuntos.
Código do Binary Search
import sys
import time
from ipaddress import ip_address
def binary_search(arr, target):
arr = sorted(arr) # Garante que a lista está ordenada
start = 0
end = len(arr) - 1
while start <= end:
mid = (start + end) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
start = mid + 1
else:
end = mid - 1
return -1
# Lê as sub-redes e converte para inteiros
with open(sys.argv[1], "r") as f:
data = [str(ip_address(line.strip())) for line in f]
# Obtém a sub-rede alvo
target = str(ip_address(input("Digite uma sub-rede /24 (ex., 10.80.40.0): ")))
start_time = time.time()
index = binary_search(data, target)
if index != -1:
print(f"Encontrado {ip_address(target)} com binary search")
else:
print(f"Sub-rede {ip_address(target)} não encontrada")
print(f"Tempo: {time.time() - start_time:.4f} segundos")
Comparação de Desempenho
Para ilustrar a diferença, testamos ambos os algoritmos em nossos conjuntos de sub-redes. Resultados para a busca de 10.255.255.0 (pior caso para linear search em ordered_ip.txt):
Linear Search: ~0.008 segundos (65.536 verificações).
Binary Search: ~0.0001 segundos (~16 verificações).
Para uma sub-rede aleatória como 10.80.40.0 em random_ip.txt:
Linear Search: ~0.004 segundos (caso médio).
Binary Search: ~0.0001 segundos (incluindo a sobrecarga de ordenação).
O gráfico abaixo visualiza o número de passos necessários conforme o tamanho do conjunto de dados aumenta:
Aplicação Prática em Automação de Redes
Imagine que você está automatizando uma tarefa para encontrar uma sub-rede específica em uma tabela de roteamento ou sistema IPAM. O linear search funciona para listas pequenas, mas se torna impraticável para milhares de sub-redes. O binary search, com sua eficiência O(log n), é ideal para dados de rede em grande escala, especialmente se os dados já estiverem ordenados (comum em bancos de dados ou ferramentas IPAM).
Exemplo de Caso de Uso: Você está validando se uma sub-rede existe no inventário de uma rede antes de atribuí-la a uma nova VLAN. O binary search garante buscas rápidas, minimizando o tempo de execução do script e melhorando a eficiência da automação.
Desafio Interativo
Experimente este exercício prático para ver os algoritmos em ação:
Salve o script de geração de sub-redes como subnets.py e execute-o para criar os três arquivos.
Combine os scripts de linear search e binary search em um único arquivo
import sys import time from ipaddress import ip_address def linear_search(arr, target): for i, prefix in enumerate(arr): if prefix == target: return i return -1 def binary_search(arr, target): arr = sorted(arr) start, end = 0, len(arr) - 1 while start <= end: mid = (start + end) // 2 if arr[mid] == target: return mid elif arr[mid] < target: start = mid + 1 else: end = mid - 1 return -1 # Lê as sub-redes with open(sys.argv[1], "r") as f: data = [int(ip_address(line.strip())) for line in f] # Obtém a sub-rede alvo target = int(ip_address(input("Digite uma sub-rede /24 (ex., 10.80.40.0): "))) # Linear search start_time = time.time() index = linear_search(data, target) print(f"Linear Search: {'Encontrado' if index != -1 else 'Não encontrado'} {ip_address(target)}") print(f"Tempo: {time.time() - start_time:.4f} segundos") # Binary search start_time = time.time() index = binary_search(data, target) print(f"Binary Search: {'Encontrado' if index != -1 else 'Não encontrado'} {ip_address(target)}") print(f"Tempo: {time.time() - start_time:.4f} segundos")Execute o script com diferentes arquivos e sub-redes:
search_subnets.py ordered_ip.txtExperimente buscar por
10.0.0.0(melhor caso),10.255.255.0(pior caso) e uma sub-rede aleatória como10.80.40.0.
Desafio: Modifique o script para contar o número de comparações que cada algoritmo faz e imprima-os. Isso ajudará a visualizar a diferença de eficiência diretamente!
Subscribe to my newsletter
Read articles from pDamasceno directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by