1

我有一组具有以下界面的对象：

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？

别的东西

有没有其他更好的方法来实现这一目标？

4

4 回答 4

2

对于基于键的快速查找，您不能比关联容器做得更好：无论是哈希表（例如）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”或等效类，在这种情况下，您应该查看.NET 中的问题 multimap。

于 2013-05-09T08:58:26.713 回答
0

您列出将采用 O(n) 进行搜索，而字典应采用 O(1) 并在内存大小方面存在压力。所以你的字典方法将是最快的

于 2013-05-09T08:58:56.483 回答
0

有几件事可以奏效：

  • 如果您可以接受仅使用列表并扫描它们的性能，那么您就完成了！
  • 你可以使用 2+ 字典 : IDictionary<string,List<IEntity>>。Dictionary1 键入 Key1，Dictionary2 键入 Key2 等。将所有实体存储在具有该键的列表中。根据您没有通过字典索引的属性，接受较差的查找性能。
  • 也许使用trie数据结构。
于 2013-05-09T08:59:20.127 回答
0

所以，我有一个IEnumerable<IEntity>，如果键是独立的，那么它很简单，

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-09T09:07:41.437 回答