使用什么数据结构？ (哈希地图与特里与？)

发布时间：2020-12-16 10:19:25 所属栏目：百科来源：网络整理

导读：我有一个C函数,可以生成大约600万个唯一数组.这些数组每个元素总共有17个元素,每个元素都是0到16之间的整数.我还有一个稍微修改过的函数版本,它也会产生大约600万个相同类型的独特数组.我的问题是,第二个产生的结果比第一个产生的结果少45,000,我想看看这些

我有一个C函数,可以生成大约600万个唯一数组.这些数组每个元素总共有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]

(或其某些转换)然后对它们执行快速成员资格测试.正如标题所说,我确实怀疑哪些数据结构可以完成这项工作,但我不确定尝试或哈希图是最好的选择.

这是一种检测另一种算法中的缺陷的算法,而不是将在生产中使用的算法.我感兴趣的是这样做的方式将被编码并在人类术语中相对快速地返回结果,不一定要刮掉毫秒,因此存在易于完成大部分工作的grok库绝对是一个优点.

解决方法

最优性取决于排列的分布方式以及插入与搜索的比率.既然你不关心最优性,但只是想要一种直接的方法来测试一个假设而不用等待整晚的结果,我的直觉说：

整数[0,16]可以表示为五位数,因此它们中的十七个可以表示为85位(11字节)二进制字符串.因此,您可以使用许多可用于存储已排序/散列字符串集的库中的一个,并对其进行成员资格测试,然后完成.它不会像调谐的trie一样快或缓存一致,但是在几秒钟内完成66mb的数据研磨就足够了,你将在午餐时间完成.

如果没有这样的库是方便的,你必须从头开始工作,我只是制作一个字符串的排序列表,然后通过二进制搜索进行成员资格测试.这可以解决类似O(n log n m(n log n))= O(2×mn log n)的问题,例如二次时间为m→n.如果这只是在生产过程中作为离线作业运行一次或两次,那可能就足够了;如果你每天不止一次这样做,我会担心缓存局部性并使用trie或B-tree.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!