我正在处理一个项目,其中数组是所有数据结构的默认值,并且每个查询都是线性搜索的形式:
- 需要一个特定名称的客户?
customer.Find(x => x.Name == name)
- 需要一个特定唯一标识符的客户?
customer.Find(x => x.Id == id)
- 需要一个特定类型和年龄的客户?
customer.Find(x => x is PreferredCustomer && x.Age >= age)
- 需要一个特定名称和年龄的客户?
customer.Find(x => x.Name == name && x.Age == age)
在几乎所有情况下,查找条件都是明确定义的。例如,我们仅按照属性Id、Type、Name或Age之一或多个来搜索客户。我们很少使用其他任何搜索方式。
是否有一种良好的数据结构支持这些类型的任意查询并具有优于O(n)的查找?是否有.NET的现成实现?
IDictionary<int, IEnumerable<Customer>> AgeIndex
和IDictionary<String, IEnumerable<Customer>> NameIndex
,通过使用var results = AgeIndex[age].Intersect(NameIndex[name])
可以获得比线性更好的时间。它的时间复杂度是 O(m),其中 m 是两个结果集大小的总和,但如果没有在所有可能的搜索条件上建立索引(例如IDictionary<AgeNamePair, IEnumerable<Customer>> AgeNameIndex
),你就无法做得更好了。这是时间/空间权衡的一种体现。 - DathanAgeIndex[age].Insersect(NameIndex[Name])
的结果并不比线性搜索更好。假设我有几个名叫Steve的人,他们的年龄分别为20、21、22、23和25岁。当我搜索20岁的人时,我会得到名字为Steve的结果--因此我们将其传递给名称索引,然后我会得到5个年龄不同的Steve,或者我会得到一组不同姓名的20岁人。所以我们又回到了线性搜索。 - Juliet