找出指针是否是C中集合的一部分的最快方法是什么?

给定一个结构上指针 ,我需要很快找到它是否是一个集合的一部分(我必须自己定义/实现)。 我可能会考虑像Bloom Filter这样的技术,但实际上并不知道如何在指针上执行此操作。

该解决方案需要在32位和64位机器上运行。

编辑:所有这些指针(其中2k-5k)指向各种随机存储器地址,因为它们的目标是我无法控制的双向链表的元素。 这可以改为:“通过创建另一个结构,如何在元素中找到只读 双向链表的一部分?”

编辑2:双向链表可能随时间增长,但不是我控制的集合。

从您引用的页面:

Bloom提出了应用技术,如果应用“常规”无差错散列技术,源数据量将需要内存中不可行的大散列区域。 他给出了一个50万字的字典的连字算法的例子,其中90%遵循简单的连字规则,但剩下的10%需要昂贵的磁盘访问来检索特定的连字模式。

如果你只有 2k-5k项目,那么我怀疑你是在谈论“内存中不可行的大散列区域”。

简而言之,我建议使用哈希表。 您需要对数据执行一次O(n)传递以构建表,然后查找将为O(1)

Interesting Posts