我有一个生成大约 600 万个唯一数组的 C 函数。这些数组每个都有 17 个元素，每个元素都是 0 到 16 之间的整数。我还有一个对该函数稍作修改的版本，它也将生成大约 600 万个相同类型的独特数组。我的问题是第二个生成的结果比第一个少大约 45,000 个结果，我想看看这些结果是什么。
所以我的方法是简单地存储第二个函数的所有结果(计算器告诉我这不应该超过 400 MB，这可以保留在内存中)然后查找第一个函数的结果，打印出来那些不存在的。
假设一般方法有意义(如果没有，请告诉)，我正在寻找的是一个合适的数据结构(最好用 C 语言实现)，它可以容纳大约 600 万个独特的排列
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
(或其某些转换)，然后对它们执行快速成员资格测试。正如标题所说，我确实怀疑哪些数据结构可以完成这项工作，但我不确定尝试或散列图是最好的选择。
这是一种用于检测另一种算法缺陷的算法，不会用于生产。我有兴趣以一种可以编码并以人类的方式相对快速地返回结果的方式来执行此操作，而不一定需要几毫秒，因此存在可以完成大部分工作的易于理解的库绝对是一个优势。
最佳答案
最优性在某种程度上取决于排列的分布方式以及插入与搜索的比率。由于您不关心最优性，而只是想要一种直接的方法来检验假设而不用整夜等待结果，我的直觉说:
一个整数 [0,16] 可以表示为一个五位数，因此其中的十七个可以表示为一个 85 位(11 字节)的二进制字符串。因此，您只需使用众多可用于存储排序/散列字符串集并对其进行成员测试的库之一即可。它不会像调整后的 trie 一样快或缓存一致，但它足以在几秒钟内处理完 66mb 的数据，您将在午餐前完成。
如果手边没有这样的库，您必须从头开始工作，我会制作一个排序的字符串列表，然后通过二进制搜索进行成员资格测试。计算结果类似于 O( n log n + m( n log n ) ) = O( 2×mn log n ) eg 二次时间为 m→n。如果这只是在生产期间作为离线作业运行一次或两次，那可能就足够了；如果您打算每天多次执行此操作，我会担心缓存局部性并使用 trie 或 B 树。
关于c - 使用什么数据结构？ ( HashMap 与特里树与？)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6401012/