Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I have a question about implementing a data structure (with algorithm) that has these features:

  1. There are too many places (like stores), and each place can store too many items, I want to store items in the places. The point is we need to have optimized insertion (or deletion) and optimized search feature.

  2. Search can be done based on places (return items in the place) or base on items (return places that have the item)

I thought to use a hashmap for this, and use places ID as the key and store items as a collection (again a hashmap with item id for both key and value).

So based on this, the insertion of each item or place would be O(1) but get or remove of place will be O(n) and for item it will be O(n*k)! (assume we have "n" places and "k" items - I hope this is the correct calculation).

Is there any better data structure or algorithm for this problem?

share|improve this question

migrated from stackoverflow.com Sep 13 '11 at 12:18

This question came from our site for professional and enthusiast programmers.

2  
Why not use a real DB for that? I think VistaDB, SQLite etc. would be perfect for the job? –  Lucero Oct 17 '10 at 20:47
    
Maybe because insertion into a DB (together with maintaining the proper indices for search) is quite slow? –  Vlad Oct 17 '10 at 20:51
    
Or maybe because a database is not an algorithm. Using a database is delegating the question of choosing the right algorithm to the database developers and database administrator (which need to make the database generic enough, so its algorithms won't necessarily be optimal for your specific case). –  Vlad Oct 17 '10 at 20:59
    
Well, even if your question does not address it I suspect that you will have some requirements regarding persistence as well. If you work on disk you may choose other algorithms and data structures than if you work in RAM, and it also depends a lot on the amount of data that you want to manage. If you think my answer was inappropriate I'm happy to delete it, but from your problem description I still believe that using a finished DB application may be the answer. –  Lucero Oct 17 '10 at 21:11
    
I think any answer can give some clue to the OP about solution to his problem. Sometimes people ask not what they exactly need to know, so any related information is useful. –  Vlad Oct 17 '10 at 21:18
show 5 more comments

1 Answer

Why not use balanced trees? You would need one tree at each store, mapping item ID to some internal information, and one global tree, mapping item ID to the list of the nodes having the given item. Your operations will be O(log n + log k).

Edit:
the operations in this case would look like the following: (I use the fact that std::map and std::set are tree-based 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];
    }
}
share|improve this answer
    
Thanks for your answer, I'll try to implement that.BTW, can you provide an example (in java or C#) a link or something? –  sander Oct 18 '10 at 3:16
    
Oh, I should add something, for this problem Items only have item id nothing more, I mean no other information as internal info. –  sander Oct 18 '10 at 3:31
    
@sander: I've added a C++-based sample. –  Vlad Oct 18 '10 at 19:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.