c++ - 正在检查大型订购 list 中的成员资格？

Question

我在C中有一段代码可以顺序生成大量数字，并且我想检查这些数字是否在排序列表中。该列表是使用numpy创建的，具有约109个元素，如上所述，这些元素从最小到最大顺序排列。 C代码检查其结果是否在此列表中的最快最快方法是什么？我应该使用哪种数据结构(如果包含C++ STL)？我当时以为在无序 map 上进行二进制搜索可能最快，但我不确定。
此外(这可能是最重要的事情)，我应如何在程序中包括数字列表-只需将其复制并粘贴到文件中即可？还是冒险进入SQLite或另一个数据库？

Answer 1

理论上最快的方法(实际上也可能是实践中的方法)是O(1):使用位图，即std::vector<bool>(它的特殊实现是每个条目仅使用一位)。仅当在原始列表中时，才将i位设置为true。这使您可以通过单个内存提取来执行检查。缺点是，这可能会花费比您更多的内存，具体取决于列表中的最大数量。
如果不合适，则可以考虑使用std::set(O(n log n))，std::unordered_set(O(1))或带二进制搜索的排序std::vector(O(n log n))。测量以查看最快。
如果仍然不够性能，您还可以考虑使用Bloom filter作为快速检查来排除许多未命中的对象，然后再开始进行较慢的搜索。