I need a fast key substitution algorithm for java

Question

Given a string with replacement keys in it, how can I most efficiently replace these keys with runtime values, using Java? I need to do this often, fast, and on reasonably long strings (say, on average, 1-2kb). The form of the keys is my choice, since I'm providing the templates here too.

Here's an example (please don't get hung up on it being XML; I want to do this, if possible, cheaper than using XSL or DOM operations). I'd want to replace all @[^@]*?@ patterns in this with property values from bean properties, true Property properties, and some other sources. The key here is fast. Any ideas?

<?xml version="1.0" encoding="utf-8"?>

<envelope version="2.3">

  <delivery_instructions>

    <delivery_channel>
      <channel_type>@CHANNEL_TYPE@</channel_type>
    </delivery_channel>

    <delivery_envelope>
      <chan_delivery_envelope>
    <queue_name>@ADDRESS@</queue_name>
      </chan_delivery_envelope>
    </delivery_envelope>

  </delivery_instructions>

  <composition_instructions>
    <mime_part content_type="application/xml">
      <content><external_uri>@URI@</external_uri></content>
    </mime_part>
  </composition_instructions>

</envelope>

The naive implementation is to use String.replaceAll() but I can't help but think that's less than ideal. If I can avoid adding new third-party dependencies, so much the better.

Answer 1

The appendReplacement method in Matcher looks like it might be useful, although I can't vouch for its speed.

Here's the sample code from the Javadoc:

Pattern p = Pattern.compile("cat");
Matcher m = p.matcher("one cat two cats in the yard");
StringBuffer sb = new StringBuffer();
while (m.find()) {
    m.appendReplacement(sb, "dog");
}
m.appendTail(sb);
System.out.println(sb.toString());

EDIT: If this is as complicated as it gets, you could probably implement your own state machine fairly easily. You'd pretty much be doing what appendReplacement is already doing, although a specialized implementation might be faster.

Answer 2

I also have a non-regexp based substitution library, available here. I have not tested its speed, and it doesn't directly support the syntax in your example. But it would be easy to extend to support that syntax; see, for instance, this class.

Answer 3

You really want to write something custom so you can avoid processing the string more than once. I can't stress this enough - as most of the other solutions I see look like they are ignoring that problem.

Optionally turn the text into a stream. Read it char by char forwarding each char to an output string/stream until you see the @ then read to the next @ slurping out the key, substituting the key into the output: repeat until end of stream.

I know it's plain old brute for - but it's probably the best.

I'm assuming you have some reasonable assumption around '@' not just 'showing up' independant of your token keys in the input. :)

Answer 4

It's premature to leap to writing your own. I would start with the naive replace solution, and actually benchmark that. Then I would try a third-party templating solution. THEN I would take a stab at the custom stream version.

Until you get some hard numbers, how can you be sure it's worth the effort to optimize it?

Answer 5

Text processing is going to always be bounded if you dont shift your paradigm. I dont know how flexible your domain is, so not sure if this is applicable, but here goes:

try creating an index into where your text substitution is - this is especially good if the template doesnt change often, because it becomes part of the "compile" of the template, into a binary object that can take in the value required for the substitutions, and blit out the entire string as a byte array. This object can be cached/saved, and next time, resubstitute in the new value to use again. I.e., you save on parsing the document every time. (implementation is left as an exercise to the reader =D )

But please use a profiler to check whether this is actually the bottleneck that you say it is before embarking on writing a custom templating engine. The problem may actually be else where.

Answer 6

Take a look at a library that specializes in this, e.g., Apache Velocity. If nothing else, you can bet their implementation for this part of the logic is fast.

Answer 7

I wouldn't be so sure the accepted answer is faster than String.replaceAll(String,String). Here for your comparison is the implementation of String.replaceAll and the Matcher.replaceAll that is used under the covers. looks very similar to what the OP is looking for, and I'm guessing its probably more optomized than this simplistic solution.

public String replaceAll(String s, String s1)
    {
        return Pattern.compile(s).matcher(this).replaceAll(s1);
    }

public String replaceAll(String s)
    {
        reset();
        boolean flag = find();
        if(flag)
        {
            StringBuffer stringbuffer = new StringBuffer();
            boolean flag1;
            do
            {
                appendReplacement(stringbuffer, s);
                flag1 = find();
            } while(flag1);
            appendTail(stringbuffer);
            return stringbuffer.toString();
        } else
        {
            return text.toString();
        }
    }

Answer 8

... Chii is right. If this is a template that has to be run so many times that speed matters, find the index of your substitution tokens to be able to get to them directly without having to start at the beginning each time. Abstract the 'compilation' into an object with the nice properties, they should only need updating after a change to the template.

Answer 9

As others have said, appendReplacement() and appendTail() are the tools you need, but there's something you have watch out for. If the replacement string contains any dollar signs, the method will try to interpret them as capture-group references. If there are any backslashes (which are used to escape the dollars sing), it will either eat them or throw an exception.

If your replacement string is dynamically generated, you may not know in advance whether it will contain any dollar signs or backslashes. To prevent problems, you can append the replacement directly to the StringBuffer, like so:

Pattern p = Pattern.compile("@([^@]*?)@");
Matcher m = p.matcher(s);
StringBuffer sb = new StringBuffer();
while (m.find()) 
{
    m.appendReplacement("");
    sb.append(substitutionTable.lookupKey(m.group(1)));
}
m.appendTail(sb);

You still have to call appendReplacement() each time, because that's what keeps you in sync with the match position. But this trick avoids a lot of pointless processing, which could give you a noticeable performance boost as a bonus.

Answer 10

this is what I use, from the apache commons project http://commons.apache.org/lang/api/org/apache/commons/lang/text/StrSubstitutor.html