c# - 多个属性的快速内存搜索

Question

我有一个内存对象列表（大约 50000-100 万个），它有 6-7 个属性（属性）。

要求是用多个属性过滤这个内存列表。线性搜索允许我对列表进行 O(N) 搜索。有没有比通用列表更快的方法来使用更好的数据结构？

我正在使用 C#.NET 4.0。

Answer 1

您可以使用名为 IndexedList 的帮助程序库，您可以从http://indexedlist.codeplex.com/下载它。 使用此库，您可以在对象的任何字段上添加索引，然后在列表中执行快速搜索。默认索引实现使用 Dictionary 来存储索引数据，您也可以更改它。我为我自己的项目创建了这个库，然后我将它作为一个新的开源项目发布。我很高兴听到您对这个库的反馈。

Answer 2

就在几秒钟前，我读到了这个：http ://blog.bodurov.com/Performance-SortedList-SortedDictionary-Dictionary-Hashtable/

似乎随着搜索的进行，这SortedDictionary可能是您最好的选择，但是由于您想按多个属性进行搜索，所以如果您想在搜索和插入大量数据之间取得良好的平衡，那么可能SortedList会以内存使用为代价产生更好的结果.

Answer 3

我能建议的最好的：

1. 为每个必需的属性制作字典（单独的字典）
2. 搜索时，分别逐一查找所需的每个字典并选择最小大小的列表
3. 迭代最小尺寸列表

如果属性值没有大量重复，这种方法将非常有用。但是，如果每个属性都有很多重复项，那么这种方法将非常糟糕。

可能的改进：每个列表进入字典可能的排序，并在使用它后按属性之一进行二进制搜索。