Andrei Alexandrescu é uma verdadeira lenda viva. É uma pessoa que fez uma contribuição significativa para a história das linguagens de programação modernas e das técnicas generalizadas e de metaprogramação. Quantas cópias foram quebradas nas discussões
dos Padrões Modernos de Design e
Codificação C ++ 101 (escritos com o Brasão Excepcional C ++ da Sutter) e em outros
livros e artigos . Como co-autor
da linguagem D , ele teve a oportunidade não apenas de teorizar, mas também de tornar seu sonho realidade - e, o que é característico, ele
personificou .
Agora você está segurando em suas mãos um
relatório da conferência DotNext 2018 Piter, que fala sobre modernas tecnologias de otimização. O que o .NET tem a ver com isso? Este é um relatório fundamental de uma pessoa que otimizou toda a sua vida. Se o desempenho é importante para você, você precisa assistir (ou ler este artigo). Bem-vindo ao gato!
A arte do benchmarking
Eu gostaria de discutir com você vários tópicos relacionados ao benchmarking. Para começar, vamos repetir algumas coisas básicas.
A lei de Amdahl faz parte dos clássicos da ciência da computação, é usada principalmente na computação paralela, mas funciona em qualquer sistema complexo. Se queremos melhorar o trabalho de um determinado sistema, precisamos começar onde os principais problemas desse sistema estão concentrados. A lei em si é óbvia: se um componente é 20% do sistema, a melhoria máxima no desempenho do sistema que pode ser alcançada pela otimização da operação de apenas esse componente é de 20%. Muitas vezes tenho que conhecer pessoas (é claro, nossos leitores não pertencem a elas) que fazem coisas como otimizar a análise de linha de comando. Essas operações levam os 10 primeiros microssegundos do seu programa e as pessoas analisam sua complexidade algorítmica e ficam horrorizadas se o tempo for quadrático.
Como você provavelmente sabe, antes de iniciar a otimização, é necessário criar um perfil do aplicativo e selecionar pontos de acesso. Aqui deve ser dito sobre a
lei de Ladma (este não é um sobrenome real, e Amdal, lido ao contrário). Você precisa concentrar seus esforços no componente que leva ao maior investimento de tempo. Ele precisa ser movido para fora do aplicativo, realizar o trabalho necessário, retornar e testar novamente. O motivo pelo qual você precisa fazer isso é que, muitas vezes, uma melhoria de desempenho de 20% é o resultado de dez melhorias de 2%. E na estrutura de um sistema grande, é impossível medir uma melhoria tão pequena. Para isso, o componente deve ser testado em um conjunto de testes. Uma melhoria de 20% no desempenho de um dos principais componentes do sistema pode significar uma melhoria de 5% para o sistema como um todo, e para algumas áreas esse é um excelente resultado. Não se esqueça que as otimizações podem ter vários efeitos globais; portanto, com base nos resultados do benchmarking seletivo, você deve ter muito cuidado ao tirar conclusões sobre a operação do sistema como um todo.
Um erro que tenho certeza de que nossos leitores não cometem, mas que geralmente é bastante comum: as pessoas medem a velocidade da montagem de depuração. Isso nunca deve ser feito. É semelhante a ficar chateado por causa da baixa velocidade do caracol nas corridas: não se destina a uma competição como essa, tem outros objetivos na vida. Outro erro, um pouco menos óbvio: as pessoas medem primeiro o desempenho básico do sistema e imediatamente depois realizam o benchmarking. Mas depois de coletar a linha de base, muitos recursos são aquecidos. Por exemplo, os arquivos abertos são armazenados em buffer e permanecem na memória (pelo menos no Linux). Assim, o segundo teste será mais rápido apenas porque é iniciado após o primeiro. Isso acontece mesmo com chamadas malloc. Após essas chamadas, o sistema não retorna ao seu estado original, mesmo que sejam feitas chamadas de liberação da memória. A configuração interna, o armazenamento em cache e os recursos usados pelo alocador de memória permitem que as seguintes chamadas do malloc sejam executadas muito mais rapidamente. Mesmo sem levar em consideração o efeito do cache, o malloc lembra que, por exemplo, algumas funções alocam memória para objetos de 4 kilobytes várias vezes, o que significa que você precisa ter uma lista livre com um tamanho de elemento de 4 kilobytes. Ou outro exemplo: as pesquisas de DNS são armazenadas em cache para reutilização após a primeira consulta. Se possível, durante o benchmarking, você precisa reiniciar todo o processo todas as vezes, do início ao fim.
Por exemplo, para retornar completamente o sistema ao seu estado original, no caso de arquivos, eles precisam ser abertos em um disco separado, que, após o final do teste, precisa ser removido (como eu entendo, isso pode ser feito no Windows). A operação não é fácil, mas na maioria dos casos é necessária.
Continuando a conversa sobre erros durante a otimização, tive que lidar com esses casos quando os custos de impressão estão incluídos nos resultados do teste. Existem erros de procedimento quando mais de uma coisa é alterada antes de cada medição, o que viola os princípios mais básicos de um experimento científico, uma vez que não está claro qual efeito você está medindo. Outro erro grave é quando alguns casos raros são otimizados, o que leva à pessimização em outras situações.
Aqui está um exemplo com estouro de pilha. O autor geralmente classifica os dados já classificados e fica surpreso, porque a função `is_sorted 'é obviamente muito mais rápida que a classificação` Por que, então, em `classificar a primeira linha não é` se is_sorted retorna? Você está otimizando um caso extremamente raro, dados completamente classificados e todos os outros que têm pelo menos um elemento não classificado terão que arcar com os custos dessa otimização. Não vale a pena fazer isso.
Acho que não preciso provar há muito tempo que as arquiteturas concorrentes de hoje são extremamente complexas: mudança dinâmica de frequência, interrupção por outros processos, virtualização etc. Portanto, é quase impossível obter o mesmo tempo ao medir, seus indicadores sempre tremerão. Portanto, não se deve confiar em coisas que parecem óbvias. Digamos, pode parecer óbvio para nós que menos instruções significam código mais rápido, e isso nem sempre é verdade. Também pode parecer que o uso de dados armazenados sempre será mais rápido do que executar novamente os cálculos; portanto, se você armazenar em cache os resultados, ficará bem. Como no caso anterior, não pode ser declarado inequivocamente, assim como o contrário não pode ser declarado incondicionalmente - tudo depende do contexto. Obviamente, você deve ter apenas uma coisa: tudo precisa ser medido. Se você medir tudo, obterá melhores resultados do que especialistas com conhecimento que não fazem medições.
Há várias práticas razoavelmente confiáveis, cuja discussão pode levar a pensamentos interessantes. Devemos começar com o fato de que a matemática não o decepcionará. Torna possível mostrar que sistemas com velocidades diferentes podem ser equivalentes. A matemática fornece regras para mostrar a equivalência de certas coisas e identificar algumas propriedades e, embora não seja tendenciosa, não importa quais coisas são interessantes e quais não são. Muitas pessoas pensam que a otimização é baseada no conhecimento do código de máquina e no trabalho com bits, mas na verdade tem muita matemática, porque você prova que um sistema mais rápido é equivalente a um mais lento.
Outra regra geral é que os computadores adoram que as coisas sejam entediantes. Você precisa se multiplicar por dois vetores, um bilhão de elementos em cada um? Essa é uma tarefa ideal para um computador, todo o equipamento nele é especialmente afiado para esse tipo de tarefa. Para analisar esses dados, com base neles, para criar uma expressão regular - não quero fazer isso. Os computadores não gostam de coisas como ramificações, dependências, chamadas indiretas, enfim - eles não gostam de código inteligente, gostam de código chato. Os computadores não gostam de gravação indireta - um problema complexo com o qual as pessoas envolvidas no ferro lutam há muito tempo e não conseguem resolver.
Outra regra é que você deve dar preferência às operações menos poderosas, em outras palavras, preferir adição à multiplicação e multiplicação à exponenciação. Novamente, a matemática é útil aqui.
Finalmente, a última regra - quanto menor, mais bonita. O tamanho pequeno permite que os computadores realizem melhor suas vantagens, pois preferem que os dados e principalmente as instruções estejam próximos um do outro. Os resultados de várias medições da velocidade do aplicativo sempre serão diferentes, você terá alguma distribuição dos resultados. Normalmente, apenas medimos a média desses poucos resultados. Mas o problema é que, devido às especificidades dos computadores, a média incluirá muito ruído. Quando Bill Gates monta um ônibus, em média, todo passageiro em um ônibus é um bilionário. Parece ótimo, mas é pouco conforto para um sem-teto andando no mesmo ônibus. Uma situação semelhante ocorre com interrupções: a operação de multiplicação leva nanossegundos, mas quando você faz muitas medições dessas operações, uma delas inevitavelmente terá uma interrupção de dois milissegundos. A diferença é de três ordens de magnitude e, no entanto, os desenvolvedores nem sempre levam isso em conta.
Então, repito: o ruído nos computadores é sempre aditivo; para as pessoas, pode parecer insignificante, mas, para as micro-marcas, é significativo e a média aritmética incluirá muito ruído. Em vez da média, você precisa de um indicador que meça apenas o tempo que você pode influenciar de alguma forma. Se abordarmos essa questão do ponto de vista da matemática, veremos que precisamos encontrar um valor que corresponda ao maior número de medições que fizemos. Em outras palavras, precisamos de um mod. Isso imediatamente nos leva ao problema: o que acontece se você usar o mod quicksort? Se o algoritmo for probabilístico ou se os dados forem aleatórios, quase nunca haverá uma moda. A densidade dos valores será quase a mesma em todo o espectro. Nesse caso, simplesmente descartamos os 5% das maiores medições e depois assumimos o valor médio - ou o máximo, no último caso, teremos um limite que não será excedido em 95% dos casos. Quase sempre haverá um assunto no porão antigo com um modem lento, no qual cada página será carregada por uma hora. Puramente humanos, é claro que simpatizamos com ele, mas não podemos ajudar tecnicamente a todos - portanto, os 5% restantes dos casos devem ser negligenciados. Em geral, ao resolver problemas de rede, geralmente focamos no percentil 95, porque é impossível focar no centésimo. O percentil centésimo significará o resultado mais lento de todas as medições coletadas - isso não é informativo.
Substituir ramificações por aritmética
Como, espero, ficou claro que a medição não é um problema fácil. Vamos dar uma olhada em alguns exemplos e começar tentando substituir ramificação por aritmética. Estamos falando de casos em que precisamos de uma declaração if, mas usá-la com muita frequência é indesejável. Em vez disso, integraremos o resultado da ramificação como um valor 0/1. O código parecerá linear, o computador precisará apenas segui-lo do começo ao fim, sem pensar em qual etapa você deve seguir.
Vamos tentar resolver o seguinte problema: transfira os mínimos de cada quartil da matriz para o primeiro quartil. Em outras palavras, a matriz deve ser dividida em quatro partes e o valor mínimo de cada parte deve ser colocado no início da matriz.
static void min4(double[] p) { int n = p.Length; int i = 0, j = n / 4, k = n / 2, l = 3 * n / 4; for (; i < n / 4; ++i, ++j, ++k, ++l) { int m = p[i] <= p[j] ? i : j; if (p[k] < p[m]) m = k; if (p[l] < p[m]) m = l; Swap(ref p[i], ref p[m]); } }
Acima está o código básico. A propósito, posso relatar orgulhosamente que traduzi esses exemplos para C # e eles foram compilados com êxito. O código em si é bastante simples: `m recebe o índice do menor dos dois valores localizados nos índices` iej, e uma atribuição semelhante é repetida mais duas vezes, dependendo dos outros dois índices. Finalmente, o valor no índice `m é revertido no array com o valor no índice` i. Como você pode ver, contornamos o array usando quatro variáveis indutivas.
O problema de testar esse algoritmo será interessante e não óbvio. Precisamos testá-lo não em um conjunto de dados, mas em dados que podem surgir em vários casos. Por exemplo, em dados que parecem tubos de um órgão: primeiro aumente e depois diminua; em dados aleatórios com uma distribuição uniforme; em um conjunto aleatório de zeros e uns - a partir de apenas dados aleatórios aqui, a diferença é que haverá muitos valores duplicados; em dados já classificados; finalmente, nos dados obtidos por medições reais de algum fenômeno físico. Essa será uma abordagem séria para medir a velocidade de um algoritmo, e geralmente é aceita entre as pessoas que estudam algoritmos.
Vamos tentar melhorar o código que acabamos de conhecer.
static void min4(double[] p) { int q = p.Length / 4; int i = 0, j = n / 4, k = n / 2, l = 3 * n / 4; for (; i < q; ++i, ++j, ++k, ++l) { int m = p[i] <= p[j] ? i : j; if (p[k] < p[m]) m = k; if (p[l] < p[m]) m = l; Swap(ref p[i], ref p[m]); } }
Como primeira otimização, tentaremos evitar repetições excessivas de operações; para isso, realizamos várias operações de divisão do loop - dividindo `n por 2 e 4 e dividindo 3 *` n por 4. Mas após essa otimização, descobrimos que os cálculos não eram para o principal problema: o código não se tornará mais rápido, embora seja mais compacto. Na melhor das hipóteses, obteremos uma melhoria de meio por cento.
static void min4(double[] p) { int q = p.Length / 4; int i = 0, j = q, k = 2 * q, l = 3 * q; for (; i < q; ++i, ++j, ++k, ++l) { int m0 = p[i] <= p[j] ? i : j; int m1 = p[k] <= p[l] ? k : l; Swap(ref p[i], ref p[p[m0] <= p[m1] ? m0 : m1]); } }
A segunda alteração que faremos no código é reduzir as dependências. Na versão anterior do algoritmo, atribuir `m a`k ou` l depende do valor atribuído à linha de m acima. Para reduzir o número de `m dependências, calculamos separadamente` m0 e `m1 e depois os comparamos. Quando realizei essa otimização, esperava uma melhora significativa na velocidade do algoritmo, mas no final ele acabou sendo zero. Mas, na minha opinião, é importante manter o número de dependências no mínimo, por isso salvei o código.
static void min4(double[] p) { int q = p.Length / 4; for (int i = 0; i < q; ++i) { int m0 = p[i] <= p[i + q] ? i : i + q; int m1 = p[i + 2 * q] <= p[i + 3 * q] ? i + 2 * q : i + 3 * q; Swap(ref p[i], ref p[p[m0] <= p[m1] ? m0 : m1]); } }
Vamos agora tentar reduzir o número de variáveis indutivas de quatro para uma e calcularemos as três restantes aritmeticamente, pois elas estão em constante relação uma com a outra. Isso é bem simples: em vez de `k, teremos` i + q, em vez das outras duas variáveis - `i + 2 * q e` i + 3 * q. Eu também tinha grandes esperanças nessa otimização, mas, como a anterior, ela não deu nenhum resultado a tempo. Isso prova novamente a importância das medidas: sem elas, eu poderia me gabar de ter melhorado significativamente a operação do algoritmo e teria argumentos muito significativos.
static void min4(double[] p) { int q = p.Length / 4, q2 = q + q; for (int i = q; i < q2: ++i) { int m0 = p[i - q] < p[i] ? i - q : i; int m1 = p[i + q2] < p[i + q] ? i + q2 ? i + q; Swap(ref p[i - q], ref p[p[m0] <= p[m1] ? m0 : m1]); } }
Como quarta tentativa, reestruturamos o ciclo para eliminar a multiplicação por 3. Isso nos dará uma melhoria de 3%. O resultado ainda não é impressionante. Em seguida, tente se livrar dos operadores ternários.
Para fazer isso, eu gostaria de apresentar uma nova função - `static int optional (sinalizador bool, valor int). Ele converte o valor booleano de entrada em Int32, multiplica por -1 e o passa para o operador AND bit a bit, juntamente com o segundo valor de entrada. Se o sinalizador de entrada for falso, em int32 será 0 e, depois de todas as conversões na saída, obteremos 0. Se o sinalizador de entrada for verdadeiro, em int32 será 1, quando multiplicado por -1, obtemos FFFFFFFF, que após o bit "E" com qualquer número dará esse segundo número. Observe que não há nenhuma declaração if em qualquer lugar, o código é sem ramificação, é chato para um computador (embora pareça complicado para nós).
static void min4(double[] p) { int q = p.Length / 4, q2 = q + q; for (int i = q; i < q2; ++i) { int m0 = i - optional(p[i - q] <= p[i], q); int m1 = i + q + optional(p[i + q2] < p[i + q], q); Swap(ref p[i - q], ref p[p[m0] <= p[m1] ? m0 : m1]); } }
Substituiremos os operadores ternários por esta função opcional, integraremos dentro do cálculo. Nós o aplicamos duas vezes e, no terceiro caso, deixe o ponto de interrogação. Assim, em vez de quatro verificações neste ciclo, terei apenas uma.
A partir dos resultados da medição que você vê no slide, fica claro o quão importante era testar o algoritmo em vários conjuntos de dados diferentes. Em um conjunto, não entenderíamos nada. Em dados aleatórios e reais, temos aceleração mais do que dupla, em tubos de órgãos e dados classificados, temos uma ligeira desaceleração. Isso se deve ao fato de que, no caso de dados classificados para o preditor de transição, não haverá surpresas, eles preverão com 100% de precisão. No caso de tubos de órgãos, teremos uma previsão errada no meio do conjunto de dados - novamente, precisão muito alta. Por outro lado, com dados aleatórios, a diferença entre nossas duas abordagens será enorme. Substituímos todas as verificações imprevisíveis por uma lógica simples. Aqui voltamos a uma verdade simples: os computadores são projetados para computação, como o nome indica (computação em computador). Ramificação, exibição de imagens na tela - tudo isso com desempenho muito pior. Executar "And" bit a bit para eles é muito mais simples do que passar a instrução if.
static void min4(double[] p) { int q = p.Length / 4, q2 = q + q; for (int i = 0; i < q; ++i) { int m = i + optional(p[i + q] < p[i], q); m += optional(p[i + q2] < p[m], q); m += optional(p[i + q2 + q] < p[m], q); Swap(ref p[i], ref p[m]); } }
Tendo finalmente alcançado um resultado positivo da otimização, tentaremos substituir o último operador ternário por nossa função `opcional. Desta vez, o ganho de velocidade será pequeno. Para entender por que isso acontece, você precisa examinar o código gerado. Na versão anterior do código, onde o ponto de interrogação ainda estava presente, o compilador já encontrou uma maneira de executar o código sem ramificação. E quando ele chega ao operador ternário, ele já pode prever. Substituir esta última peça por `opcional resultará em um código um pouco pior. Portanto, repito, é importante fazer medições sempre.
Outro recurso que eu gostaria de recomendar a você é `ifelse without branches, que você vê agora na tela. É verdade que não pude alcançar as melhorias de desempenho em nosso exemplo. Se 0 for passado como um sinalizador, a primeira linha será 0; no segundo, subtraímos 1 de 0 no Int32 e obtemos FFFFFFFF, após o qual esse valor é passado para o "bit" bit a bit "And" junto com o argumento da função `v2, que nos dará esse argumento sem alterações; finalmente, a primeira e a segunda linhas são passadas para o “bit” OR, que, novamente, nos dará `v2. Se o sinalizador for 1, a primeira linha será igual a `v1; no segundo, subtraímos 1 de 1 e obtemos 0, como resultado, a linha inteira será 0 e 0 e `v1 no bit a bit 'OR' fornecerão` v1.
Espero que esse `ifelse sem função de ramificação interesse as pessoas envolvidas no back-end - por enquanto, por algum motivo, os compiladores modernos não usam essa abordagem. Com essas funções, você pode reorganizar os algoritmos para que os compiladores os entendam para você, porque você é mais inteligente e criativo do que seu compilador.
Interseção de conjunto grande
Mude um pouco o assunto da nossa conversa e passe para a interseção de grandes conjuntos. Até agora, estivemos conversando sobre operadores individuais, agora criaremos novos algoritmos, portanto precisaremos nos distrair dos detalhes e abrir nossa mente para uma perspectiva mais ampla. Suponho que você esteja familiarizado com a classificação por mesclagem, multiplique dois vetores e procure por elementos comuns de dois vetores classificados. Dois conjuntos classificados são percorridos e, quando elementos iguais estão neles, isso é considerado uma correspondência. Se um dos dois elementos comparados for menor, ele será alterado. Esse algoritmo é bastante simples, mas muito comum - provavelmente o mais usado no mundo. É usado em todas as consultas de várias palavras, cada uma dessas consultas é a interseção de dois conjuntos. Esse algoritmo, em particular, usa o Google e também deve ser aplicado em todas as consultas ao banco de dados.
int Intersect(double[] a1, double[] a2, double[] t) { if (a1.Length == 0 || a2.Length == 0) return 0; int i1 = 0, i2 = 0, i = 0; for (;;) if (a1[i1] < a2[i2]) { if (++i1 == a1.Length) break; } else if (a2[i2] < a1[i1]) { if (++i2 == a2.Length) break; } else { t[i++] = a1[i1]; if (++i1 == a1.Length || ++i2 == a2.Length) break: } return i; }
Dê uma olhada na implementação básica deste algoritmo. Se os dois conjuntos de entradas estiverem vazios, então, obviamente, retornamos 0. Em seguida, iniciamos um loop infinito, no qual, se houver uma correspondência, aumentamos o resultado em 1 e verificamos se o ciclo deve ser concluído. Em vez de um loop infinito, pode-se usar a instrução for e especificar a condição para encerrar o loop nela. Mas isso significaria trabalho extra. Na implementação que você vê no slide, no primeiro ramo, temos `if (a1 [i1] <a2 [i2]), após o qual há um aumento de` i1 em 1 e só podemos verificar `i1. Da mesma forma, no segundo ramo, precisamos apenas checar `i2. Ambos os valores precisam ser verificados apenas na terceira ramificação. Se essa verificação estivesse no início do ciclo, faríamos o trabalho extra.
Vamos tentar melhorar essa implementação. No momento, sua complexidade algorítmica é linear, dependendo de dois argumentos de entrada. No aprendizado de máquina, muitas vezes é preciso encontrar a interseção de conjuntos que são muito diferentes um do outro em tamanho ou em estatística. Por exemplo, você tem um vetor de entrada longo e um vetor de recurso curto que você está verificando. Em nosso código, pode haver um milhão de registros em `a1 e mil em` a2. Nesse caso, não estamos prontos para executar um milhão de etapas para concluir esse algoritmo. A maior carga aqui será na seguinte linha de código: `if (++ i1 == a1.length) break. Pouco antes disso, ocorre uma comparação e, nessa linha, há um incremento do valor; isso, em essência, é uma pesquisa linear. Repetimos um vetor longo em busca de elementos de um vetor curto. Na pior das hipóteses, realizaremos muitas dessas pesquisas, movendo-se lentamente ao longo do vetor.
Vamos tentar melhorar esse algoritmo. Bem, se não for pesquisa linear, então binário é melhor, certo? Vamos usar binário. Sua vantagem é que ele fornece o índice do maior dos elementos menores.
int Intersect(double[] a1, double[] a2, double[] t) { int i1 = 0, i = 0; for (; i1 != a1.Length; ++i1) { auto m = Bsearch(a2, a1[i1]); if (m == a2.Length) continue; --m; if (!(a2[m] < a1[i1])) t[i++] = a1[i1]; } return i; }
O código acima é uma implementação do nosso algoritmo de busca binária. Mas não é muito eficaz. A pior situação aqui será quando a pesquisa binária falhará sempre. E surgirá em cenários bastante importantes - por exemplo, quando os dois conjuntos são idênticos. Você, como um tolo, corta círculos com busca binária, enquanto apenas precisa passar pelo primeiro algoritmo linear. Por que pesquisa binária, quando o item desejado - toda vez aqui, o primeiro da lista?
Como fazer o algoritmo funcionar com sucesso em dados idênticos e diferentes? A verificação de todos os dados será muito cara para recursos. Farei uma reserva de que não se trata de dados completamente idênticos, mas de muito semelhantes, com estatísticas semelhantes, os tamanhos também podem variar. Você pode verificar os seguintes itens. A solução óbvia é reduzir sua pesquisa. Quando realizamos uma pesquisa binária, depois de encontrar algum elemento, não estamos mais interessados em elementos menores que ele, pois o segundo vetor também é classificado. Assim, podemos reduzir sempre nossa área de pesquisa, descartando todos os elementos menos do elemento encontrado.
int Intersect(double[] a1, double[] a2, double[] t) { int i1 = 0, i2 = 0, i = 0; for (; i1 != a1.Length; ++i1) { auto m = Bsearch(a2, i2, a2.Length, a1[i1]); if (m == i2) continue; if (!(a2[m - 1] < a1[i1])) t[i++] = a1[i1]; i2 = m + 1; } return i; }
Aqui está a implementação dessa abordagem. Você vê que realizamos uma pesquisa binária a cada vez para uma parte da matriz original começando com `i2 e terminando com` a2.length. Como o `i2 aumentará a cada pesquisa, a área de pesquisa será reduzida.
A próxima otimização que eu gostaria de implementar aqui está relacionada ao algoritmo Galloping Search. Em essência, esta é uma pesquisa binária com uma etapa diferente. No caso da pesquisa binária, começamos sempre do meio - mas vamos pensar que, quando procuramos um nome na lista telefônica, não o abrimos no meio? Se o sobrenome de uma pessoa começar, digamos, em "B", abriremos o livro mais perto do início. Esse princípio é implementado em uma pesquisa galopante: começamos a rastrear os dados na direção ascendente com um passo exponencialmente aumentado após cada verificação: primeiro 1, depois 2 e depois 4. Isso nos dá uma boa complexidade algorítmica. Se o passo crescesse linearmente, a complexidade seria quadrática. Quando pulamos o elemento que procuramos, realizamos uma pesquisa binária normal no segmento restante, que será pequeno e não afetará significativamente o tempo de execução do algoritmo. Assim, combinamos todas as vantagens de ambas as abordagens. Implementação de um algoritmo desse tipo:
int GBsearch(double[] a, int i, int j, double v) { for (int step = 1;; step *= 2) { if (i >= j) break; if (a[i] > v) break; if (i + step >= j) return Bsearch(a, i + 1, J, v); if (a[i + step] > v) return Bsearch(a, i + 1, i + step, v); i += step + 1; } return i; }
Agora, discutimos o dimensionamento, ou seja, tentamos encontrar a interseção de mais de dois conjuntos. Para cada pesquisa de várias palavras, precisaremos encontrar a interseção de vários conjuntos. Para fazer isso, podemos, por exemplo, comparar os dois primeiros conjuntos, depois sua interseção com o terceiro e assim por diante. Mas essa não é uma solução ideal. Precisamos pegar os primeiros elementos de todos os conjuntos e encontrar o menor deles, que precisará ser movido. Precisamos de uma estrutura de dados que permita encontrar o menor dos muitos elementos e tenha complexidade constante. Essa estrutura de dados é um monte. Mas será um grupo estranho, não será baseado em uma matriz física. Será imaginário, organizaremos nele apenas os primeiros elementos de nossos conjuntos. Depois de encontrarmos o menor elemento na pilha, ainda podemos procurar todos os outros conjuntos.
O trabalho sobre os tópicos que estamos discutindo na prática hoje tem uma forma artesanal. Na prática, na maioria das vezes teremos vários conjuntos, não apenas dois, e muito trabalho foi escrito sobre esse tópico. O algoritmo clássico aqui é o SVS, no qual agrupamos os conjuntos, pegamos os dois menores e escolhemos o menor como candidato.
Aqui você pode encontrar uma boa visão geral sobre esse tópico. Os problemas associados aos conjuntos de interseção, o produto escalar de vetores esparsos, a classificação por mesclagem e as formas de comparação com a imagem ao longo do tempo estão se tornando cada vez mais interessantes. O algoritmo que mostrei para você se estabeleceu como muito útil. Obrigado pela atenção.
Andrei Alexandrescu não chegará ao DotNext 2018 em Moscou, mas Jeffrey Richter, Greg Young, Pavel Yosifovich e outros estarão lá. Os nomes dos palestrantes e os tópicos dos relatórios podem ser encontrados aqui e os ingressos aqui . Inscreva-se agora!