Optimisation on lookup question

The requirement is that a number of 'clients' select a range of resources which they wish to control and listen to events on. Typically there would be 10 or so clients and 100 or so resources. It is possible that the number of clients and resources could be 1000 plus however.

This is currently implemented as a map indexed by clientid with the value as the client object. The client object contains a list of resources selected The problem is that if there is an event for a resource, say resource A then the code has to cycle through each client and then through each list within a client. I am concerned about performance.

Is there a more effici开发者_StackOverflow中文版ent algorithm to handle this possible bottleneck?

Angus

---

your structure looks like {client:[resource]} but for efficient event delivery you need {resource:[client]}

---

It seems you want to do a reverse lookup, so take a look at the boost.bimap which supports this.

---

Insert standard disclaimer: premature optimisation is bad, don't complicate things before you know you have a performance problem

How about just having a second, inverse data structure, a hashMap of resources, containing a list of interested clients? Bit more work as clints and resources change, but probably worth it.

---

Did you run a profiler? Did the profiler register that as the real bottleneck?

10 client and 100 resources is nothing for a modern PC. Simple std::map could get that lookup very fast. Something like this :

struct Resource
{
  // data 2
};
struct Client
{
  // data 2
};

std::map< Client, std::vector< Resource > > mappingClientToResources;

This is just an idea, and is missing some things to have it working (like for example sorting criteria for Clients)

---

Or you can have your resource list also as a map , with resource as key and boolean value as value.

Something like

{ client1 : { resource1 : true, resource2: true, resource3:true },... }

instead of your current

{ client1 : [resource1,resource2,resource3],.... 

The lookup becomes faster.