How to optimize nested loops?

Question

I have two foreach loops. One of them contains list of unique emails (outer). I would like to have that as outer loop and increase count by one every time there is a match between an element of outer loop and the inner loop.

My code now:

outer: for (String email : emailsOfContactsWhoFitDynConFilter) {
        for (Contact contact : emailClicks.items) {
            String[] contactLink =  (contact.link).split("\\?", -1);
            String queryStringActivity = getQueryStringByName("elqTrackId", contactLink[1]);

            if (email.equals(contact.EmailAddress) && contactLink[0].equals(linkInDynamicContentSplit[0])) {
                if (queryStringActivity !=null && queryStringDynConLink!=null && queryStringActivity.equals(queryStringDynConLink)){
                    count++;
                    break outer; 
                    } else if (queryStringActivity == null || queryStringDynConLink == null) {
                    System.out.println("  -  Missing elqTrackId. But base the same, count++");
                    count++;
                    break outer;
                }
            }
        }
    }

It works, but problem is these two lines:

String[] contactLink =  (contact.link).split("\\?", -1);
String queryStringActivity = getQueryStringByName("elqTrackId", contactLink[1]);

Are executed too many times which consumes a lot of time.

I could reverse the loops, so it would look like this:

outer: for (Contact contact : emailClicks.items) {
            String[] contactLink =  (contact.link).split("\\?", -1);
            String queryStringActivity = getQueryStringByName("elqTrackId", contactLink[1]);
          for (String email : emailsOfContactsWhoFitDynConFilter) {
          if (email.equals(contact.EmailAddress) && contactLink[0].equals(linkInDynamicContentSplit[0])) {
                if (queryStringActivity !=null && queryStringDynConLink!=null && queryStringActivity.equals(queryStringDynConLink)){
                    count++;
                    break outer; 
                    } else if (queryStringActivity == null || queryStringDynConLink == null) {
                    System.out.println("  -  Missing elqTrackId. But base the same, count++");
                    count++;
                    break outer;
                }
            }
        }
    }

That would be much faster, but my count++ would happen more times than I want, it wouldn't be +1 per unique email.

Answer 1

With a great help from @corsiKlause Ho Ho Ho I could come to the solution:

Map<String, String[]> linkSplitCache = new HashMap<>();
    int count = 0;
    String[] linkInDynamicContentSplit = linkInDynamicContent.split("\\?", -1);
    String queryStringDynConLink = getQueryStringByName("elqTrackId", linkInDynamicContentSplit[1]);
    if (emailClicks != null && emailsOfContactsWhoFitDynConFilter != null) {
        for (String email : emailsOfContactsWhoFitDynConFilter) {
        inner: for (Contact contact : emailClicks.items) {
                String[] contactLink = linkSplitCache.get(contact.EmailAddress);
                if (contactLink == null){
                    contactLink =  (contact.link).split("\\?", -1);
                    contactLink[1] = getQueryStringByName("elqTrackId", contactLink[1]);
                    linkSplitCache.put(contact.EmailAddress, contactLink);
                }

                if (email.equals(contact.EmailAddress) && contactLink[0].equals(linkInDynamicContentSplit[0])) {
                     if (contactLink[1] !=null && queryStringDynConLink!=null && contactLink[1].equals(queryStringDynConLink)){
                        count++;
                        break inner; // this excludes link clicks which were done
                                // twice by the same person
                    } else if (contactLink[1] == null || queryStringDynConLink == null) {
                        System.out.println("  -  Missing elqTrackId. But base the same, count++");
                        count++;
                        break inner;
                    }
                }
            }
        }
    }

Basically what I did was adding the link into the HashMap with the unique key Email address, which makes sure that I don't do the same operation more than once where it's not necessary.

Answer 2

There are a couple good options here, but the first would be to simply cache the String[]. This is a valuable lesson in why you should use methods instead of members.

I suggest having a method of contact.getLinkCache() method, implemented something like I have below. This gives you the benefit of not splitting over and over again (there is a clone in there to protect the data, but clone is a pretty fast method, and unless you've identified this as being too slow, you should probably go with this.

class Contact {

    String link;
    String[] linkSplitCache;

    public void setLink(String link) {
        this.link = link;
        this.linkSplitCache = null;
    }

    public String getLink() {
        return link;
    }

    public String[] getLinkCache() {
        if(linkSplitCache == null) {
            linkSplitCache = link.split("\\?",-1);
        }
        // return linkSplitCache; // could corrupt!
        return linkSplitCache.clone(); // pretty fast array copy
    }
}

If it is too slow, then you would want some kind of map to cache it in, and this would probably be outside the Contact class.

Map<Contact, String[]> linkSplitCache = new HashMap<>();

outer: for (Contact contact : emailClicks.items) {
    String[] contactLink =  linkSplitCache.get(contact);
    if(contactLink == null) {
        contactLink = (contact.link).split("\\?", -1);
        linkSplitCache.put(contact,contactLink);
    }
    // rest of loop here