Pergunta curiosa: Qual algoritmo STL Set_intersect implementa?

Question

Passei uma quantidade considerável de tempo codificando no algoritmo de interseção rápido de Baeza-Yates para um dos meus aplicativos. Embora eu tenha superado marginalmente o STL Set_intersect, o fato de eu exigir que o conjunto resultante fosse resolvido sempre que obtiver ao implementar meu próprio algoritmo depois de classificar a saída. Dado que o STL Set_intersect executa isso bem, alguém pode me apontar para o algoritmo que ele realmente implementa? Ou implementa o mesmo algoritmo Baeza-Yates, mas apenas de uma maneira muito mais eficiente?

Baeza-Yates: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.91.7899&rep=rep1&type=pdf

Answer 1

Pelo menos nas implementações que observei, a implementação é bastante simplista - algo nesta ordem geral:

template <class inIt, class outIt>
outIt set_intersection(inIt start1, inIt end1, inIt start2, inIt end2, outIt out) {
    while (start1 != end1 && start2 != end2) {
       if (*start1 < *start2)
           ++start1;
       else if (*start2 < *start1)
           ++start2;
       else {                 // equal elements.
           *out++ = *start1;
           ++start1;
           ++start2;
       }
    }
    return out;
}

Claro, estou apenas digitando isso no topo da minha cabeça - provavelmente nem sequer compilará, e certamente não está pedanteicamente correto (por exemplo, provavelmente deve usar uma função de comparador em vez de usar operator< Diretamente e deve ter outro parâmetro de modelo para permitir que o START1/END1 seja um tipo diferente do start2/end2).

Do ponto de vista algorítmico, no entanto, eu acho que a maioria das implementações reais é praticamente acima.

Answer 2

O STL não requer nenhum algoritmo específico, apenas define restrições na complexidade algorítmica de certas operações. Como é tudo baseado em modelo, você pode visualizar facilmente a fonte de sua implementação específica para ver como ela funciona.

Answer 3

Interessante. Portanto, o número de comparações no seu algoritmo escala linearmente com o número de elementos nos dois conjuntos. O algoritmo Baeza-Yates vai algo assim (observe que ele assume que os dois conjuntos de entrada são classificados):

1) Encontre a mediana do conjunto A (a é o conjunto menor aqui) 2) Procure a mediana de A em B. Se encontrado, adicione ao resultado mais, a classificação de inserção da mediana em B é conhecida. 3) Split Define uma mediana em duas partes e defina B sobre sua classificação de inserção em duas partes e repita o procedimento recursivamente em ambas as partes. Esta etapa funciona porque todos os elementos menores do que a mediana em A se cruzariam apenas com esses elementos antes da classificação de inserção da mediana de A em B.

Como você pode usar uma pesquisa binária para localizar a mediana de A em B, claramente, o número de comparações no algoritmo é menor que o que você mencionou. De fato, no "melhor" caso, o número de comparações é O (log (m) * log (n)), onde m e n são os tamanhos dos conjuntos e, na pior das hipóteses, o número de comparações é O (M + N). Como diabos eu estraguei a implementação tão ruim? :(