language-agnostic - 包含对常量集的测试

Question

问题陈述:

给定一组预先已知的整数，生成 测试单个整数是否在集合中的代码。测试函数的域是某个连续范围内的整数。

现在对要测试的范围或集合一无所知。范围可以很小也可以很大(但解决方案可以拒绝太大但更高限制更好的问题)。可能是允许范围内的值很少在集合中，或者它们中的大多数是或介于两者之间。该集合可以是均匀分布的或集群的。可能有很大一部分仅包含/不包含值，或者在大多数 strip 中每种类型的值可能至少有几个。 (有点像分析排序算法时对要排序的项目所做的假设)

目标是生成用于运行测试的有效代码的过程。

想到的部分解决方案包括

完美的散列函数(对于大集合来说代价高昂)

范围测试:foreach(b in ranges) if(b.l <= v && v <= b.h) return true;

树/索引(在某些情况下比其他成本更高)

表查找(对于大集合来说代价高昂)

这些的倒数(科多斯到 Jason S)

似乎理想的解决方案能够选择最好的选项，或者如果没有一个效果很好，则使用树将整个范围分解为多个部分，然后切换到更适合它们的子部分的其他选项。

可能有用的主题包括:

Huffman coding

注意:这不是作业。如果它是作为低于博士水平的作业发布的，教授应该用 Nerf 枪射击(如果你不明白，然后重新阅读问题，这是非常重要的)

注意:这是我几天前遇到的一个问题，我一直在困惑它。我对此没有直接用途，但认为攻击会是一个很酷的问题。我想生成代码的原因是生成的代码不会比一般代码慢(如果需要，它可以是同一件事)并且在某些/许多情况下可能更快。

我发布这个问题是为了澄清我的想法。如果我能提出任何合理或酷的解决方案，我计划将它们作为模板元程序实现(生成代码的另一个原因)

有人注意到这个问题很普遍。这就是我想说的。我希望生成一个可以在一个非常通用的领域工作的系统:某个范围内的整数集。

Answer 1

previous question on dictionary/spellchecking有很多回复提到 Bloom filters ;也许那会有所帮助。

我认为无论如何测试大型集都会很昂贵。