unión / intersección de 2 conjuntos, donde cada conjunto está definido por sus subconjuntos

Question

Sabemos la definición de cada conjunto de la unión de otros conjuntos.

Por ejemplo

A = B union {1,2}

B = C union D

C = {5,6}

D = {5,7}

E = {4}

entonces A = {1,2,5,6,7}

Una unión E = {1,2,4,5,6,7}

Son los algoritmos eficientes para hacer eso. Supongamos que la jerarquía de uniones puede ser realmente profunda y que los subconjuntos pueden cambiar con bastante frecuencia (no tanto). Creo que debería haber formas de reducir al mínimo la cantidad de sindicatos que uno tiene que hacer.

Answer 1

¿Así que tienes una jerarquía inmutable de uniones de conjuntos cambiantes? ¿Y, como en su ejemplo, solo le interesa el valor de un conjunto?

Luego aplana la jerarquía. Es decir, en su ejemplo, una vez recorrería la jerarquía para encontrar el conjunto de conjuntos de cambios de los que su conjunto es la unión y almacenar este conjunto.

Para prescindir de las recálputas de unión siempre que cambie un conjunto de hojas, puede hacer un seguimiento de cada elemento de la cantidad de conjuntos que contiene actualmente. Esto se puede actualizar rápidamente si un conjunto de hojas cambia, y aquellos que no son necesarios para mirar cualquier conjunto de hojas sin cambios. Luego, aquellos elementos con conteo de frecuencia > 0 están actualmente en el sindicato.

Answer 2

Tal vez esté buscando algún tipo de conjunto de datos disociados ?

Answer 3

Varias preguntas sobre este caso.

Primera pregunta: ¿Cuánto tiempo dura esta " secuencia de comandos " / " programa " ¿tengo que correr? En caso de que no sea demasiado largo, podría ser una buena opción simplemente almacenar uniones anteriores y verificar el caché antes de realizar una acción sindical. La memoria no es tan cara hoy en día :).

Segunda pregunta que debe hacer: ¿hay elementos en un cierto orden antes de la unión? Si no lo están, y se accede a una lista más de una vez, puede ser muy útil ordenar primero una lista (de lo que puede tomar una decisión cuando solo está a mitad de camino de una lista, por ejemplo). Mergesort es una poderosa técnica de la combinación eficiente de dos listas ordenadas.