Question curieuse: quel algorithme est implémenté par STL set_intersect?

Question

J'ai passé beaucoup de temps à coder dans l'algorithme d'intersection rapide de Baeza-Yates pour l'une de mes applications. Bien que je l'ai fait marginalement sur-performer la STL set_intersect, le fait que j'avais besoin que l'ensemble résultant soit trié est retiré à chaque fois que j'avais gagné de l'implémentation de mon propre algorithme après avoir trié la sortie. Etant donné que le fichier STL set_intersect fonctionne bien, quelqu'un peut-il me signaler l'algorithme qu'il implémente réellement? Ou met-il en œuvre le même algorithme de Baeza-Yates mais de manière beaucoup plus efficace?

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

Answer 1

Au moins dans les mises en œuvre, je l'ai regardé, la mise en œuvre est assez simpliste - quelque chose de cet ordre général:

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; 
} 

Bien sûr, je suis juste en tapant ce du haut de ma tête - il ne sera probablement pas compilé, et certainement pas corrélativement correct (par exemple, devrait probablement utiliser une fonction de comparaison au lieu d'utiliser operator< directement, et devrait avoir un autre paramètre de modèle pour permettre à start1/end1 d'être un type différent de start2/end2). D'un point de vue algorithmique, cependant, je suppose que la plupart des implémentations réelles sont à peu près comme ci-dessus.

Answer 2

STL ne nécessite aucun algorithme particulier, il définit simplement des contraintes sur la complexité algorithmique de certaines opérations. Comme tout est basé sur un modèle, vous pouvez facilement voir la source de votre implémentation particulière pour voir comment cela fonctionne.

Answer 3

Intéressant. Ainsi, le nombre de comparaisons dans votre algorithme s'échelonne linéairement avec le nombre d'éléments dans les deux ensembles. L'algorithme de Baeza-Yates va quelque chose comme ceci (notez qu'il suppose que les deux ensembles d'entrée sont triés):

1) Trouve la médiane de l'ensemble A (A est l'ensemble le plus petit ici) 2) Recherche la médiane de A dans B. Si trouvé, ajouter au résultat sinon, le rang d'insertion de la médiane dans B est connu. 3) Diviser l'ensemble A sur sa médiane en deux parties, et définir B sur son rang d'insertion en deux parties, et répéter la procédure récursivement sur les deux parties. Cette étape fonctionne parce que tous les éléments inférieurs à la médiane dans A ne croiseraient avec ces éléments avant le rang d'insertion de la médiane de A dans B.

Puisque vous pouvez utiliser une recherche binaire pour localiser la médiane de A dans B, clairement, le nombre de comparaisons dans cet algorithme est inférieur à celui que vous avez mentionné. En fait, dans le «meilleur» cas, le nombre de comparaisons est O (log (m) * log (n)), où m et n sont les tailles des ensembles, et dans le pire des cas, le nombre de comparaisons est O (m + n). Comment diable ai-je gâché la mise en œuvre ce mauvais? :(