logo标签列表

高效插入/查询任意属性的良好数据结构

c#data-structures
6

我正在处理一个项目，其中数组是所有数据结构的默认值，并且每个查询都是线性搜索的形式：

  • 需要一个特定名称的客户？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的现成实现？

3个回答
4

对于内存中的数据，你有几个选择。

大多数选项的时间复杂度为 O(n)。尽管如此，字典查找可以接近 O(1)。

一种选择是将客户信息存储在多个字典中，每个字典的键设置为名称、ID和年龄。如果在字典中使用相同的对象引用，则可以使任何单个查找的时间复杂度为 O(1)，而不需要大量的开销。

当然，随着标准数量的增加，这种方法变得不太实用，但对于 3 条标准来说还不错。

如果您想要更灵活的选择，那么数据库是一个合适的选项。许多数据库都可以作为完全内存数据库工作，包括 SQLite，它可以以比 O(n) 更好的速度进行任意查询。

@朱丽叶：你回到了线性搜索，但是在一个非常受限制的空间内。每次额外的搜索都仅限于第一个有效元素，因此搜索空间要小得多。第二次搜索是O(n)，但N变得非常小。话虽如此，另一种选择仍然是使用内存数据库，它可以为您提供具有任意条件的快速查询... - Reed Copsey
假设有 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），你就无法做得更好了。这是时间/空间权衡的一种体现。 - Dathan
@Dathan：AgeIndex[age].Insersect(NameIndex[Name])的结果并不比线性搜索更好。假设我有几个名叫Steve的人，他们的年龄分别为20、21、22、23和25岁。当我搜索20岁的人时，我会得到名字为Steve的结果--因此我们将其传递给名称索引，然后我会得到5个年龄不同的Steve，或者我会得到一组不同姓名的20岁人。所以我们又回到了线性搜索。 - Juliet
1
@朱丽叶：以你的情况为例。假设你有1000个客户，其中5个是“史蒂夫”，150个20岁左右的人。你使用AgeIndex[age]，返回150个20岁左右的人，并与NameIndex[Name]相交，返回5个史蒂夫。现在，你只剩下一个20个元素集合和一个5个元素集合之间的交集。在这一点上，它基本上是线性的，但你正在处理一个非常小的集合（150+5）与1000个集合相比...此外，相交在内部使用了一个集合，因此它不是以同样的方式进行“线性”搜索。对此进行分析，它比线性搜索快得多，特别是在处理真实数据时。 - Reed Copsey
+1，+答案：起初我持怀疑态度，认为我需要使用像kd-tree这样的奇异数据结构，但这真的很有效，并且帮助将龟速区域的速度提高了5倍。通过更多的优化，我认为我可以挤出更多的速度 - 在此期间，谢谢！ :) - Juliet
显示剩余3条评论
0
为什么不能将数据放入多个字典中？一个字典映射名称到数据，另一个字典映射年龄等信息。
首先，这不是一个非常通用的解决方案。我们不仅在客户端上有这些类型的搜索，而且为了我们经常搜索的数百种集合类型创建成千上万个字典是有点疯狂的。其次，多个字典不能在合理的时间内支持复合键的搜索，例如，如果没有通过一个字典进行线性搜索，我无法搜索具有给定名称和年龄的人。 - Juliet
-1
那跟数据结构有什么关系？ - Andrew Barber
虽然这不是一个结构，但如果他想查询这些数组并且不想为寻找完美的设计而浪费时间，只需在数组上使用LINQ，并结束一天的工作。 - RS999
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接