domanda, la migliore struttura dati e algoritmo

Question

domanda, la migliore struttura dati e algoritmo

#1 da (3 voti)

0

Ho una domanda sull'implementazione di una struttura dati (con algoritmo) con queste caratteristiche:

Ci sono troppi posti (come i negozi), e ogni posto può contenere troppi articoli, voglio conservare gli articoli nei luoghi. Il punto è che dobbiamo ottimizzare l'inserimento (o la cancellazione) e ottimizzare la funzione di ricerca.
La ricerca può essere effettuata in base ai luoghi (restituire gli elementi nel posto) o basare sugli elementi (restituire i posti che contengono l'elemento)

Ho pensato di utilizzare una hashmap per questo, e utilizzare l'ID di luoghi come chiave e memorizzare gli elementi come una raccolta (ancora una hashmap con l'ID oggetto per la chiave e il valore).

Quindi, in base a ciò, l'inserimento di ogni oggetto o luogo sarebbe O (1) ma ottenere o rimuovere di posto sarà O (n) e per oggetto sarà O (n * k)! (supponiamo di avere "n" posti e "k" elementi - spero che questo sia il calcolo corretto)

Esistono strutture o algoritmi dati migliori per questo problema?

data-structures algorithms

posta 17.10.2010 - 22:37

fonte

1 risposta

Leggi altre domande sui tag data-structures algorithms

Come salvare un modello di business da un database non corrispondente? Perché il runtime Android e le librerie native si trovano nello stesso livello?

score 3 · Answer 1

Perché non usare alberi equilibrati? Avresti bisogno di un albero in ogni negozio, mappando l'ID oggetto ad alcune informazioni interne e un albero globale, associando l'ID oggetto all'elenco dei nodi che hanno l'oggetto specificato. Le tue operazioni saranno O (log n + log k).

Modifica:
le operazioni in questo caso saranno come le seguenti: (Io uso il fatto che std::map e std::set sono basati su albero in C ++)

using namespace std;

typedef int itemid_t;
typedef int storeid_t;

map<itemid_t, set<storeid_t>> itemID2storeList;

class Store
{
    storeid_t Id;

    // insert requires one lookup in the map (O(log k))
    // plus one insert into a set (O(log n)).
    void insert(itemid_t item)
    {
        itemID2storeList[item].insert(Id);
    }

    // the same as for insert
    void delete(itemid_t item)
    {
        itemID2storeList[item].erase(Id);
    }

    // search in a store requires one lookup in a map (O(log k))
    // and one search in a set (O(log n)).
    bool have(itemid_t item)
    {
        const set<storeid_t>& storesForItem = itemID2storeList[item];
        return storesForItem.find(Id) != storesForItem.end();
    }
}

class Central
{
    // getting the list of stores having the given item requires
    // one lookup in a map (O(log k))
    const set<storeid_t>& storesForItem(itemid_t item)
    {
        return itemID2storeList[item];
    }
}