Elementi minimi di calcolo in modo efficiente rispetto ai set parzialmente ordinati

Question

Ho un elenco di set che vorrei ordinare un ordine parziale in base alla relazione del sottoinsieme.

In effetti, non ho bisogno dell'ordine completo, solo gli elementi minimi.

Se non sono sbagliato, ogni elemento minimo dovrebbe definire un componente separato del rispettivo grafico - e questo componente dovrebbe essere un semilattice di incontro.

Quale sarebbe lo spazio più conveniente e il modo efficace per risolvere questo problema? Forse c'è un modo che non richiede di costruire l'intero grafico? Forse c'è un algoritmo noto sotto una terminologia migliore di quello che ho descritto ingenuamente sopra?

Sono consapevole che i requisiti del tempo e dello spazio sono sottoprizzati sopra, ma sarei felice di qualsiasi suggerimento, se sono dimostrati di essere ottimale o meno ...

Background : Attualmente sto costruendo un intero database grafico che contiene tutti i bordi tra i set e quindi cerca i nodi che non hanno generalizzazioni, ma questo è molto complicato, lento e richiede molto di spazio (disco). L'elenco sopra menzionato contiene circa 100 milioni di set .

Answer 1

Un approccio è quello di ordinare i set aumentando le dimensioni, quindi eseguire ripetutamente quanto segue: PRENDERE IL PRINCIPO IL PRIMO SET IN ELENCO, ESPOSTARLO e RIMUOVERE DALL'ELLY ELENCO TUTTI I SUPERSETTI. Questo produrrà tutti i set minimi. Il tempo di esecuzione è $ o (nk) $ set confronto plus $ o (n \ log n) $ Passi per l'ordinamento, dove $ N $ è il numero di set che hai e $ k $ è il numero di elementi minimi. Oppure, per metterlo in un altro modo, se ogni set contiene $ m $ elementi, il tempo di esecuzione sarà di circa $ o ( n (k + \ log n) m) $ Passi di base.

Perché ordinare per dimensione? Questa è un'ottimizzazione. Il set più piccolo è garantito per essere minimo (non vi è alcuna cardinalità più piccola nell'elenco, quindi nessuno dei suoi sottoinsiemi può essere nell'elenco), quindi la dimensione è un trucco utile per identificare un set che deve essere sicuramente minimo. Senza ordinare per dimensione, il tempo di esecuzione del caso peggiore è probabile che si concluda come $ o (n ^ 2) $ set di confronti (o $ o (n ^ 2 m) $ gradini di base), che è peggiore quando $ k \ ll n $ . .

---

.

Ecco una versione ottimizzata di quell'algoritmo. Let $ M $ BE Una Struttura dei dati che memorizza una serie di set, come trie: ad esempio, il set $ \ {1,3,67 \} $ corrisponde alla parola $ 1367 $ ed è memorizzato nel trie di conseguenza. Inizialmente, $ m $ è vuoto. Ripeti quanto segue: Prendi il set successivo $ s $ dall'elenco; Controllare se qualsiasi set in $ m $ è un sottoinsieme di $ s $ ; In caso contrario, inserire $ s $ in $ m $ ; Finalmente Elimina $ s $ dall'elenco (o fai avanzare il puntatore all'elemento successivo nell'elenco). L'operazione "Check ..." può essere eseguita abbastanza in modo efficiente utilizzando una traversata ricorsiva del trie. Alla fine, una volta che hai attraversato l'intera lista, output $ m $ .

Il tempo di esecuzione del caso peggiore dell'algoritmo ottimizzato rimane lo stesso. In pratica il tempo di esecuzione potrebbe essere migliorato in modo significativo, forse fino a $ o (nm) $ passi di base in alcuni casi se sei fortunato (ma non contare su di essa). Puoi provare entrambi e vedere che funziona meglio in pratica sul tipo di carichi di lavoro con cui hai a che fare.

Answer 2

Ho trovato una soluzione in Questo documento, p.12 .

L'algoritmo citato lì come prova dovrebbe tradurre il seguente codice 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);

.

Mi aspetto che il break sia cruciale per il runtime effettivo, quindi potrebbe essere una buona idea ordinare X in anticipo per ottenere pause precoce - ma non ne sono sicuro.

Un altro punto che vedo qui è che > dovrebbe essere irrefrezione, quindi x>x non tiene. Ma per questo codice sarebbe meglio se lo fece. Se a==x, si rompe invece di guardare inutilmente oltre.

Aggiornamento: Ora sono stato in grado di testare diverse implementazioni in Python. Si prega di permettermi di dare direttamente al codice Python, penso che sia sufficientemente simile alla pseudocodice - e forse più concreto per molte persone.

Ecco l'implementazione come prelevato dalla carta:

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;

.

Ora questo si è rivelato troppo lento e possiamo già dire dalla complessità che è pessimo se la larghezza dell'ordine parziale, che è il numero m degli elementi minimi dovrebbe essere grande.

Il trucco è quello di rendere questo algoritmo indipendentemente dal m evitando di passare attraverso tutti gli elementi minimi correnti. Invece, possiamo usufruire del fatto che la ricerca nel set di risultati è veloce (immagino che sia qui che il trie entra in gioco).

Per ogni X, generezziamo tutte le generalizzazioni. Ora la complessità dipende dal numero di X e dalla loro dimensione, ma non molto sul numero di elementi minimi ( solo o (n log n)? ). Ancora meglio, come ora dobbiamo rimuovere elementi non minimi dall'elenco iniziale di elementi invece di aggiungerli, il tempo utilizzato per ciascuna X sta diminuendo invece di aumentare il runtime.

Ecco il rispettivo codice:

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;

.

Questo utilizza una funzione generatore generalizations() per evitare di calcolare più generalizzazioni di x una volta che uno è già stato trovato negli attuali elementi minimi. Questo è già abbastanza veloce con i miei dati, ma potrebbe forse essere migliorato generando le generalizzazioni prima che sono più generali (è necessario testato se questo lo rende più veloce) e in particolare generando solo generalizzazioni che consistono in elementi che sono già stati osservati negli attuali elementi minimi. Ad esempio se il nostro x è {a,b,c}, ma nessun elemento minimo corrente ha c in esso, non dobbiamo generare alcun sottoinsieme di x che contiene c, I.e. Solo {a,b},{a},{b},{}.