java - 针对特定数据字段的高效搜索算法

Question

所以我实际上被分配编写过滤/搜索算法。

任务:过滤:搜索并列出满足指定属性的对象

假设整个系统是一个学生注册记录系统。

我有数据如下所示。我需要按这些属性进行过滤和搜索，例如按性别或学生姓名或出生日期等进行搜索/过滤。

学生姓名， 性别， 出生日期，手机号码

这些领域有没有具体高效的算法公式或方法。

例如，字符串和整数都有自己类型的高效搜索算法，对吧？

这就是我要做的。我将根据上面的这些字段编写一个用于搜索/过滤的二元搜索算法。

就是这样。但是，说实话这很容易。

但我只是很好奇，对于这些字段中的每个字段来说，高效搜索/过滤算法的正确且适当的编码方法是什么？

我显然不会使用顺序搜索算法，因为这将涉及大量数据，所以我不会迭代这些数据中的每一个降低效率表现。

如果数据较少，将在需要时使用顺序搜索算法。

Answer 1

搜索是一个非常广泛的主题，它完全取决于您的用例。在构建有效的搜索算法时，您应该考虑以下因素

• 您的数据大小是多少？ -它是固定的还是不断变化的 定期？
• 插入/修改/删除的频率 你的数据？
• 您的数据是排序的还是未排序的？

• 您是否需要基于前缀的搜索，例如自动搜索、自动完成、最长前缀搜索等？

  现在让我们考虑一下解决方案/方法

  1. 如果您的数据较少且未排序，您可以尝试线性搜索(其时间复杂度为 O(n)，其中“n”是您的搜索引擎的大小)数据/数组)

  2. 如果您的数据已经排序(但情况并非总是如此)，您可以使用二分搜索，因为它的复杂度为0(log n)。如果你的数据未排序然后再次排序数据需要(nlogn)~通常如果您使用 Java，Arrays.sort() 默认情况下使用合并排序或快速排序是(nlogn)。

  3. 如果更快的检索是主要对象你可以想到HashMaps或HashMaps。 Hashmap的元素通过Hashcode进行索引，搜索任何元素的时间几乎是 1 或常数时间(如果你的哈希函数实现很好)

  4. 基于前缀的搜索:既然您提到了按名称搜索，您还可以选择使用“尝试”数据结构。

如果您频繁执行插入/删除/更新功能，尝试是很好的选择。Trie 中元素的查找次数为 0(k)，其中“k”是要搜索的字符串的长度。

由于您拥有插入、更新、删除很常见的注册数据，TRIES 数据结构是一个值得考虑的不错选择。

另外，请检查此链接以在 Tries 和 HashTables 之间进行选择 TriesVsMaps

下面是 Tries(img src:Hackerearth) 的示例表示