c - C 从列表中查找字符串的子集

Question

我有一个 1M 条目的列表，我想排除其中 20,000 个条目的子集（这两个列表的顺序不同，因为它们具有相同的键（字符串））。任何人都可以在 C 中建议一个快速搜索算法来做到这一点吗？

我不想每次都阅读每一个 20K ID 并查看 1M 的列表。任何建议都是最有帮助的。

谢谢你。

Answer 1

您要使用的是哈希集。哈希集是哈希表的一种特殊情况，它基本上以恒定时间记录集合中是否存在元素。所以，你要做的就是将你的 20k 个 ID 插入哈希集中，然后遍历 100 万个字符串，看看它们是否存在于哈希集中。

供您参考，这是 C 中哈希集的实现：https ://github.com/avsej/hashset.c

您的运行时间将是 O(n)，因为对于 1M 字符串的每次检查，这将是恒定时间。

Answer 2

首先对两个列表进行排序。然后你可以一起遍历它们，将列表中的指针推进到另一个指针后面。

你必须使用C吗？这听起来像是 Perl 的工作。

Answer 3

在开始搜索列表之前，将 20,000 个键包含在哈希表中。然后对于列表中每个项目的键，如果在哈希表中找到该键，则从列表中排除该项目。