performance - 查找集合成员的有效方法

Question

我正在使用 2^n 向量，例如n=3 可能的值为:

000, 001, 010, 011, 100, 101, 110, 111

我想找到最有效的方法，给定一组组合说

000, 000, 001, 100, 000, 110, 000, 110

如何查找给定值是否在可能集中。

一种方法是遍历整个列表(蛮力)。另一种方法是使用任何经典搜索方法，例如二进制搜索等 log_2(n) +1

另一种方法是使用布隆过滤器，尽管这是一种概率方法

我想知道在给定位串列表的情况下是否还有其他任何东西可以有效地测试其成员资格。

Answer 1

任何数据结构都可以。无论您的本地字典结构是什么，我都会伸手去拿，因为这很容易做到并且是经过充分测试的代码。通常这是一个散列，尽管它通常被称为字典、HashMap 或 std::unordered_map 等其他名称。有时它是一棵二叉树。散列 (Perl)、字典 (Python)、HashMap。

如果我要推出一个“解决这个问题的完美数据结构”，我可能会希望在 trie 树上有一些变体。但从中获得的最大胜利是一个相当小的因素加速，所以除非我知道它是需要的，否则为什么要费心呢？