Camaradas, boa noite! Você
separou tão friamente a primeira edição do livro "
C ++ 17 STL. Standard Template Library " e continua analisando a segunda, que finalmente decidimos apresentar aqui um ponto de vista alternativo. O autor do artigo de hoje é Ivan Čukić, proprietário do livro
Functional Programming in C ++ , que está sendo preparado para publicação na Manning Publishing House. Oferecemos a avaliação de seus pensamentos, códigos e cálculos céticos
PreâmbuloQueria nomear este post como "Sobre a crueldade dos algoritmos STL" para testar minhas próprias habilidades em provocar cliques. Mas então ele decidiu que era melhor escrever um artigo para o público-alvo, e não escrever um post em que aqueles que desejassem discutir sobre minhas teses egrégias se reunissem.
Assim, posso assumir que você está interessado em algoritmos, sua complexidade e deseja escrever o código mais perfeito.
AlgoritmosNa comunidade C ++ profissional moderna, as pessoas geralmente são aconselhadas: para tornar seu programa mais seguro, mais rápido, mais expressivo etc. - Use os algoritmos da biblioteca padrão. Também tento popularizar esse conselho em meus livros, discursos, seminários ... sempre que houver um público adequado.
Obviamente, é absolutamente verdade que, se somos atraídos a escrever um loop
for para resolver o problema diante de nós, primeiro precisamos pensar se os algoritmos existentes da biblioteca padrão (ou boost) são adequados para isso e não agem cegamente.
Ainda precisamos saber como esses algoritmos são implementados, quais requisitos e garantias estão associados a eles, qual é sua complexidade espacial e temporal.
Normalmente, se nos deparamos com uma tarefa que atende exatamente aos requisitos do algoritmo STL, e ela pode ser aplicada diretamente, esse algoritmo será a solução mais eficaz.
Um problema pode surgir se precisarmos preparar os dados de alguma forma antes de aplicar o algoritmo.
Interseção de conjuntosSuponha que estamos escrevendo uma ferramenta para desenvolvedores de C ++ que dê dicas sobre como substituir as opções de captura padrão (falando sobre
[=] e
[&] ) nas expressões lambda e exiba explicitamente uma lista de variáveis capturadas.
std::partition(begin(elements), end(elements), [=] (auto element) { ^~~ - - , [threshold] return element > threshold; });
Ao analisar um arquivo, precisamos de uma coleção que armazene variáveis dos escopos atuais e vizinhos. Assim que encontrarmos uma expressão lambda com uma captura padrão, precisaremos ver quais variáveis são usadas lá.
Como resultado, temos dois conjuntos: em um, haverá variáveis das áreas de visibilidade ao redor, e no outro, haverá variáveis usadas no corpo da expressão lambda.
A lista de opções de captura que ofereceremos para substituição deve ser a interseção desses dois conjuntos (expressões lambda podem usar variáveis globais que não precisam ser capturadas, e nem todas as variáveis do escopo circundante serão usadas na expressão lambda).
E, se precisarmos de interseção, podemos usar o
std::set_intersection .
Este algoritmo é bastante bonito em sua simplicidade. Ele aceita duas coleções classificadas e as executa simultaneamente do começo ao fim:
- Se o item atual na primeira coleção for igual ao item atual na segunda coleção, ele será adicionado ao resultado, que o algoritmo simplesmente move para o próximo item nas duas coleções;
- Se o item real na primeira coleção for menor que o item real na segunda coleção, o algoritmo simplesmente ignorará o item atual na primeira coleção;
- Se o item real na primeira coleção for maior que o item real na segunda coleção, o algoritmo simplesmente ignorará o item atual na segunda coleção;
Pelo menos um elemento (da primeira ou segunda coleção de entrada) é ignorado em cada iteração - portanto, a complexidade do algoritmo será linear -
O(m + n) , em que
m é o número de elementos na primeira coleção en é o número de elementos na segunda coleção .
Simples e eficaz. Contanto que as coleções de entrada sejam classificadas.
ClassificaçãoAqui está o problema: e se as coleções não forem pré-classificadas?
No exemplo anterior, seria aconselhável armazenar variáveis das áreas de visibilidade circundantes em uma estrutura semelhante a uma pilha, onde o analisador poderia simplesmente adicionar novos elementos entrando em um novo escopo e excluir as variáveis do escopo atual assim que saírem.
Assim, as variáveis não serão classificadas por nome e não poderemos usar diretamente
std::set_intersection para operações nelas. Da mesma forma, se você rastrear as variáveis no corpo de uma expressão lambda, provavelmente não conseguiremos salvá-las na forma classificada.
Como
std::set_intersection funciona apenas com coleções classificadas, em muitos projetos esse princípio ocorre: primeiro, classificamos as coleções e depois chamamos o
std::set_intersection .
Se esquecermos que a classificação de uma pilha de variáveis em nosso exemplo desvaloriza completamente todo o uso da pilha que definimos, o algoritmo de interseção para coleções não-classificadas terá algo parecido com isto:
template <typename InputIt1, typename InputIt2, typename OutputIt> auto unordered_intersection_1(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt dest) { std::sort(first1, last1); std::sort(first2, last2); return std::set_intersection(first1, last1, first2, last2, dest); }
Qual é a complexidade de todo esse algoritmo? A classificação leva um tempo quase-linear, portanto, a complexidade geral dessa abordagem é
O(n log n + m log m + n + m) .
Classificar menorÉ possível fazer sem classificar?
Se as duas coleções não forem classificadas, teremos que percorrer a segunda coleção para cada elemento da primeira - para decidir se a incluiremos no conjunto de resultados. Embora essa abordagem seja bastante comum em projetos reais, é ainda pior que a anterior - sua complexidade é
O(n * m) .
Em vez de classificar tudo em uma fileira ou não classificar nada, lembre-se do Zen e escolha o Terceiro Caminho - classificamos apenas uma coleção.
Se apenas uma coleção estiver classificada, podemos iterar todos os valores da não classificada um por um e, para cada valor, verificar se está na coleção classificada. Para fazer isso, aplique uma pesquisa binária.
Nesse caso, a complexidade do tempo será
O(n log n) para classificar a primeira coleção e
O (m log n) para classificar e verificar. A complexidade total será
O((n + m) log n) .
Se decidíssemos classificar a segunda coleção, e não a primeira, a complexidade seria
O((n + m) log m) .
Para alcançar a máxima eficiência, sempre classificamos a coleção na qual há menos elementos, para que a complexidade final do nosso algoritmo seja
((m + n) log (min(m, n)) .
A implementação terá a seguinte aparência:
template <typename InputIt1, typename InputIt2, typename OutputIt> auto unordered_intersection_2(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt dest) { const auto size1 = std::distance(first1, last1); const auto size2 = std::distance(first2, last2); if (size1 > size2) { unordered_intersection_2(first2, last2, first1, last1, dest); return; } std::sort(first1, last1); return std::copy_if(first2, last2, dest, [&] (auto&& value) { return std::binary_search(first1, last1, FWD(value)); }); }
Em nosso exemplo com listas de captura em expressões lambda, a coleção de variáveis presentes na expressão lambda geralmente é classificada, pois é provável que seja menor que a coleção de todas as variáveis de todos os escopos circundantes.
HashingA opção final é criar
std::unordered_set (uma implementação de conjunto não ordenado baseado em hash) a partir de uma coleção menor, em vez de classificá-la. Nesse caso, a complexidade das operações de pesquisa terá uma média de
O(1) , mas levará tempo para criar
std::unordered_set . A complexidade da construção pode variar de
O(n) a
O(n*n) , e esse é um problema em potencial.
template <typename InputIt1, typename InputIt2, typename OutputIt> void unordered_intersection_3(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt dest) { const auto size1 = std::distance(first1, last1); const auto size2 = std::distance(first2, last2); if (size1 > size2) { unordered_intersection_3(first2, last2, first1, last1, dest); return; } std::unordered_set<int> test_set(first1, last1); return std::copy_if(first2, last2, dest, [&] (auto&& value) { return test_set.count(FWD(value)); }); }
A abordagem de hash vence completamente quando você precisa calcular as interseções de vários conjuntos com um único conjunto pequeno predefinido. Ou seja, temos o conjunto
A , os conjuntos
B₁ ,
B₂… e queremos calcular
A ∩ B₁, A ∩ B₂…Nesse caso, você pode ignorar a complexidade da construção
std::unordered_set , e a complexidade do cálculo de cada interseção será linear -
O(m) , em que
m é o número de elementos na segunda coleção.
ControlarObviamente, é sempre útil verificar a complexidade do algoritmo, mas nesses casos também é aconselhável verificar várias abordagens usando pontos de verificação. Especialmente ao escolher as duas últimas opções, onde comparamos pesquisas binárias e conjuntos baseados em hash.
Meu teste mais simples mostrou que a primeira opção, onde você precisa classificar as duas coleções, é sempre a mais lenta.
Classificar uma coleção menor supera
std::unordered_set pouco o
std::unordered_set , mas não particularmente.
A segunda e a terceira abordagens são um pouco mais rápidas que a primeira, no caso em que ambas as coleções têm um número igual de elementos e muito mais rápidas (até seis vezes) quando o número de elementos em uma coleção é cerca de 1000 vezes mais que no segundo.