最佳搜索性能收集策略？

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

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

最佳搜索性能收集策略？

回答

相关问题