Calcular eficientemente elementos mínimos en conjuntos parcialmente ordenados

Question

Tengo una lista de conjuntos que me gustaría ordenar en un orden parcial según la relación del subconjunto.

De hecho, no necesito el pedido completo, sólo los elementos mínimos.

Si no me equivoco, cada elemento mínimo debe definir un componente separado del gráfico respectivo, y este componente debe ser una semirrejilla de encuentro.

¿Cuál sería la forma más conveniente y eficiente en cuanto a espacio y tiempo para resolver este problema?¿Quizás haya una manera que no requiera construir el gráfico completo?¿Quizás exista un algoritmo conocido con una terminología mejor que la que he descrito ingenuamente anteriormente?

Soy consciente de que los requisitos de tiempo y espacio no se especifican lo suficiente anteriormente, pero estaría encantado de recibir cualquier sugerencia, ya sea que se haya demostrado que es óptima o no...

Fondo:Actualmente estoy construyendo una base de datos de gráficos completa que contiene todos los bordes entre los conjuntos y luego busco los nodos que no tienen generalizaciones, pero esto es bastante complicado, lento y requiere mucho espacio (en disco).La lista mencionada anteriormente contiene aproximadamente 100 millones de juegos.

Answer 1

Un enfoque es ordenar los conjuntos al aumentar el tamaño, luego realice repetidamente lo siguiente: Tome el primer set en la lista, lo salí y retire de la lista todos los supersets de él. Esto emitirá todos los conjuntos mínimos. El tiempo de ejecución es $ o (nk) $ establecer comparaciones más $ o (n \ log n) $ Pasos para clasificar, donde $ n $ es el número de conjuntos que tiene y $ k $ es el número de elementos mínimos. O, para decirlo de otra manera, si cada conjunto contiene $ m $ elementos, el tiempo de ejecución será aproximadamente $ O ( n (k + \ log n) m) $ pasos básicos.

¿Por qué ordenar por tamaño? Esta es una optimización. Se garantiza que el set más pequeño es mínimo (no hay ninguna cardinalidad más pequeña en la lista, por lo que ninguno de sus subconjuntos puede estar en la lista), por lo que el tamaño es un truco útil para identificar un conjunto que seguramente debe ser mínimo.

Sin clasificación por tamaño, es probable que el tiempo de funcionamiento en el peor de los casos termine como $ o (n ^ 2) $ establece comparaciones (o $ o (n ^ 2 m) $ pasos básicos), lo que es peor cuando $ k \ ll n $ .

---

Aquí hay una versión optimizada de ese algoritmo. Deje que $ m $ sea una estructura de datos que almacena un conjunto de conjuntos, como un trie: por ejemplo, el conjunto $ \ {1.3,67 \} $ corresponde a la palabra $ 1367 $ y se almacena en el Trie en consecuencia. Inicialmente, $ M $ está vacío. Repita lo siguiente: Tome el siguiente conjunto $ s $ de la lista; Compruebe si cualquier conjunto en $ m $ es un subconjunto de $ s $ ; Si no, inserte $ s $ en $ m $ ; Finalmente, elimine $ s $ de la lista (o avance su puntero al siguiente elemento en la lista). La operación "Comprobar ..." se puede realizar de manera bastante eficiente utilizando un recorrido recursivo del Trie. Al final, una vez que haya pasado por toda la lista, salida $ m $ .

El tiempo de ejecución en el peor de los casos del algoritmo optimizado sigue siendo el mismo. En la práctica, el tiempo de funcionamiento podría mejorarse significativamente, tal vez a tan rápido como $ o (nm) $ pasos básicos en algunos casos si tiene suerte (pero no cuente en eso). Puede probar ambos y ver qué funciona mejor en la práctica en el tipo de cargas de trabajo que está tratando.

Answer 2

He encontrado una solución en este artículo, p.12.

El algoritmo mencionado allí como prueba debería traducirse al siguiente código Python:

T = set([]);
for x in X:
    rem = set([]);
    spe = False;
    for a in T:
        rel = oracle(x,a);
        if rel == "x>a":
            spe = True;
            break;
        elif rel == "x<a":
            rem.add(a);
    if not spe:
        T -= rem;
        T.add(x);

espero el break ser crucial para el tiempo de ejecución real, por lo que podría ser una buena idea ordenar X con anticipación para tener descansos tempranos, pero no estoy seguro de eso.

Otro punto que veo aquí es que > se supone que es irreflexivo, por lo que x>x no se sostiene.Pero para este código sería mejor si así fuera.Si a==x, se rompe en lugar de mirar más allá innecesariamente.

ACTUALIZAR: Ahora he podido probar diferentes implementaciones en Python.Permítanme brindarles directamente el código de Python. Creo que es suficientemente similar al pseudocódigo y quizás más concreto para muchas personas.

Aquí está la implementación tomada del documento:

def oracle(rep1,rep2):
    if generalizes(rep2,rep1):
        return ">";
    elif generalizes(rep1,rep2):
        return "<";
    return None;

def find_min_els_(repIDs,ID2rep):
    min_els = set([]);
    for x in repIDs:
        spec_of_x = set([]);
        x_is_spec = False;
        for min_el in min_els:
            relation = oracle(ID2rep[x],ID2rep[min_el]);
            if relation == ">":
                x_is_spec = True;
                break;
            elif relation == "<":
                spec_of_x.add(min_el);
        if not x_is_spec:
            min_els -= spec_of_x;
            min_els.add(x);
    return min_els;

Ahora bien, esto resultó ser demasiado lento y ya podemos decir por la complejidad que es muy malo si el ancho del orden parcial, es decir, el número m Se espera que el número de elementos mínimos sea grande.

El truco consiste en hacer que este algoritmo sea independiente de m evitando pasar por todos los elementos mínimos actuales.En su lugar, podemos aprovechar el hecho de que la búsqueda en el conjunto de resultados es rápida (supongo que aquí es donde entra en juego el trie).

Para cada x, generamos todas las generalizaciones.Ahora la complejidad depende del número de x y su tamaño, pero no tanto del número de elementos mínimos (sólo O(n iniciar sesión n)?).Aún mejor, como ahora tenemos que eliminar elementos no mínimos de la lista inicial de elementos en lugar de agregarlos, el tiempo utilizado para cada x disminuye en lugar de aumentar durante el tiempo de ejecución.

Aquí está el código respectivo:

def generalizations(spe_rep,gens):
    for el in spe_rep:
        gen_rep = spe_rep - set([el]);
        gen_str = string(gen_rep);
        if not gen_str in gens:
            gens.add(gen_str);
            yield gen_str;
            for x in generalizations(gen_rep,gens):
                yield x;

def find_min_els(repIDs,ID2rep):
    min_els = set(repIDs);
    for x in repIDs:
        for genID in generalizations(ID2rep[x],set([])):
            if genID in min_els:
                min_els.remove(x);
                break;
    return min_els;

Esto utiliza una función generadora. generalizations() para evitar computar más generalizaciones de x una vez que ya se ha encontrado uno en los elementos mínimos actuales.Esto ya es bastante rápido con mis datos, pero tal vez podría mejorarse generando primero generalizaciones que sean más generales (es necesario probar si esto lo hace más rápido) y, en particular, generando solo generalizaciones que constan de elementos que ya se han observado. en los elementos mínimos actuales.Por ejemplo si nuestro x es {a,b,c}, pero ningún elemento mínimo actual tiene c en él, no tenemos que generar ningún subconjunto de x eso contiene c, es decir.solo {a,b},{a},{b},{}.