C++/Java: in modo efficiente trovare un set della collezione contenente dato valore

Supponiamo di avere una collezione di set si escludono a vicenda
{A, B, C, D} dove A = {1, 2,3}, B = {4,5,6}, C = {7,8,9}, D = {10,11,12}
E dato un valore Z , per esempio di 3, mi aspetto che restituisca l'indice del set A, perché A ha 3 come membro.C++/Java: in modo efficiente trovare un set della collezione contenente dato valore

La domanda è: come potrei farlo in modo efficiente usando C++ o JAVA.

mia soluzione attuale: negozio A, B, C, D come HashSet (o unordered_set in C++) nel contenitore e ciclo attraverso ogni set fino un insieme contenente Z è trovato.
Il problema è che la complessità è O (n) per la quantità di serie memorizzate nel contenitore.

C'è qualche modo (o qualsiasi struttura dati per memorizzare questi set) per farlo più veloce di O (n)?

fonte

2014-06-07 Truthseeker Rangwan

TBH se i tuoi set sono così semplici, basta usare un array di 'char', richiede meno memoria e un accesso molto veloce. – Olayinka

@Olayinka: è esattamente il contrario. Se i suoi set sono davvero così piccoli, probabilmente non ci saranno differenze significative tra O (n) e O (1), quindi perché introdurre tutti i pericoli e i problemi associati agli array, piuttosto che scegliere la soluzione robusta e semanticamente corretta? E per quanto riguarda il C++, perché array e non 'std :: vector' (o' std :: array' se la dimensione è nota in fase di compilazione)? –

@TruthseekerRangwan: quanto puoi modificare sulla struttura generale del tuo codice? Da dove viene il tuo input? Sei bloccato con la ricezione di una collezione di set? Puoi assumere qualsiasi altra cosa sul contenuto dell'insieme (ad esempio, il valore più piccolo in B è maggiore del più grande in A, o c'è una relazione di ordinamento tra i set)? Ho la sensazione che la tua domanda sia troppo incentrata sulla micro-ottimizzazione. –

È possibile creare una mappa che mappa un valore per impostare l'ID (ad esempio, deve eseguire il mapping da 1, 2, 3 a A, 4, 5 e da 6 a B e così via). Con una mappa hash, può funzionare in O (1) in media.

fonte

2014-06-07 07:47:04 kraskevich

@TruthseekerRangwan non si mappa il set come chiave, si rende ciascun elemento del set come chiave 1 -> A, 2 -> A, 12 -> D – Olayinka

Supponendo che il meccanismo di input dell'OP non possa essere modificato, questa soluzione solo sposta il problema in un altro posto. Trovare l'ID impostato alla fine sarà veloce, ma questo ha il costo di creare la mappa prima di quello. –

Come un'euristica rapida che può aiutare a provare a utilizzare la bolla più attiva utilizzata imposta nell'elenco. È probabile che la maggior parte delle volte ci siano uno o due set restituiti per l'80-90% delle richieste.

int getSetIndex(Object elem) { 
    Set first = sets.get(0); 
    if (first.contains(elem)) 
     // if "index of the set" has some special meaning in your question, 
     // you should save it along with the set 
     return first.index(); 
    for (int i = 1; i < sets.size(); i++) { 
     Set cur = sets.get(i); 
     if (cur.contains(elem)) { 
      sets.set(i, sets.get(i - 1)); 
      sets.set(i - 1, cur); 
      return cur.index(); 
     } 
    } 
    return -1; // not found 
}

fonte

2014-06-07 12:47:56 leventov

C++/Java: in modo efficiente trovare un set della collezione contenente dato valore

risposta

Problemi correlati