O programador
A ciência da computação
Por muitos anos, ouvi colegas se descreverem como “cientistas da computação.” Também ouvi dizer que, “Qualquer campo de estudo que tiver de colocar ‘ciência’ no nome não é realmente ciência.” Certamente um grande número de pessoas da minha área não teve treinamento formal na ciência da computação, e outro número bastante grande olha com desdém para o trabalho gerado nas universidades e grupos acadêmicos, e com alguma justificativa. Quando foi a última vez que uma porção de símbolos gregos pretendendo descrever um sistema de tipos o ajudou a colocar em funcionamento um aplicativo de linha de negócios?
Conheço várias pessoas muitíssimo inteligentes, e uma delas é Joe Hummel, alguém que legitimamente faz jus ao título de cientista da computação, graças ao Ph.D. por trás de seu nome e tudo mais. Pedi a ele para se juntasse a mim ao escrever essa coluna para explorar a ciência da computação. Pensei que seria interessante começar com algumas das partes mais simples da ciência de computação e prosseguir com como entender a teoria por trás de algumas dessas partes pode, de fato, tornar sua vida como programador um pouco mais fácil.
Para essa edição, atacamos a discussão clássica do “Grande O”, que procura nos dar uma maneira consistente de descrever um conceito simples: De quantos recursos (tempo, memória, potência, etc.) o computador precisará para executar um determinado programa? Essa determinação é conhecida como análise de algoritmos, com o objetivo de colocar seu algoritmo escolhido em uma categoria matemática específica. Por que? Para que você possa selecionar o melhor para uma situação. Há muitas categorias, com cada categoria sucessiva indicando um salto no consumo de recursos. Vamos nos concentrar no tempo de execução e apenas as três primeiras categorias: O(1), O(lgN) e O(N). Como é típico, N indica o número de itens de dados processados pelo algoritmo. Para obter um resumo executivo de aonde vamos com tudo isso, consulte a Figura 1, que destaca o tempo de execução que pode ser esperado de cada categoria à medida que N cresce.
Figura 1 Tempos de execução à medida que o número de itens processados (N) cresce
Um algoritmo de ordem N é escrito como O(N), pronunciado “Grande O de N” e também conhecido como “linear.” Dados N itens de dados, um algoritmo O(N) assume a ordem de N etapas de tempo. Um algoritmo de ordem log N é escrito como O(lgN), pronunciado “Grande O de log N” e referido como “logarítmico.” Dados N itens de dados, um algoritmo O(lgN) assume a ordem de log2(N) etapas de tempo (muito menos). Finalmente, um algoritmo de ordem 1 é escrito como O(1), pronunciado “Grande O de 1” e referido como “constante.” Para N itens de dados, um algoritmo O(1) assume um número constante de etapas de tempo (menos ainda). Reserve um momento para olhar novamente a Figura1. O que mais esse gráfico transmite? Por exemplo, observe que quando N dobra, um algoritmo linear leva duas vezes mais tempo.
Vamos dar uma olhada em um exemplo de como isso se aplica à vida real, e onde saber apenas um pouco sobre análise de algoritmo pode causar um grande impacto. Suponha que você receba um arquivo de log para pesquisar correspondências em relação a uma lista de endereços IP suspeitos. Bem simples:
List<string> suspicious = BuildList(); /* step 0 */
foreach (string line in logfile)
{
string ipaddr = parse(line); /* step 1 */
if (suspicious.Contains(ipaddr)) /* step 2 */
matches++; /* step 3 */
}
Como categorizamos a complexidade de tempo dessa abordagem? Vamos supor que haja M linhas no arquivo de log e N endereços IP suspeitos. Criar uma lista não classificada de N elementos (etapa 0) produzirá um custo único de O(N). O loop executará M iterações, portanto, o custo do loop será O(M * custo de uma iteração). Cada iteração executa três etapas básicas:
- Analisa a linha
- Pesquisa a lista
- Incrementa as correspondências se uma correspondência for encontrada
Tornando-se analítico
O aspecto intelectual da análise de algoritmo é saber o que contar e o que não contar. Por exemplo, embora analisar uma linha, talvez aplicando uma expressão regular ou dividindo a linha em tokens, possa custar caro, leva uma quantidade de tempo constante em relação aos dados. Em outras palavras, o tempo necessário para analisar uma linha permanece inteiramente inalterado, haja M ou 2M linhas no arquivo. Também não se altera haja N ou 2N endereços IP suspeitos. Assim, dizemos que as etapas 1 e 3 levam c (constante) de tempo. No entanto, a etapa 2, que pesquisa a lista, muda em relação ao número de endereços IP suspeitos:
if (suspicious.Contains(ipaddr))
O método Contains executa uma pesquisa linear, começando do primeiro elemento e pesquisando até uma correspondência ser encontrada ou o fim da lista ser atingido. (Como poderíamos saber disso? De uma das três maneiras: testamos, olhamos o código-fonte ou a documentação da Biblioteca MSDN nos diz.)
Com dados aleatórios, na média pesquisaremos a metade da lista, exigindo N/2 etapas. Isso estaria bem para a maioria dois casos, mas nesse caso em particular, um argumento mais forte é que a maioria dos endereços IP no arquivo de log são confiáveis, pois nosso servidor Web não é um banco ou um site de candidato presidencial. Isso significa que em vez de existir mesmo uma chance de que um determinado cliente não seja confiável, a grande maioria das pesquisas irá esgotar a lista sem encontrar uma correspondência, precisando de N etapas.
Como as constantes são descartadas ao computar a ordem das coisas, a pesquisa é O(N) em qualquer caso, resultando em uma complexidade de O(M * N) para o loop. Por sua vez, isso resulta em uma complexidade de algoritmo geral de:
= O(build + loop)
= O(N + M * N)
= O( (1 + M) * N )
= O(M * N)
Portanto, a versão 1 de nossa solução requer O(MN) de tempo.
‘Dados, dados, dados! não posso fazer tijolos sem argila!’
A primeira pergunta a ser feita a si próprio é: “Precisamos de uma algoritmo melhor?” M é normalmente grande, na casa de milhões (possivelmente bilhões) de linhas. Não há nada a ser feito sobre isso, pois você tem de acessar cada linha para pesquisá-la. Se N, o número de endereços IP suspeitos, é pequeno (digamos, N < 100), então seu trabalho está feito. Com as máquinas rápidas atuais, há uma pequena diferença mensurável entre M etapas de tempo e 100M etapas de tempo. No entanto, à medida que N aumenta (por exemplo, N >> 100, ou significativamente maior que 100), vale a pena considerar outros algoritmos de pesquisa.
A menos que você tenha um orçamento de hardware realmente grande, é claro. (Às vezes, mesmo assim.)
Um algoritmo mais eficiente é a pesquisa binária, que vai até o meio e então pesquisa para a esquerda ou direita dependendo de se o elemento que está procurando é menor que o elemento do meio ou maior. Cortando o espaço da pesquisa pela metade a cada vez, o algoritmo exibe o comportamento O(lgN). O que isso significa na prática? Considerando N=1.000 elementos, no pior caso a pesquisa binária leva na ordem de 10 etapas de tempo (210 ≈ 1.000), enquanto a pesquisa linear leva 1.000. Para N = 1 milhão, a diferença é ainda mais dramática, na ordem de 20 etapas de tempo versus 1 milhão. A desvantagem principal é que a pesquisa binária requer que os dados estejam em ordem classificada. Aqui está o programa de pesquisa do arquivo de log reescrito para usar pesquisa binária:
List<string> suspicious = BuildList(); /* step 0 */
suspicious.Sort(); /* step 0.5 */
foreach (string line in logfile)
{
string ipaddr = parse(line); /* step 1 */
if (suspicious.BinarySearch(ipaddr) >= 0) /* step 2 */
matches++; /* step 3 */
}
Classificar a lista suspeita (etapa 0.5) representa um custo único de O(NlgN), enquanto o custo por iteração é reduzido de O(N) para O(lgN) considerando a pesquisa binária mais eficiente (etapa 2). Isso resulta em uma complexidade geral de algoritmo de:
= O(build + sort + loop)
= O(N + N * lgN + M * lgN)
= O(N * (1 + lgN) + M * lgN)
= O(N * lgN + M * lgN)
= O((N + M) * lgN)
Em nosso cenário, em que M >> N, o N age mais como uma pequena constante quando adicionada a M, assim, a versão 2 de nossa solução requer aproximadamente O(MlgN) de tempo. E então? Para N = 1.000 endereços IP suspeitos, reduzimos apenas o tempo de execução de uma ordem de 1.000M etapas de tempo para 10M, que é 100x mais rápido. O tempo de classificação adicional de aproximadamente 10.000 etapas de tempo (O(NlgN)) é mais que compensada pela economia repetida no tempo de pesquisa.
Vamos fazer hash
Quando você sabe algo sobre os dados que está pesquisando, você pode(e deve) criar uma tabela de hash. O hash reduz o tempo médio de pesquisa a O(1). Não é possível fazer nada melhor do que isso. Ele faz isso criando um mapeamento de um valor único para os elementos armazenados na tabela, onde esse valor é produzido por uma função de hash. O principal requisito para o hash é a existência de uma boa função de hash que mapeie os dados da pesquisa em um intervalo de inteiros, com poucos conflitos (mapeamentos duplicados). Nosso programa de arquivo de log revisado (versão 3) aproveita o suporte interno do hash efetivo de cadeia de caracteres do Microsoft .NET Framework:
Dictionary<string, int> suspicious = BuildHashTable(); /* step 0 */
foreach (string line in logfile)
{
string ipaddr = parse(line); /* step 1 */
if (suspicious.ContainsKey(ipaddr)) /* step 2 */
matches++; /* step 3 */
}
Criar a tabela de hash (etapa 0) produz um custo único e inicial de O(N). Isso resulta em uma complexidade geral de algoritmo de:
= O(build + loop)
= O(N + M * 1)
= O(N + M)
Supondo nosso cenário de M >> N, a versão 3 é nossa solução mais rápida, aproximadamente no tempo de O(M). Para N = 1.000 endereços IP suspeitos, reduzimos apenas o tempo de execução por outro fator de 10, que é 1.000x mais rápido do que nossa versão original. E o que é impressionante a respeito dessa abordagem é que mesmo para valores maiores que N, digamos 10.000, ou mesmo 100.000, o tempo de execução é o mesmo, na ordem de M etapas de tempo.
Então, qual é o problema? Com a versão 2 e pesquisa binária, é simples: A lista de endereços IP deve ser primeiramente classificada. Nessa versão com hash, há três problemas a considerar: criar uma função de hash efetiva, o custo de construção inicial e um espaço de memória maior. A chave é a função de hash. Uma função de hash efetiva espalha os dados pela tabela com um mínimo de conflitos, eliminando a necessidade de pesquisa adicional após o hash inicial na tabela. Tal função oferece um custo de construção inicial de O(1) por dado, ou O(N), o mesmo da pesquisa linear. No entanto, tal efetividade normalmente envolve um fator de carga na vizinhança de 10%, o que significa que os dados ocupam somente 10% da tabela. O hash então requer um espaço de memória 10x maior do que a pesquisa linear ou binária, embora, formalmente, isso ainda é O(N) como as outras.
Por que estamos fazendo isso, novamente?
Depois de toda essa pseudomatemática, deve ocorrer ao formado em ciências não da computação que fizemos muita manipulação teórica, e embora pensemos que encontramos uma solução eficiente, certamente descartamos muitas constantes ao longo do caminho. E isso nos leva à pergunta de um milhão de dólares: “Nossa análise teórica realmente compensa na prática?” Uma pergunta razoável, especialmente quando você considera o objetivo final deste artigo—encorajá-lo a usar a análise de algoritmo (se ainda não está) para avaliar as abordagens concorrentes antes de confirmar o código.
Muitas vezes me sentei em volta de uma mesa vendo os engenheiros discutindo por horas, mesmo dias, algumas vezes, se a abordagem A é melhor que a abordagem B. Raramente os caras pegam um papel e fazem uma rápida análise de algoritmo.
Bem, agora que fizemos a análise, vamos executar alguns testes e ver o que acontece na prática. Para isso, geramos arquivos de log aleatórios com M entradas e, então, pesquisamos esses arquivos com relação a listas aleatoriamente geradas de N endereços IP. (Arquivos de código-fonte e de entrada completos estão disponíveis em bit.ly/srchlogfiles.)
Para recapitular, supondo que M >>N, derivamos as complexidades do algoritmo mostradas na Figura 2.
Figura 2 Complexidades do algoritmo supondo queM >> N
| Tempo (t) | |
| Versão 1: usando pesquisa linear | O(M * N) |
| Versão 2: usando pesquisa binária | O(M * lgN) |
| Versão 3: usando hash | O(M) |
Para nossos testes, definimos M como 1 milhão, e dobramos N para cada teste: 128, 256, 512 e assim por diante. Dobrar N destaca as características de desempenho dos algoritmos de pesquisa. Se nossa análise estiver precisa, cada vez que N for dobrado, o tempo de execução deverá mudar, conforme mostrado na Figura 3.
Figura 3 Alteração prevista no tempo de execução quandoNé dobrado
| Tempo para 2N | |
| Versão 1 | O(M * 2 * N) => 2 * O(M * N) => 2t |
| Versão 2 | O(M * lg(2N)) => O(M * (lg2 + lgN)) => O(M * (1 + lgN) => O(M + M * lgN) => M + O(M * lgN) => M + t |
| Versão 3 | O(M) => t |
Em outras palavras, a versão 1 deve dobrar em tempo (2t), a versão 2 deve levar mais M etapas de tempo (t + M) e a versão 3 não deve levar mais tempo adicional (t). A Figura 4 mostra os tempos registrados reais (em segundos).
Figura 4 Tempos de execução reais (segundos)
| M | N | Versão 1 | Versão 2 | Versão 3 |
| 1,000,000 | 128 | 3.81 | 2.88 | 2.15 |
| 256 | 5.65 | 2.98 | 2.15 | |
| 512 | 9.39 | 3.11 | 2.17 | |
| 1,024 | 16.78 | 3.23 | 2.19 | |
| 2,048 | 31.52 | 3.36 | 2.19 | |
| 4,096 | 61.18 | 3.49 | 2.28 | |
| 8,192 | 120.63 | 3.68 | 2.39 | |
| 16,384 | 238.86 | 3.95 | 2.54 | |
| 32,768 | 473.91 | 4.34 | 2.89 |
Como você pode ver na Figura 4, a versão 1, baseada em pesquisa linear, de fato dobra no tempo à medida que N dobra. Provavelmente, é uma coisa ruim para a maioria das situações.
A versão 2, baseada em pesquisa binária, é executada muito mais rapidamente que a versão 1 e cresce muito mais lentamente. A taxa de crescimento é mais difícil de quantificar, pois depende do tempo TM para executar M operações, que parece estar entre 0,1 e 0,3 segundos. De acordo com nossa análise, a versão 2 deve estar crescendo a uma taxa constante de TM à medida que N dobra, mas esse não parece ser o caso; pode ser o resultado da pressão de cache aumentado (e, portanto, erros de cache) à medida que N cresce.
Finalmente, a Figura 4 confirma que a versão 3 é, de fato, o algoritmo mais rápido, com essencialmente o mesmo tempo de execução independentemente de N (embora, novamente, não muito constante).
Busque o equilíbrio
De uma perspectiva pragmática, não está claro que o aperfeiçoamento da versão 2 para a versão 3 vale nada mais que uma quantidade trivial de esforço, apesar da economia de mais de um segundo. A economia potencial não vai realmente fazer uma grande diferença, a menos que comecemos a ver valores realmente grandes de M e N (lembrando que o hash pode exigir 10x mais memória para armazenar os endereços IP). E isso levanta o último ponto: saber quando parar de buscar a otimização. Pode ser excitante e atraente para um programador descobrir o algoritmo absoluto mais rápido para executar alguma espécie de operação, mas a menos que essa operação esteja bem na cara do usuário, o tempo gasto tentando otimizar aquele último segundo, com frequência, poderia ser muito mais bem gasto trabalhando em algo mais. Claramente, o salto da versão 1 para a versão 2 vale o tempo (é uma economia de cerca de 10.000%), mas como com todas as coisas, o programador deve buscar o equilíbrio. Algumas vezes a teoria deve dar lugar à prática, mas outras vezes, a teoria ajuda a ditar onde devemos colocar nossos esforços em prática.
Boa codificação.
Ted Neward é um consultor de arquitetura na Neudesic LLC. Ele já escreveu mais de 100 artigos e é autor ou coautor de dezenas de livros, incluindo “Professional F# 2.0” (Wrox, 2010). Ele é um MVP de C# e participa como palestrante em conferências em todo o mundo. Ele atua como consultor e mentor regularmente. Entre em contato com ele pelos emails ted@tedneward.com ou Ted.Neward@neudesic.com se desejar que ele venha trabalhar com sua equipe ou leia seu blog em blogs.tedneward.com.
Joe Hummel é um consultor particular, membro da equipe técnica na Pluralsight LLC, um instrutor da MVP-Training.net e um pesquisador visitante no Departamento de Ciências da Computação da Universidade da Califórnia, Irvine. Ele obteve o grau de Ph.D. na UC Irvine na área de computação de alto desempenho e é interessado em todas as coisas paralelas. Ele reside na área de Chicago e, quando não está velejando, pode ser contatado pelo email joe@joehummel.net.