zen*_*nna 5 c++ algorithm optimization set data-structures
例如,我有一个整数列表1,2,2,3,4,1.我需要能够检查不同列表之间的等价(==).
但是,我并不是指一个简单的数字比较.这些列表中的每一个实际上表示集合分区,其中列表中的位置表示元素的索引,而数字表示组的索引.例如,在前者中,元素0和元素5在同一组中,元素1和2在同一组中,元素3和4都在它们各自的组中. 该组的实际索引并不重要,只有分组.
我需要能够在这个意义上测试等价,所以例如前面的列表将等同于5,3,3,2,9,5,因为它们具有相同的分组.
我这样做的方法是将数组减少为一种正常形式.我发现所有数字都与第一个数字具有相同的值,并将这些全部设置为0.然后我继续在列表中找到一个新数字,找到相同值的所有数字,并将它们全部设置为1.继续以这种方式.
在我的例子中,两个数字都会减少到会减少到0,1,1,2,3,0当然我可以只使用简单的比较来查看它们是否相同.
但是这很慢,因为我必须在列表上进行几次线性传递.那么为了减少追逐,有没有更有效的方法将这些数字减少到这种正常形式？
更一般地说,我可以一起避免这种减少,并以不同的,也许更有效的方式比较数组吗？
实施细节
Jer*_*ock 18
尝试并行迭代这两个序列,将std::map第一个数组中的值(或数组)保持为第二个数组中的值,反之亦然.如果你找到一个不在你表中的一对,那么添加它,除非表中有第一个或第二个数字的东西(因为这表明不平等).例如:
1,2,2,3,4,1
5,3,3,2,9,5
您可以添加1-> 5,2-> 3,3-> 2和4-> 9,比较将通过.对于略有不同的东西:
5,3,3,2,9,5
1,2,2,3,2,1
你会添加5-> 1,3-> 2,2-> 3,然后9-> 2会失败,因为在第二个序列中已经存在2的绑定; 因此,你会知道序列不是等价的.
对于创建哈希函数,您可能需要执行正在进行的规范化,但它应该只需要一次遍历序列.同样,保持两个方向的地图,但如果在输入序列中找到未知元素,则将其映射到下一个可用数字,否则使用地图将输入序列转换为标准化序列.