Оптимизация по поисковому вопросу

Question

Требование состоит в том, что ряд «клиентов» выбирают диапазон ресурсов, которыми они хотят управлять, и прослушивают события.Как правило, было бы около 10 клиентов и около 100 ресурсов.Вполне возможно, что количество клиентов и ресурсов может быть более 1000, однако.

В настоящее время это реализовано в виде карты, индексируемой clientid со значением в качестве объекта клиента.Объект client содержит список выбранных ресурсов. Проблема в том, что если для ресурса существует событие, скажем, ресурс A, то код должен циклически проходить через каждого клиента, а затем через каждый список в клиенте.Я обеспокоен производительностью.

Есть ли более эффективный алгоритм для устранения этого возможного узкого места?

Angus

Answer 1

ваша структура выглядит как {client:[resource]}, но для эффективной доставки событий вам нужно {resource:[client]}

Answer 2

Вы запускали профилировщик?Профилировщик зарегистрировал это как реальное узкое место?

10 клиент и 100 ресурсов - ничто для современного ПК.Простой std :: map может очень быстро получить этот поиск.Примерно так:

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

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

Это просто идея, и некоторые вещи отсутствуют, чтобы она работала (например, критерии сортировки для клиентов)

Answer 3

Вставьте стандартный отказ от ответственности: преждевременная оптимизация - это плохо, не усложняйте ситуацию, пока не узнаете, что у вас проблемы с производительностью

Как насчет просто иметь вторую обратную структуру данных, хэш-карту ресурсов, содержащую список заинтересованных клиентов? Немного больше работы, так как клинты и ресурсы меняются, но, вероятно, оно того стоит.

Answer 4

Кажется, вы хотите сделать обратный поиск, поэтому взгляните на boost.bimap , который поддерживает это.

Answer 5

Или вы можете иметь свой список ресурсов также в виде карты с ресурсом в качестве ключа и логическим значением в качестве значения.

Что-то вроде

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

вместо текущего

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

Поиск становится быстрее.