c – 查找要删除的项目
|
我有一个数据池(X1..XN),我想找到相同值的组.比较非常昂贵,我无法将所有数据保存在内存中.
我需要的结果是,例如：
(行的顺序或行内的顺序无关紧要). 如何通过成对比较实现这一点？ 这是我到目前为止所拥有的： 比较所有对(Xi,Xk)与i <1. k,并利用传递性：如果我已经找到X1 == X3和X1 == X6,我不需要比较X3和X6. 所以我可以使用以下数据结构： map: index --> group multimap: group --> indices 其中组被任意分配(例如输出中的“行号”). 对于一对(Xi,Xk),其中i <1. k： >如果我已经分配了一个组,则将k放入该组 >如果他们不相等： >如果我还没有分配组,请为i分配一个新组 如果我对项目的顺序很谨慎,这应该有用,但我想知道这是否是解决这个问题的最佳/最不令人惊讶的方法,因为这个问题似乎有点普遍. 背景/更多信息：目的是重复删除项目的存储.他们已经有一个哈希,如果发生碰撞,我们希望保证完整的比较.所讨论数据的大小具有非常尖锐的长尾分布. 迭代算法(找到任意两个重复项,共享它们,重复直到没有重复项)可能会更容易,但我们需要非修改诊断. [编辑]关于哈希：为了这个问题的目的,请假设一个无法替换的弱哈希函数. 这需要对现有数据进行一次性重复数据删除,并且需要处理散列冲突.最初的选择是“快速哈希,并在碰撞时进行比较”,所选择的哈希结果有点弱,但改变它会破坏向后兼容性.即便如此,我还是会用一个简单的陈述睡得更好：如果发生碰撞,你就不会得到错误的数据.而不是关于wolf attacks的博客. 解决方法
这是另一种可能更简单的数据结构,用于利用传递性.制作一个需要进行比较的队列.例如,在4项的情况下,它将是[(1,2),(1,3),4),(2,(3,4)] .还有一个阵列用于比较你已经完成的.在每次比较之前,检查之前是否已完成比较,并且每次找到匹配项时,请检查队列并将匹配项目索引替换为其较低的索引等效项.
例如,假设我们弹出(1,比较,它们不相等,推(1,2)到已经访问过的数组并继续.接下来,弹出(1,3)并发现它们是相等的.此时,通过队列并用1替换所有3.队列将是[(1,1),4)],依此类推.当我们到达(2,1)时,它已被访问过,所以我们跳过它,和(1,4)相同. 但我同意以前的答案.由于比较计算成本很高,您可能希望首先计算快速,可靠的哈希表,然后才将此方法应用于冲突. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |