優化查找問題

Question

需求是，一些'客戶'選擇他們希望控制和監聽事件的資源範圍。通常會有10個左右的客戶和100個左右的資源。但是，客戶端和資源的數量可能會超過1000個。

這當前實現爲由clientid以索引作爲客戶端對象的值進行索引的映射。客戶端對象包含選擇的資源列表問題是，如果資源發生事件，比如說資源A，那麼代碼必須遍歷每個客戶端，然後遍歷客戶端中的每個列表。我擔心表演。

是否有更高效的算法來處理這種可能的瓶頸？

安格斯

Answer 1

您的結構看起來像{client:[resource]}但高效的事件傳遞需要{resource:[client]}

Answer 2

看來你想要做一個反向查找，所以來看看支持這個boost.bimap。

Answer 3

插入標準的免責聲明：過早的優化是壞的，你知道之前，你有性能問題並不複雜的事情

如何只具有第二，逆數據結構，資源的一個HashMap，包含列表有興趣的客戶更多的工作因爲克萊因和資源的變化，但可能值得。

Answer 4

你運行一個探查？剖析器是否註冊爲真正的瓶頸？

10個客戶端和100個資源對於現代個人電腦來說沒有任何意義。簡單的std :: map可以非常快速地查找。 事情是這樣的：

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

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

這只是一個想法，而缺少一些東西，有它的工作（例如像排序標準客戶端）

Answer 5

或者你也可以有你的資源列表作爲映射，資源作爲鍵和布爾值作爲值。

喜歡的東西

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

，代替目前的

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

查找變快。