最佳搜索性能收集策略？

我有具有以下接口對象的集合：最佳搜索性能收集策略？

public IEntity 
{ 
    public string Key1 { get; set; } 
    public string Key2 { get; set; } 
    ... some other properties 
}

，我期待爲通過LINQ在這些對象的內存集合查詢的最佳策略。大多數查詢（但不是全部）可能會查找Key1或Key2來訪問實體，所以我不確定查詢它們的最高性能方式是什麼。我的想法是：

的IList < IEntity>

只要堅持這些列表中的一個使用LINQ來過濾他們

IDictionary的<元組<字符串，字符串>，IEntity>

使用key1和key2創建一個多鍵字典，但我不知道如何才能訪問IEntity，如果我只知道一個部分？

別的東西

有一些其他的，更好的方式來實現這一目標？

來源

2013-05-09 Matt Brailsford

It ** all **取決於您要執行的搜索類型。 – mattytommo 2013-05-09 08:56:43

要實現什麼？鑰匙是複合還是獨立？ – Jodrell 2013-05-09 08:59:07

對於基於密鑰的快速查找，您不可能比關聯容器做得更好：或者是諸如Dictionary之類的散列表或者諸如SortedDictionary之類的基於樹的結構。在一個相對罕見的情況下，您的數據結構是從排序的輸入構建而成，並且很少修改，請考慮SortedList。所有這些都有不同的性能特點，所以選擇取決於具體情況。

如果你的鍵有不同的類型，那麼你實際上將不得不去與多個這樣的容器，但在這裏，你可以簡單地只使用一個，並給每個「類型的密鑰」唯一的前綴。例如，你可以決定這樣做：

var dict = new Dictionary<string, IEntity>(); 
var entity = (IEntity)whatever; 

dict.Add("key1:" + entity.Key1, entity); 
dict.Add("key2:" + entity.Key2, entity); 

// and now find by either Key1 or Key2 by using the same prefix

如果密鑰不能保證是唯一的，那麼你就需要一個「MultiDictionary」或等價類，在這種情況下，你應該在這個問題multimap in .NET看看。

來源

2013-05-09 08:58:26 Jon

您的列表將採取O（n）進行搜索，而字典應採取O（1）的內存大小應變。所以，你的字典方法將是最快的

來源

2013-05-09 08:58:56

有幾件事情可以工作：

如果你能接受只用通過他們的列表和掃描的性能，你做！
您可以使用2+詞典：IDictionary<string,List<IEntity>>。在Key1上鍵入的Dictionary1，在Key2上鍵入的Dictionary2等。將所有實體存儲在具有該鍵的列表中。根據未通過字典編入索引的屬性，接受較差的查找性能。
也許使用一個trie數據結構。

來源

2013-05-09 08:59:20

所以，我有一個IEnumerable<IEntity>，如果鍵獨立unqiue那麼它的簡單，

IEnumerable<IEntity> entities = ... 

var byKey1 = entities.ToDictionary(e => e.Key1); 
var byKey2 = entities.ToDictionary(e => e.Key2);

如果不是，

var byKey1 = entities.ToLookup(e => e.Key1); 
var byKey2 = entities.ToLookup(e => e.Key2);

然後，如果你有兩個鍵，

var match = byKey1[key1].Intersect(byKey2[key2]);

來源

2013-05-09 09:07:41 Jodrell

最佳搜索性能收集策略？

回答

相關問題