我想知道基于不同字段搜索大型数据集的最佳方法是什么。 例如,Person 对象定义如下:
Person:
first name
last name
phone numbers
我有 10 万个 Person 类型的对象,我想根据任何字段搜索特定的人?
我尝试使用不同的字段对数据集进行排序,以便在 O(logn) 时间内执行搜索操作,但我知道这不是正确的方法。
最佳答案
对此没有唯一的答案,因为正确的答案(在很大程度上)取决于您对速度与额外存储的关注程度。
如果你想要绝对的最大速度,并且根本不关心使用额外的存储空间,是的,你可以创建三个数据拷贝,每个字段排序一个,当输入搜索时,只需使用适当的一。这可能不像它第一次出现时那么可怕。假设您的字符串平均每个约 10 个字节,因此结构的总大小约为 30 个字节。其中 100'000 每个拷贝大约有 3 兆字节,总计约 9 兆字节。在过去,这显然是令人望而却步的——但现在一台典型的机器至少有 8 GB 的 RAM,这并没有那么糟糕。
假设您排除了这种可能性,下一个最明显的可能性是在原始数据中建立索引——将原始数据放入一个数组中,然后为每个字段建立一个索引,索引中的每个条目都包含数据对于一个字段,以及指向主要数据的指针/下标。每个索引条目可以是 ~14 字节,因此每个索引大约是整个数据大小的一半。只有三个字段,您不会节省很多,但确实可以节省一些——而且极复杂性成本最低。有了更多字段,您将节省更多。
另一种可能性是将您的索引实现为哈希表。这里的主要优点是您可以避免重复存储日期。例如,如果您计算一个 16 位散列,每个桶有 2 个条目,您可以在 ~512K 字节中存储一个索引。如果桶已满,但没有条目与您的输入匹配,您将重新散列并尝试另一个桶。继续前进,直到找到您的元素或找到一个空桶。
关于c++ - 基于多个字段搜索大数据集的有效方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19691333/