curiosa pregunta: ¿Qué algoritmo no STL set_intersect implementar?

Question

Me pasó una cantidad considerable de tiempo de codificación en Baeza-Yates fraguado rápido algoritmo de intersección de una de mis aplicaciones. Mientras me marginalmente superar a la set_intersect STL, el hecho de que yo requería el conjunto resultante para ser ordenados sacar en cualquier momento he obtenido de la aplicación de mi propio algoritmo después de ordenada la salida. Dado que el set_intersect STL realiza esta bien, me puede señalar a nadie con el algoritmo que pone efectivamente en marcha? ¿O se aplique el mismo algoritmo de Baeza-Yates, pero sólo de una manera mucho más eficiente?

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

Answer 1

Por lo menos en las implementaciones que he mirado, la aplicación es bastante simple - algo en este orden general:

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

Por supuesto, sólo estoy escribiendo esto de la parte superior de mi cabeza - es probable que ni siquiera compilar, y ciertamente no es pedante correcta (por ejemplo, probablemente debería utilizar una función de comparación en lugar de utilizar directamente operator<, y debe tener otro parámetro de plantilla para permitir start1 / END1 ser un tipo diferente de start2 / end2).

Desde un punto de vista algorítmico, sin embargo, supongo que más real implementaciones son más o menos que el anterior.

Answer 2

STL no requiere ningún algoritmo concreto, sólo establece limitaciones de la complejidad algorítmica de ciertas operaciones. Ya que todo plantilla basada, puede ver fácilmente la fuente de su aplicación en particular para ver cómo funciona.

Answer 3

Interesante. Por lo tanto, el número de comparaciones en el algoritmo de escala de forma lineal con el número de elementos de ambos conjuntos. El algoritmo de Baeza-Yates es algo como esto (nota que asume tanto la entrada como conjuntos se clasifican):

1) Encontrar la mediana del conjunto A (A es el conjunto más pequeño aquí) 2) Búsqueda de la mediana de A en B.     Si lo encuentra, debe añadirse al resultado     demás, se conoce el rango de inserción de la mediana en B. 3) Dividir establece A sobre su mediana en dos partes, y conjunto B sobre su rango de inserción en dos partes, y repetir el procedimiento de forma recursiva en ambas partes. Este paso funciona porque todos los elementos, menos de la mediana en A se cruzarían sólo con aquellos elementos antes de la fila de inserción de la mediana de A en B.

Ya que se puede utilizar una búsqueda binaria para encontrar la mediana de A en B, con claridad, el número de comparaciones en el este algoritmo es inferior a la que usted ha mencionado. De hecho, en el "mejor" caso, el número de comparaciones es O (log (m) * log (n)), donde m y n son los tamaños de los conjuntos, y en el peor de los casos, el número de comparaciones es O (m + n). ¿Cómo diablos lo hizo me lío la puesta en práctica de este mal? : (