language-agnostic - 包含常数集的测试

Question

问题陈述:

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

---

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

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

想到的部分解决方案包括

• 完美的哈希函数(对于大型集合来说代价高昂)
• 范围测试:foreach(b in ranges) if(b.l <= v && v <= b.h) return true;
• 树/索引(在某些情况下比其他树/索引更昂贵)
• 表查找(对于大型集合来说成本高昂)
• 其中任何一个的逆(kodos 到 Jason S )

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

可能有用的主题包括:

• Huffman coding

---

注意:这不是家庭作业。如果它是作为低于博士水平的家庭作业发布的，那么教授应该用 Nerf 枪射击(如果你没有得到这一点，那么重新阅读问题，这非常重要)

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

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

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

Answer 1

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

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