3
\$\begingroup\$

This code runs fine without a bug, I need to optimize this code for following interview requirement.

Lets say i need to send it to 1 million contacts and emailBody is ~100Kb.

What code optimization do you recommend to make it faster ? Write code or algorithm to explain the optimization you think will make this code faster, let's say 10x, 100x ?

public String sendEmail(String emailBody, Email email) {
      Hashtable<String, String> dataHash = new Hashtable<String, String>();

      dataHash.put("{{USER_EMAIL}}", email.getEmail());
      dataHash.put("{{USER_NAME}}", email.getName());
      dataHash.put("{{USER_PHONE}}", email.getPhone());
      dataHash.put("{{LOGIN_URL}}", email.getLoginUrl());

      Enumeration<String> tagList = dataHash.keys();

      while (tagList.hasMoreElements()) {
          String tag = tagList.nextElement();
          while (emailBody.indexOf(tag) != -1) {
              int indexOf = emailBody.toLowerCase()
                      .indexOf(tag.toLowerCase());

              String part1 = emailBody.substring(0, indexOf);
              String part2 = emailBody.substring(indexOf + tag.length(),
                      emailBody.length());

              emailBody = part1 + (String) dataHash.get(tag) + part2;
          }
      }
      return emailBody;
  }

My version is:

public String sendEmailUsingStringBuilder(String emailBody, Email email) {

        HashMap<String, String> dataHash = new HashMap<String, String>();
        dataHash.put("{{USER_EMAIL}}", email.getEmail());
        dataHash.put("{{USER_NAME}}", email.getName());
        dataHash.put("{{USER_PHONE}}", email.getPhone());
        dataHash.put("{{LOGIN_URL}}", email.getLoginUrl());

        StringBuilder strBuilder = new StringBuilder(emailBody);        
        for ( String tag : dataHash.keySet() ) {
            int tagIndex;
            while ((tagIndex = strBuilder.indexOf(tag)) != -1) {
                strBuilder.replace(tagIndex, tagIndex + tag.length(),
                        (String) dataHash.get(tag));
                tagIndex = strBuilder.indexOf(tag);
            }
        }
        return strBuilder.toString();
    }
\$\endgroup\$

migrated from stackoverflow.com Aug 27 '15 at 22:03

This question came from our site for professional and enthusiast programmers.

  • \$\begingroup\$ is your application multithreaded, if not using a hashtable is just wrong since its methods are synchronized, I would use a hashmap instead... \$\endgroup\$ – QuakeCore Aug 25 '15 at 11:22
  • 3
    \$\begingroup\$ strBuilder.indexOf() has also a method with two parameters (fromIndex) which could make it even faster. OTOH, I doubt that your future employer will be happy when he sees how you "outsource" the question. \$\endgroup\$ – Tilman Hausherr Aug 25 '15 at 11:28
  • 2
    \$\begingroup\$ Looks like @FahadShehzad and @Stephan have missed these lines in their solutions .toLowerCase(). BTW, original code looks fishy cause a while loop condition doesn't care about the case but indexOf does care. \$\endgroup\$ – Sergey Pauk Aug 25 '15 at 11:34
  • \$\begingroup\$ @SergeyPauk good catch ... i was only looking as his solution to improve \$\endgroup\$ – Stephan Aug 25 '15 at 11:39
4
\$\begingroup\$

The big picture

First of all, consider the possibility that this is a trick question. When sending bulk e-mail, the performance bottleneck is likely to be with the Mail Transfer Agent or the database query that fetches the contacts rather than with the text generation. I would raise a concern with the interviewer that perhaps we should gather some evidence before making a premature effort to optimize the wrong part of the process. Optimizing the code in this question (which takes about 2 seconds to run) will not make any noticeable difference to the time necessary to conduct the e-mail campaign.

Review

That said, if you had to optimize the text generation process, your changes would be a mild improvement. The HashMap is more lightweight than the synchronized Hashtable, and the StringBuilder does save a bit of copying, though not by as much as you think, since you are still making four global substitution passes through the entire emailBody.

Strictly speaking, both the original code and your version of it are buggy. Because string substitution is being done in multiple passes, it is possible that the output from one round of substitution could introduce a string that looks like a placeholder that ends up being inappropriately substituted in a subsequent round. (Another example of this class of bug.) Here, it's unlikely to be a problem unless someone decided to deliberately exploit the bug.

Alternative approach

If I really had to optimize this code, I would take a different approach entirely. The same emailBody template is likely to used for a million emails. Therefore, it would make sense to "pre-compile" the template…

Dear {{USER_NAME}},

According to our records, your phone number is {{USER_PHONE}} and 
your e-mail address is {{USER_EMAIL}}.  If this is incorrect, please 
go to {{LOGIN_URL}} and update your contact information.

… into code that looks like this:

public class C implements Template {
    public void write(Writer out, Map<String, String> params) throws IOException {
        out.write("Dear ");
        out.write(params.get("USER_NAME"));
        out.write("\n\nAccording to our records, your phone number is ");
        out.write(params.get("USER_PHONE"));
        out.write(" and \nyour e-mail address is ");
        out.write(params.get("USER_EMAIL"));
        out.write(".  If this is incorrect, please \ngo to ");
        out.write(params.get("LOGIN_URL"));
        out.write(" and update your contact information.\n");
        out.flush();
    }
}

The performance is likely to be unbeatable, since there is no longer any string substitution going on. This is, in fact, very similar to the code that a JSP engine generates, and you could try to integrate a JSP implementation instead of reinventing the wheel.

As a bonus, you can stack layers of writers. For example, you might pass it a subclass of FilterWriter that performs Format=Flowed line wrapping as per RFC 2646 to keep line lengths to a reasonable length as required by SMTP. You could also stack that directly on top of a Writer that feeds the text directly to an SMTP socket. Or, to obtain the resulting text as a string as in the original code, just use a StringWriter.

When I tried generating a million messages with a pre-compiled template, it completed the task in half the time of your code. If you include the time to compile the template into executable form, it's still better than break-even for one million messages. For a hundred million messages, it's about four times faster, compilation overhead included.

\$\endgroup\$
  • \$\begingroup\$ the template approach is by far the most efficient solution gg:) \$\endgroup\$ – Stephan Aug 31 '15 at 8:17
  • \$\begingroup\$ As @rolfl has pointed out, pre-processing the template is a good idea, but the particular way I chose to compile it into Java bytecode is overkill — too complicated for this simple application. \$\endgroup\$ – 200_success Sep 1 '15 at 8:12
3
\$\begingroup\$

you can try this:

public String sendEmailUsingStringBuilder(String emailBody, Email email) {

    HashMap<String, String> dataHash = new HashMap<String, String>();
    dataHash.put("{{user_email}}", email.getEmail());
    dataHash.put("{{user_name}}", email.getName());
    dataHash.put("{{user_phone}}", email.getPhone());
    dataHash.put("{{login_url}}", email.getLoginUrl());

    StringBuilder strBuilder = new StringBuilder(emailBody.toLowerCase());  
    StringBuilder strBuilderU = new StringBuilder(emailBody); 
    for (Map.Entry<String, String> entrySet : dataHash.entrySet()) {
        String key = entrySet.getKey();
        String value = entrySet.getValue();

        int tagIndex= 0;
        while ((tagIndex = strBuilder.indexOf(key, tagIndex)) != -1) {
            strBuilderU.replace(tagIndex, tagIndex + key.length(),
                    value);
            tagIndex += value.length()-tag.length();
        }
    }

    return strBuilderU.toString();
}
  1. you had a logical bug at tagIndex = strBuilder.indexOf(tag); (the last one) who has no purpose... you need to specify the start position for the while to continue like strBuilder.indexOf(key, tagIndex))

  2. you only need to get the value once String value = entrySet.getValue();

As @Burkhard well pointed out you need to think if this method needs synchronization or not.

As @Sergey Pauk observed i needed to make the match case insensitive

Solution 2

No need to create that Map for each email it should be a big improvement in speed but especially in memory consumtion:

private static final List<String> tags = Arrays.asList("{{user_email}}","{{user_name}}");


public String sendEmailUsingStringBuilder(String emailBody, Email email) {

    StringBuilder strBuilder = new StringBuilder(emailBody.toLowerCase());  
    StringBuilder strBuilderU = new StringBuilder(emailBody);
    for (int i = 0; i < tags.size(); i++) {
        String tag = tags.get(i);
        String value = null;
        switch(i){
            case 0:
                value = email.getEmail();
                break;
            case 1:
                value = email.getName();
                break;

        }

        int tagIndex= 0;
        while ((tagIndex = strBuilder.indexOf(tag, tagIndex)) != -1) {
            strBuilderU.replace(tagIndex, tagIndex + tag.length(),
                    value);
            tagIndex += value.length()-tag.length();
        }
    }

    return strBuilderU.toString();
}
\$\endgroup\$
  • 1
    \$\begingroup\$ I see a bug, you return the whole text in small letters. You have to modify the original emailBody as well. \$\endgroup\$ – Sergey Pauk Aug 25 '15 at 11:49
  • \$\begingroup\$ ur right.. i will fix it \$\endgroup\$ – Stephan Aug 25 '15 at 11:54
2
\$\begingroup\$

The following uses the faster HashMap, as Hashtable is synchronized, bearing also in a single thread a bit of overhead.

The capacity of the HashMap has been give a generous 10, as the size will be 4.

The greatest gain is to not use Strings. Here I use a conventional solution: Pattern for the place holders {{...}}. The replacing pattern uses the older class StringBuffer (synchronized too unfortunately), but StringBuilder is not possible. The StringBuffer got an initial capacity of one and a half.

private static final Pattern VAR_PATTERN =
        Pattern.compile("{{(USER_EMAIL|USER_NAME|USER_PHONE|LOGIN_URL)}}");


public String sendEmailUsingStringBuilder(String emailBody, Email email) {
    HashMap<String, String> vars = new HashMap<>(10);
    vars.put("USER_EMAIL", email.getEmail());
    vars.put("USER_NAME", email.getName());
    vars.put("USER_PHONE", email.getPhone());
    vars.put("LOGIN_URL", email.getLoginUrl());

    StringBuffer sb = new StringBuffer(emailBody.length() * 3 / 2);
    Matcher m = PATTERN .matcher(emailBody);
    while (m.find) {
        String var = m.group(1);
        String value = vars.get(var)
        m.appendReplacement(sb, value);
    }
    m.appendTail(sb);
    return sb.toString();
}

The speedup is due to the numerous String concatenations and substrings taken. A substring keeps the original string too. And concatenation is very slow.

My solution is not the fastest because of Pattern and StringBuffer but production quality.

\$\endgroup\$
0
\$\begingroup\$

If you need a concurrent implementation (multithread), you should use a ConcurrentHashMap.

If you do not need multithread, a HashMap is much faster.

Your version looks quite decent.

\$\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.