Comparing two vectors of maps

Question

I've got two ways of fetching a bunch of data. The data is stored in a sorted vector<map<string, int> >.

I want to identify whether there are inconsistencies between the two vectors.

What I'm currently doing (pseudo-code):

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]

This works in general, but breaks horribly if vector1 has a, b, c, d and vector2 has a, b, b1, c, d (it reports brokenness for b1, c, and d). I'm after an algorithm that tells me that there's an extra entry in vector2 compared to vector1.

I think I want to do something where when I encountered mismatches entries, I look at the next entries in the second vector, and if a match is found before the end of the second vector, store the index i of the entry found in the second vector, and move to matching the next entry in the first vector, beginning with vector2[i+1].

Is there a neater way of doing this? Some standard algorithm that I've not come across?

I'm working in C++, so C++ solutions are welcome, but solutions in any language or pseudo-code would also be great.

Example

Given the arbitrary map objects: a, b, c, d, e, f and g;

With vector1: a, b, d, e, f

and vector2: a, c, e, f

I want an algorithm that tells me either:

Extra b at index 1 of vector1, and vector2's c != vector1's d.

or (I'd view this as an effectively equivalent outcome)

vector1's b != vector2's c and extra d at index 2 of vector1

Edit

I ended up using std::set_difference, and then doing some matching on the diffs from both sets to work out which entries were similar but different, and which had entries completely absent from the other vector.

Answer 1

Something like the std::mismatch algorithm

You could also use std::set_difference

Answer 2

What exactly are you trying to achieve? Could you please define precisely what output you expect in terms of the input? Your pseudo code compares maps at the vector index. If that is not the correct semantics, then what is?

Answer 3

Can you associate with each map some kind of checksum (or Blumen filter) - that at single check you could be able to decide if comparison has a sense.

Answer 4

In your example, note that is not possible to differentiate between

Extra b at index 1 of vector1, and vector2's c != vector1's d.

and

Extra b at index 1 of vector 1, extra d at index 2 of v1, and extra c at 1 in v2

because it is not clear that "c" shoud be compared to "d", it could be compared to "b" either. I assume the vectors are not sorted, because std::map doesn't provide a relational operator. Rather are the maps, which is as far as I see completly irrelevant ;-) So your example is slightly misreading. It could even be

Compare b f e a d

with a c f e

You can check each element of the first vector against each element of the second vector. This has quadratic runtime.

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"

If you want the find the missing elements, just swap vector1 and vector2.

If you want to check in a element in vector2 mismatches to a element in vector1 in only a single key, you have to add additional code around "no need to compare against the remainig keys".

Answer 5

It sounds like you're looking for the diff algorithm. The idea is to identify the longest common subsequence of the two vectors (using map equality), then recurse down the non-common portions. Eventually you'll have an alternating list of vector sub-sequences that are identical, and sub-sequences that have no common elements. You can then easily produce whatever output you like from this.

Apply it to the two vectors, and there you go.

Note that since map comparison is expensive, if you can hash the maps (use a strong hash - collisions will result in incorrect output) and use the hashes for comparisons you'll save a lot of time.

Once you're down to the mismatched subsequences at the end, you'll have something like:

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

You can then individually compare the maps c and c' to figure out how they differ.

If you have a mutation and insertion next to each other, it gets more complex:

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

Determining whether to match V and W against X or Y (or not at all) is something you'll have to come up with a heuristic for.

Of course, if you don't care about how the content of the maps differ, then you can stop here, and you have the output you want.