请教 高效数据操作问题

wmpact518

现在有如下的问题：
我们通过多模式字符串匹配算法找到了一篇文本中出现的所有我们关心的关键字，并返回这些关键字的ID，比如返回的关键字ID是{1，2， 300， 42， 293， 834，........}。
现在有一组与表达式，每个与表达式是多个关键字的与，比如如下的两个表达式{{2, 42}, {293, 100}},现在我们的任务是看是否有表达式在关键字ID列表中出现，如果是的话返回该表达式的ID，比如第一个表达式{2， 42}表示同时出现2号和42号关键字，而在关键字ID列表中确实同时存在2， 42号关键字，所以返回第一个表达式的ID。
要完成这个任务最简单的做法就是对每个表达式进行循环，依次判断表达式的每个关键字是否出现在ID列表中。但是这样算法的效率很低，有没有更加有效的算法来完成这个工作？

redspider

map or set

glasslion

我觉得位图效率最高。毕竟ID的范围一般是可以确定的

swxlion

没明白。
不过如果要用map或set，且单个对象比较大或复杂的话，不妨可以使用我签名项目中的GDST子项目的TSimpleMap，或者用TRBTree 或 TAVLTree自己实现一个容器。
因为我曾在Fedora 4上跟过一次map，它压入一个对象时会构造三个临时对象，一共构造四次，析构三次，最后一次构造真正存放在map中的对象。
如果对析构函数对相关的克隆有影响（比如从全局对象池中清除与自己的ID相关的索引（看具体实现，克隆对象的ID有可能是一样的）），或者构造/析购函数比较废效率的话，可以用我的实现。只不过为了效率，使用上我的实现可能要比map麻烦点。^_^

wmpact518

初步感觉可行，但是ID的范围是32位无符号整数的范围，如果使用位图冲突是不是比较高？如使用50000的位图，我们用除以50000取模，这样50001和1号关键字对应相同的位。

wmpact518

maybe 加一些布隆过滤器的思想会好一些  呵呵  试一次吧 谢谢