代码之家 › 专栏 › 技术社区 › Dominic Rodger

比较两种地图矢量

diff c++

6

Dominic Rodger · 技术社区 · 16 年前

vector<map<string, int> > .

我目前正在做什么(伪代码):

for i in 0... min(length(vector1), length(vector2)):
    for (k, v) in vector1[i]:
        if v != vector2[i][k]:
            // report that k is bad for index i,
            // with vector1 having v, vector2 having vector2[i][k]

for i in 0... min(length(vector1), length(vector2)):
    for (k, v) in vector2[i]:
        if v != vector1[i][k]:
            // report that k is bad for index i,
            // with vector2 having v, vector1 having vector1[i][k]

vector1 有 a, b, c, d 和 vector2 a, b, b1, c, d (报告称,该公司已破产 b1 , c d 矢量1

i ,并移动到与第一个向量中的下一个条目相匹配的位置,从 vector2[i+1] .

我在C++中工作,所以欢迎C++解决方案,但是任何语言或伪代码的解决方案也会很棒。

例子

给定任意贴图对象: a , b , , D , e f 和 g

具有 矢量1 : A. B , D E , F

和 : A. C , F

B 矢量1 ,及 vector2's c != vector1's d

或者(我认为这是一个相当有效的结果)

vector1's b != vector2's c 额外的 D 矢量1

编辑

std::set_difference ,然后对两个集合的差异进行匹配,找出哪些条目相似但不同,哪些条目完全不存在于另一个向量中。

5 回复 | 直到 16 年前

1

4

Glen 16 年前

类似于 std::mismatch 算法

你也可以使用 std::set_difference

2

1

bdonlan 16 年前

diff longest common subsequence 在两个向量中(使用映射相等),然后递归非公共部分。最终,您将有一个相同的向量子序列和没有公共元素的子序列的交替列表。然后,您可以很容易地从中产生您喜欢的任何输出。

将它应用于两个向量,就可以了。

请注意,由于映射比较昂贵,如果您可以对映射进行散列(使用强散列-冲突将导致不正确的输出)并使用散列进行比较,您将节省大量时间。

一旦您在末尾找到不匹配的子序列,您将得到如下结果:

Input vectors: a b c d e f, a b c' d e f
Output:
   COMMON a b
   LEFT c
   RIGHT c'
   COMMON d e f

c 和 c'

如果突变和插入相邻,则会变得更复杂:

Input vectors: a b V W d e f, a b X Y d e f
Output:
   COMMON a b
   LEFT V W
   RIGHT X Y
   COMMON d e f

确定是否匹配 V W 反对 X 或 Y

当然,如果您不关心地图的内容如何不同,那么您可以停在这里,您就有了所需的输出。

3

0

Ari 16 年前

你到底想达到什么目的?你们能准确地定义你们期望的输入输出吗?伪代码在向量索引处比较贴图。如果这不是正确的语义,那么是什么?

4

0

Dewfy 16 年前

你能把每一张地图和某种校验和(或布鲁曼过滤器)联系起来吗?在一次检查中,你就可以判断比较是否有意义。

5

0

Gunther Piez 16 年前

向量1的索引1处的额外b,以及向量2的c!=向量1的d。

和

向量1的索引1处的额外b,额外在v2中

因为不清楚“c”是否应该与“d”相比较,所以它也可以与“b”相比较。我假设向量没有排序,因为std::map没有提供关系运算符。相反,这些地图在我看来完全不相关;-) 所以你的例子有点误读。甚至可能是

具有 a c f e

这是二次运行时。

for i in 0... length(vector1):
    foundmatch = false;

    for j in 0... length(vector2):
        mismatch = false;
        for (k, v) in vector1[i]:
            if v != vector2[j][k]:
                mismatch = true;
                break; // no need to compare against the remaining keys.

        if (!mismatch) // found matching element j in vector2 for element i in vector1
            foundmatch = true;
            break;  // no need to compare against the remaining elements in vector2

    if (foundmatch)
        continue;
    else
        // report that vector1[i] has no matching element in vector2[]
        // "extra b at i"

如果要查找缺少的元素,只需交换vector1和vector2。

如果您想在vector2中的某个元素与vector1中的某个元素仅在一个键中进行不匹配的检查,则必须在“无需与剩余键进行比较”周围添加其他代码。