1
\$\begingroup\$

dataListOne and dataListTwo will be full of BO objects (around 4000 - 5000).

Lets say dataListOne comes with objects with business keys: "one,two,three,one" and dataListTwo has: "three,four,five".

At the end I must have:

  • insertList: "one,two"
  • updateList: "three"
  • deactivateList: "four,five"

There may be 2 BO's with same business key but different properties but I do not care about that.. So once I process a BO which has a businessKey "one" in dataListOne, if there comes another, I will not care about it..

What kind of approach should I take?

/*
Base Business Objects are considered to be same if they have the same businessKey !
 */
public class DataDiffContainer<BO extends BaseBusinessObject> {

    private List<BO> insertList = new ArrayList<BO>();
    private List<BO> updateList = new ArrayList<BO>();
    private List<BO> deactivateList = new ArrayList<BO>();

    private Set<String> handledString = new HashSet<String>();


    public void performDiff(List<BO> dataListOne, List<BO> dataListTwo) {
        for (BO dataOne : dataListOne) {
            if (handledString.contains(dataOne.getBusinessKey())) {
                // See the comment above class declaration
                continue;
            }
            boolean found = false;
            for (BO dataTwo : dataListTwo) {
                if (dataTwo.equals(dataOne)) {
                    updateList.add(dataOne);
                    dataListTwo.remove(dataTwo);
                    // we already know what to do with this object,
                    // so we may as well remove from the List that we need to check..
                    found = true;
                    break;
                }
            }
            if (!found) {
                insertList.add(dataOne);
            }
            handledString.add(dataOne.getBusinessKey());
        }

        // What is remaining in dataListTwo data should be dectivated:
        for (BO bo : dataListTwo) {
            if (bo.isActive())
                deactivateList.add(bo);
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ How is your equals method implemented if you need to have dataTwo.equals(dataOne) in your updateList? How many duplicate keys do you expect? Also maybe not a performance improvement, but you can use the return value of Set.add() instead of your contains. \$\endgroup\$ – Marvin Nov 21 '15 at 16:02
  • \$\begingroup\$ @Marvin Sorry, what do you mean "if you need to have dataTwo.equals(dataOne) in your updateList" \$\endgroup\$ – Koray Tugay Nov 21 '15 at 16:14
  • \$\begingroup\$ Sorry, what I meant was: if dataOne and dataTwo are equals according to your method, why would you need to update anything? \$\endgroup\$ – Marvin Nov 21 '15 at 16:48
  • \$\begingroup\$ @Marvin they have fields like foo and bar and their values might be different. \$\endgroup\$ – Koray Tugay Nov 21 '15 at 17:10
  • \$\begingroup\$ @Marvin they are equal if they have the same business key, think like people, they have same names so same person but they may have different weight, age etc.. I need to update them.. \$\endgroup\$ – Koray Tugay Nov 21 '15 at 17:11
3
\$\begingroup\$

List is not a very performant data structure when you need to search and match elements. Here you have a nested for loop, with even one more "hidden" loop when dataListTwo.remove(dataTwo); is called.

To improve the performance, I can suggest to operate on Maps. If it is not possible to change the signature of performDiff method, the contents of the lists can be transformed into two Map<String, BO> objects, where the key points to BO.getBusinessKey ref and the value contains the BO itself. The transformation method:

private Map<String, BO> toMap(List<BO> dataList) {
  final Map<String, BO> items = new HashMap<>();
  for (BO item : dataList) {
    items.put(item.getBusinessKey(), item);
  }
  return items;
}

This will need only two loops, one on dataListOne and another on dataListTwo.

The main logic of the improved method will make a single iteration on the keys of dataOne map. The matching of keys in the maps will perform much faster:

public void performDiff(List<BO> dataListOne, List<BO> dataListTwo) {
  final Map<String, BO> dataOne = toMap(dataListOne);
  final Map<String, BO> dataTwo = toMap(dataListTwo);
  for (String key : dataOne.keySet()) {
    final BO boToUpdate = dataTwo.get(key);
    if (boToUpdate != null) {
      this.updateList.add(dataOne.get(key));
      // or even: this.updateList.add(boToUpdate);
      dataTwo.remove(key);
    }
    else {
      this.insertList.add(dataOne.get(key));
    }
  handledString.add(key);
  }
  for (String key : dataTwo.keySet()) {
    final BO bo = dataTwo.get(key);
    if (bo.isActive()) {
      deactivateList.add(bo);
    }
  }
}

This can also be transformed in Java8 streams processing to get a more elegant solution, but since the original code strongly looks like "before-Java-8", I decided to keep the style.

To compare the solutions, I've also written a simple test with an ad-hoc BO object definition. The tests executed on 6K objects, with 5900 "inserts", 100 "updates" and 5900 "deactivated" expected items in the results gave the following:

original time: between 350 and 450 ms.

improved solution: between 8 and 15ms.

For this implementation, there is still a drawback concerning duplicate items from the original lists. Only the last occurrence of each duplicate will be retained in the Maps. But since you say that you don't care about duplicates, I don't care about them neither :)

P.S. And I'm not sure if it is still necessary to keep the handledString object, if it was used only to check for processed items.

\$\endgroup\$
5
\$\begingroup\$

I would go down the simple road:

1) Converting both lists to sets

2) Use set operations:

    Set<Integer> update = new HashSet<>(list1);
    Set<Integer> insert = new HashSet<>(list1);
    Set<Integer> delete = new HashSet<>(list2);
    update.retainAll(delete);
    insert.removeAll(delete);
    delete.removeAll(update);

Done.

Even if it is not the fastest solution, it should not be too bad for only 5k objects. It is simple, readable and not errorprone.

\$\endgroup\$
  • 1
    \$\begingroup\$ This is a nice solution and it performs fast. But there are are two drawbacks: 1) .removeAll() and retainAll() both return booleans, so you cannot assign the result to the target collections directly. 2) both the operations do change the contents of the source Sets, so an additional conversion from sorce list1 to a Set will be necessary. \$\endgroup\$ – Antot Nov 22 '15 at 8:18
  • \$\begingroup\$ @Antot Thanks :] I haven't done java for a while. But this should do the trick ;) \$\endgroup\$ – Thomas Junk Nov 22 '15 at 9:36
1
\$\begingroup\$

Can you sort the lists by businessKey? If so, you could sort both lists, then do your comparisons. After finding a match, you could remember the position of the match and start your next search there, since the keys are in order. This would greatly reduce the number of comparisons you make in the general case.

You might want to do a few checks before starting your search. For example, if the last item of (sorted) list one is less than the first item of (sorted) list two, then you know there's no overlap and nothing to search. (And the reverse is true, too - if the last item of list 2 is less than the first item of list 1, then no overlap.)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.