Efficient way to merge two similar objects (where only a few fields are different)

Question

I am being challenged (or confused) by this problem:

I have a List<CustomObject> in which each element has around 20 fields/attributes. In this list I might have sort of duplicate items. Four particular fields may be different, if the others match I would regard them to be equal enough and I want to merge them into a single element.

The question is how to identify these "sort of duplicate" elements. Here are a few approaches I am thinking of:

1. Use a HashMap and use a concatenated string of all similar attributes as "key". Then store the "sort of duplicates" in separate lists per "key". The problem I feel is that the key values will be quite big (like around 3000+ characters, this could be clumsy).

2. Override the Equals method and make a Set<CustomObject> to store the CustomObject. If it exists, override the 4 fields based on business logic and save this new object. A lookup cost for if exists.

3. N x N approach. Looping through N x N doesn't make sense to me and will become expensive as the number of items in the list increases.

I would appreciate any other thoughts on how resolve this.

Answer 1

Edited to address the issue of 4 specific fields allowed to mismatch.

@Hans-Martin Mosner is right that the remaining fields form a unique key. It's best to address this with the database, but it sounds like you can't in your circumstances. In this case, Option 1 seems to be the superior choice.

Option 3 is obviously undesirable because of its O(N^2) complexity, but why not Option 2? The main reason is that once we add an object to a set, we cannot retrieve it without iterating through the collection at O(N). So there's no way to "merge" two equal objects in O(1) (the main reason for preferring 2 to 3), other than simply replacing the existing object. This doesn't sound like what you wanted. You can use a modified form of Option 2 by using a HashMap<CustomObject, CustomObject>, but this is basically Option 1 except you're not keeping a list.

So what does this key look like?

If you want the key to be a CustomObject (for either Option 1 or modified Option 2), then we'll need to override hashCode() to use all and only the fields that we care about (e.g. like this). This is an especially nice option if you've already overridden equals(obj).

If you want a String key, then you can concatenate all the field values that we care about (including a separator to prevent values from one field flowing into another). E.g. assuming that field1, ... fieldN have a suitable toString():

String getKey(CustomObject obj) {
   return obj.getField1() + "|" + ... + "|" obj.getFieldN();
}

Original answer assuming any 4 fields were allowed to mismatch.

As ugly as it seems, I think the most viable algorithm proposed is Option 3^*. Here's why.

The Problem of Option 1

Let's suppose we have our list and we're going through elements one by one. We encounter the problem on the first element. How do we even know what the "concatenated string of all similar attributes" is for this element? We have nothing to compare against. In order to determine this, we need to scan through the rest of the elements and compare them to this particular element. It's up to you if we break once we find a match, or look for a better candidate / all candidates.

Okay, on to the next element. If it was marked as a duplicate already, then we might be able to skip this. Otherwise, then we are in exactly the same situation as before: we have to run through each of the subsequent elements looking for a potential match.

(You see where this is going, don't you?)

The Problem of Option 2

So you've decided to stick our objects in a Set. Great, we've got 2 popular choices: a HashSet and a TreeSet.

If we choose a HashSet, then we need to define a hashcode, particularly one such that equal objects have the same hashcode. Because of our fuzzy version of equality, defining a suitable hashcode is going to be really difficult. Given what I know of the problem, the only consistent hash seems to be a constant. (You may be able to do better, but it's not an easy task.) Practically this means that set.contains(myObj) will have linear lookup time, so we're back to O(N^2) for overall complexity.

If we choose a TreeSet, then we need to define an ordering. Again, good luck with finding one that works with our fuzzy equality. Worst case for this will also give us linear lookup time.

Aside

The problem of detecting duplicates is hard. For example, what potential duplicates do we have among this data?

A = { a: 1, b: 1 }, B = { a: 1, b: 2 }, C = { a: 2, b: 1 }, D = { a: 2, b: 2 }

Pairwise, A and D are each similar to both B and C. But B and C are not similar to each other; nor are A and D similar.

^{_{*Technically, option 3 takes N(N+1)/2 steps and not N^2, but I'm assuming that you are referring to the big-O.}}

Answer 2

This sort of problem is much easier solved if you know the meaning of those records and the process by which duplicates happen. Look at the actual fields and decide which ones should be "keys" and which ones should be "values", then you have basically solved it (you need to decide on a proper database representation but that's an implementation issue).

So if you already know the 4 fields that are variable, all others constitute the primary key. You could either simply concatenate them to form a hash key, or build a hierarchical map structure, or let a relational database engine figure out the details. All of these might be viable solutions depending on your problem details which you omitted from the question.

Answer 3

The simplest solution would be to implement a method:

bool EqualsEnough(CustomObject other)
{
    return this.A == other.A &&
        this.B == other.B &&
        ... ;  // compare each property pair that matters
}

This may look expensive but it probably isn't. If you start with pairs that are least likely to match, most comparisons will return early with false.