Hash Table con gli iteratori come chiavi, è questo design scarso e posso farlo meglio?

3

Sto sviluppando un programma in cui due volte ho trovato la soluzione a un problema era usare le tabelle hash con iteratori come chiavi e qualche altro tipo arbitrario come valore.

Mi sono ritrovato a utilizzare questo modello inizialmente per gestire due strutture di dati che si influenzano a vicenda, ma che non sono accoppiate a sé stanti. In questo primo istante avevo una GUI creata in QT in cui desideravo che l'interazione dell'utente influisse su una struttura dati sottostante. In questo caso c'era una lista collegata all'interno di un altro oggetto che doveva essere modificato quando l'utente rimuoveva o aggiungeva elementi a una rappresentazione della GUI di quell'oggetto (che era una lista).

Non ho molta esperienza nella programmazione della GUI, quindi la mia soluzione era quella di inviare segnali all'oggetto incapsulante sull'utente cancellando l'elemento corrispondente nella GUI con informazioni su quale elemento della GUI era stato cancellato. internamente l'oggetto incapsulante prende queste informazioni dal segnale (l'informazione è un iteratore) e le associa ad un altro iteratore che viene poi rimosso dalla lista collegata (o in modo simile è inserito un nuovo elemento). Per evitare l'accoppiamento tra la GUI e l'elaborazione del mio programma, ho creato una nuova classe che era un oggetto di configurazione che genera l'effettiva classe principale utilizzata nell'elaborazione dopo che sono state eseguite determinate azioni.

Sembrava una soluzione piuttosto disgustosa al problema, ma non riuscivo a capire come migliorarlo, l'azione di Gui sembra avere bisogno di una correlazione diretta con l'azione non gui.

Recentemente mi sono ritrovato a usare di nuovo uno schema simile, stavolta stavo cercando di implementare quanto segue:

Ho due elenchi di elementi (vecchi e nuovi) ai quali posso applicare una metrica di distanza. Voglio associare elementi da una lista con elementi nel secondo. Non voglio utilizzare l'algoritmo ungherese a causa della complessità del codice e del runtime dell'algoritmo.

Stavo pianificando di implementare l'associazione trovando l'elemento con la minima distanza dal nuovo elemento, confrontandolo con il precedente valore più piccolo associato a quell'elemento, quindi sostituendo il valore associato fino a quando ogni elemento è stato ripetuto con iterazione in nuovo.

Il problema è che, se non voglio semplicemente taggare un nuovo valore non necessario a questi elementi (cioè last_smallest_distance e current_closest_associated_item ) che non hanno alcun valore dopo il passo di associazione. Dovrò trovare un modo per aggiungere persistenza tra le iterazioni utilizzate per trovare l'associazione. La soluzione più ovvia per me è ancora una volta creare una tabella hash iteratore in cui ogni iteratore è associato a una distanza minima separata e alla coppia di valore associata più vicina corrente.

Ecco un esempio di ciò di cui sto parlando:

struct ItemDistancePair{
    Item & item;
    double distance;
}

void updateOldItems(std::list<Item>& old_items, const std::list<Item>& new_items){
    std::unordered_map<std::list<Item>::iterator, ItemDistancePair) old_new_value_map;
    for(auto& new_item: new_items){
        std::list<Item>::iterator closest_old_itr = findClosestAssociation(new_item, old_items)
        double distance = new_item.distanceFrom(*closest_old_itr);
        auto map_location_itr = old_new_value_map.find(closest_old_itr);
        if(map_location_itr == old_new_value_map.end()){
            old_new_value_map.insert(std::make_pair(closest_old_itr, ItemDistancePair(new_item, distance)));

        }
        else if(map_location_itr->second.distance > distance){ 
            map_location_itr->second = ItemDistancePair(new_item, distance);
        }
    }
    for(auto& key_value_pair : old_new_value_map){
        key_value_pair.first->updateItem(key_value_pair->second.item);
    }
}

Si noti che nel caso in cui più elementi nuovi siano più vicini a un vecchio articolo, è possibile che un altro vecchio oggetto non venga mai aggiornato, questo va bene

Come puoi vedere, questo non è l'ideale (anche se forse questo non sarebbe un problema in una lingua diversa dal C ++?) causa un sacco di codice strano (mi costringe a fare una struct se non lo faccio voglio usare std :: pair).

È accettabile o c'è un modo per aggirare questo, o è la vera soluzione migliore al problema solo per includere queste informazioni sulla distanza nella classe Item stessa, cosa stavo cercando di evitare in primo luogo?

    
posta opa 10.10.2017 - 23:11
fonte

1 risposta

5

Algoritmo

Quindi, AFAICT il tuo algoritmo si riduce a:

  1. Per ogni new_item , trova il old_item più vicino. (Questo crea un set di old_item s.)
  2. Per ogni old_item nel set, aggiornalo con il new_item più vicino.

Avviso bug

Immagina una linea con 4 punti: A_new , 3 unità di distanza, B_old , 2 unità di distanza, C_new , 1 unità di distanza, D_old .

In questo caso, è necessaria una decisione:

  1. aggiorna B_old con A_new ( C_new ha una corrispondenza migliore D_old , quindi prendi la prossima corrispondenza migliore
  2. aggiorna B_old con C_new ( C_new è più vicino a B_old , quindi prendi la migliore corrispondenza)
  3. non aggiorna B_old ( A_new non valido perché C_new è più vicino a B_old , ma C_new non è valido anche perché D_old è più vicino a C_new di B_old )
  4. aggiorna B_old con C_new (aggiorna solo ogni vecchio articolo con il nuovo elemento più vicino, problema diverso, ma soluzione più semplice)

Il tuo esempio sceglierebbe l'opzione 1 in questo caso, ma non necessariamente in quelli più complessi. Questo potrebbe non essere inteso.

Il mio pseudocodice dell'algoritmo di cui sopra sceglierebbe l'opzione 2. Questo potrebbe anche non essere inteso.

Continuerò sotto l'ipotesi che l'opzione 3 è ciò che è realmente inteso. (Se questo è sbagliato, lasciami un commento!)

Algoritmo (riparato)

L'algoritmo è quindi:

  1. Per ogni new_item , trova il old_item più vicino. (Questo crea un set di old_item s.)
  2. Per ogni old_item nel set:
    1. trova il new_item più vicino.
    2. trova il old_item più vicino al% co_de trovato.
    3. se il valore trovato più vicino new_item è uguale all'attuale old_item , aggiornalo con il valore trovato old_item .

Attuazione

Come hai giustamente dedotto, una sorta di riferimento al new_item deve essere passato dal passaggio 1 al passaggio 2. Questo riferimento deve essere memorizzato e confrontato ("questi due elementi sono allo stesso indirizzo?" ).

I riferimenti Pure C ++ non funzionano bene per questo tipo di riferimento, in quanto non esiste un modo semplice per archiviarli e confrontarli. I puntatori soddisfano comunque entrambi i requisiti e sono più diretti degli iteratori (anche se tecnicamente parlando, gli iteratori possono funzionare allo stesso modo).

void updateOldItems(std::list<Item>& old_items, std::list<Item>& new_items) {
    std::unordered_set<Item*> old_items_to_update;

    // STEP 1
    for(auto& new_item : new_items) {
        auto old_item = &(*findClosestAssociation(new_item, old_items));
        old_items_to_update.insert(old_item); // takes care of duplicates
    }

    // STEP 2
    for(auto old_item : old_items_to_update) {
        auto new_item = findClosestAssociation(*old_item, new_items);
        auto closest_old_item = &(*findClosestAssociation(*new_item, old_items));

        if(closest_old_item == old_item) old_item->updateItem(*new_item);
    }
}

La conversione da old_item a std::list<Item>::iterator è un po 'macchinosa (iteratore di dereferenziazione per ottenere riferimenti, prendere l'indirizzo dal riferimento), ma questo è più un problema di Item* che restituisce un iteratore in primo luogo (invece di diciamo, un riferimento o un puntatore). Ovviamente, potresti semplicemente creare findClosestAssociation un insieme di iteratori, ma questo potrebbe causare altri problemi in futuro (ad esempio, lo scambio di old_items_to_update per std::list o std::forward_list richiede l'aggiornamento di tutti i tipi di iteratore).

    
risposta data 11.10.2017 - 05:46
fonte

Leggi altre domande sui tag