String find and replace

[B M Tejaswi]

Am trying to write code which replaces the words in really large input string with the encoded word.The encoded pair is given. I would like you guys to give me some inputs as to how it can be done better(optimization). Below is the code

private String inputString_;
	private String actualMsg_;
	private String encodePairs_;
	private Map<String, String> tokenMap_ = null;
	
	/**
	 * Private Constructor to avoid creating empty object
	 */
	private MessageEncoderUtil() {}

	/**
	 * @param inputString
	 */
	public MessageEncoderUtil(String inputString) {
		setInputString_(inputString);
	}


	public String encodeMessage() {
		long startTime = System.currentTimeMillis();
		splitInputMsg();
		populateEncodePairMap();
		String outputString = actualMsg_;
		for(Map.Entry<String, String> entry : tokenMap_.entrySet()) {
			//outputString = outputString.replace(entry.getKey(), entry.getValue());
			outputString = replace(outputString, entry.getKey(), entry.getValue());
		}
		releaseResources();
		System.out.println("Encode Message :: "+(System.currentTimeMillis() - startTime));
		return outputString;
	}


	/**
	 * 
	 */
	private void populateEncodePairMap() {
		long startTime = System.currentTimeMillis();
		tokenMap_ = newHashMapInstance();
		//System.out.println("Encode pair :: "+encodePairs_);
//		String encodePairs[] = encodePairs_.split(Constants.ENCODE_PAIRS_DELIM);
		for(String pair : encodePairs_.split(Constants.ENCODE_PAIRS_DELIM)) {
			String pairs[] = pair.split(Constants.ENCODE_PAIR_DELIM);
			tokenMap_.put(pairs[0], pairs[1]);
		}
		System.out.println("populateEncodePairMap :: "+(System.currentTimeMillis() - startTime));
	}

	/**
	 * 
	 */
	private void releaseResources() {
		long startTime = System.currentTimeMillis();
		tokenMap_.clear();
		tokenMap_ = null;
		actualMsg_ = null;
		encodePairs_ = null;
		System.out.println("Release Resouces :: "+(System.currentTimeMillis() - startTime));
	}

	/**
	 * 
	 */
	private void splitInputMsg() {
		long startTime = System.currentTimeMillis();
		String temp[] = inputString_.split(Constants.IN_MSG_ENC_MSG_DELIMITER);
		actualMsg_ = temp[0];
		encodePairs_ = temp[1].trim();
		System.out.println("split :: "+(System.currentTimeMillis() - startTime));
	}
	
	 private String replace (String source, String os, String ns) {
		 long startTime = System.currentTimeMillis();
	        if (source == null) {
	            return null;
	        }
	        int i = 0;
	        // Make sure that oldString appears at least once before doing any processing.
	        if ((i = source.indexOf(os, i)) >= 0) {
	            // Use char []'s, as they are more efficient to deal with.
	            char[] sourceArray = source.toCharArray();
	            char[] nsArray = ns.toCharArray();
	            int oLength = os.length();
	            StringBuilder buf = new StringBuilder (sourceArray.length);
	            buf.append (sourceArray, 0, i).append(nsArray);
	            i += oLength;
	            int j = i;
	            // Replace all remaining instances of oldString with newString.
	            while ((i = source.indexOf(os, i)) > 0) {
	                buf.append (sourceArray, j, i - j).append(nsArray);
	                i += oLength;
	                j = i;
	            }
	            buf.append (sourceArray, j, sourceArray.length - j);
	            source = buf.toString();
	            buf.setLength (0);
	        }
	        System.out.println("replace :: "+(System.currentTimeMillis() - startTime));
	        return source;
	  }

Input string is :
This component is standard compliant|3rdparty api fails===component=C|standard=S|3rdparty=3|compliant=I

output :
This C is S I|3 api fails

string after '===' is the encoding pairs from which the LHS of '===' is encoded.

Any suggestions?

[Jesper de Jong]

Can you isolate the problem? It's a lot of work to try to understand all the code you posted and things are missing, such as your Constants class, which would be especially interesting since you're passing values that are defined in there to String.split(...).

Can you give a concrete example of where String.split(...) doesn't do what you expected? What are the exact inputs and outputs?

[B M Tejaswi]

Thanks for the reply.
AM able to achieve the expected output given the input..the only problem is how it can be optimized/how it can be further enhanced so that the runtime might reduce given a very long input string.
Below is the code snippet for Constants class:

public static final String IN_MSG_ENC_MSG_DELIMITER = "===";
	public static final String MESSAGE_DELIM = "\\|";
	public static final String ENCODE_PAIR_DELIM = "=";
	
	public static final String ERROR_INPUT = "Invalid input message";
	public static final String ENCODE_PAIRS_DELIM = "\\|";

[Jeff Verdegan]

Tejaswi Bm wrote:Thanks for the reply.
AM able to achieve the expected output given the input..the only problem is how it can be optimized/how it can be further enhanced so that the runtime might reduce given a very long input string.

Have you measured the performance and found that it doesn't meet your already-defined, specific requirements? If not, then there's no point in trying to optimize it. You'd just be guessing at what might be wrong and trying to make it "better" without having an actual target.

Having said that, one thing does pop to mind. I'm not going to read your code, but if you're using String.split() or String.replaceAll(), you're compiling the regex every time. If you're reusing the same regex then you might get better performance by calling Pattern.compile() once, reusing the same Pattern each time, and then creating a Matcher for each input String and calling its methods as needed.

[B M Tejaswi]

Thanks Jeff!!
But i dont think my code is optimized and can handle really huge input string. I have used a HashMap to store the tokens, but i feel the same can be achieved with 'something else'. I am not aware of that 'something else'. So if you could point me in right direction??

[Paul Clapham]

My first thought would be to throw out your replace() method and simply use the replace() method which is already built into the String class.

Quite often people will write their own code rather than use built-in methods, disregarding the fact that the built-in methods were written by people with more experience and have been improved over the years. Often that's a mistake. At any rate you now ought to compare your code to the built-in code and see which is more "optimized" (by which it looks like you mean runs faster, rather than uses less memory or something else).

[Jeff Verdegan]

Tejaswi Bm wrote:Thanks Jeff!!
But i dont think my code is optimized and can handle really huge input string. I have used a HashMap to store the tokens, but i feel the same can be achieved with 'something else'. I am not aware of that 'something else'.

Why? In what way does HashMap not meet your needs, or in what way does it seem inappropriate to you? There may be something better, but I can't recommend anything without a clear picture of how HashMap is falling short.

If you're associating a key with a value, Map is the way to go. If you don't care about the iteration order of the keys, values, or pairings, then HashMap is the default workhorse Map implementation to choose.

[fred rosenberger]

Tejaswi Bm wrote:I don't think my code is optimized and can handle really huge input string.

without actual evidence - actual measurements of how long things take - what you "think" is irrelevant. this kind of this has been discussed ad nauseam in the performance forum (where this thread really belongs).

Never try and do optimization without measuring your performance. You will ALWAYS be served better writing clean, readable, understandable code first. OK...second. FIRST you should define what your performance requirements are. Then write your clean, readable, understandable code. Then test it to see if it meets your requirements.

If it does - you're done.

If not, use a profiler to find out exactly where it is slow, and spend your time optimizing that.

[William Brogden]

Personally I would read the input String as a stream, parsing out words and writing to an output stream - for each word, do a hash table lookup to see if it has a replacement - if so substitute in the output stream. Completely insensitive to problems of string replace in a really large string in memory.

Things to watch out for - case differences, word separators.

Bill

[Winston Gutkowski]

Tejaswi Bm wrote:But i dont think my code is optimized and can handle really huge input string. I have used a HashMap to store the tokens, but i feel the same can be achieved with 'something else'. I am not aware of that 'something else'. So if you could point me in right direction??

Well, like the others I suspect you're obsessing about something which you don't yet know is a problem.

However, if you're absolutely bound and determined to research this problem as an exercise. I'd say they are a few things you need to concentrate on:
1. Searching: I'm not sure about how regexes (ie, Matcher.find()) work, but I do know that indexOf() is sometimes not an optimal search because it's sequential. For more general searches you may want to look at something like the Boyer-Moore-Horspool algorithm, but in your case (searching for a delimiter), it's almost certainly overkill, and I would say indexOf() should be be just fine.

2. Storage of your "token" information: A HashMap sounds perfectly reasonable for your tokens and replacements, but I'd say you don't want to split() the String you're searching.

My advice, starting from the beginning of the String:
a. Find a delimiter.
b. Check if the substring before it matches any of your tokens to be replaced. If it does, copy the replacement token to the output; otherwise just copy the substring.
c. Copy the delimiter to the output.
And repeat that with the substring starting at the character after the delimiter until there are no more delimiters to find. Chances are that you'll still have a "last token" to process, in which case do check (b) on it.

In your case you may have a little bit more work to do, but the basic pattern is the same, and it will run in O(n) time.

Winston

[B M Tejaswi]

With the suggestions that i have got from the learned ones in this forum, i tried to alter the code and have come up with the following code :

/**
	 * Method encodeMessage.
	 * @return String
	 */
	public String encodeMessage() {
		actualMsg_ = inputString_;
		if(inputString_.contains(IN_MSG_ENC_MSG_DELIMITER)) {
			splitInputMsg();
			populateEncodePairMap();
		}
		populateNumericTokenMap();
		String outputString = null;
		StringBuilder sb = new StringBuilder();
		StringTokenizer stringTokenizer = new StringTokenizer(actualMsg_);
		while(stringTokenizer.hasMoreTokens()) {
			String word = stringTokenizer.nextToken();
			if(word.contains(MESSAGE_DELIM)) {
				replaceEndWord(sb, word);
			}
			else if(isNumeric(word)) {
				replaceNumber(sb, word);
			} else {
				replaceAlphaWord(sb, word);
			}
			sb.append(' ');
		}
		if(sb.length() == 0) {
			outputString = "";
		} else {
			outputString = sb.substring(0, sb.length());
		}

		releaseResources();
		return outputString;
	}

	/**
	 * @param sb 
	 * @param inputWord String
	 */
	private void replaceEndWord(StringBuilder sb, String inputWord) {
		String words[] = inputWord.split(END_OF_MSG_DELIM);
		if(words.length == 2) {
			if(null != words[0] && !words[0].isEmpty()) {
				if(isNumeric(words[0])) {
					replaceNumber(sb, words[0]);
				}else {
					replaceAlphaWord(sb, words[0]);
				}
			}
			sb.append(MESSAGE_DELIM);
			if(null != words[1] && !words[1].isEmpty()) {
				if(isNumeric(words[1])) {
					replaceNumber(sb, words[1]);
				}else {
					replaceAlphaWord(sb, words[1]);
				}
			}
		} else if(words.length > 0) {
			if(null != words[0] && !words[0].isEmpty()) {
				if(isNumeric(words[0])) {
					replaceNumber(sb, words[0]);
				}else {
					replaceAlphaWord(sb, words[0]);
				}
			}
			sb.append(MESSAGE_DELIM);
		} else {
			sb.append(inputWord);
		}
	}

	/**
	 * @param sb 
	 * @param outputString
	 */
	private void replaceAlphaWord(StringBuilder sb, String inputWord) {
		Pattern patern = null;
		Matcher matcher = null;
		String value = null;
		if(null != (value = tokenMap_.get(inputWord))) {
			patern = Pattern.compile(inputWord);
			matcher = patern.matcher(inputWord);
			if(matcher.matches()) {
				inputWord = replace(inputWord, inputWord, value);
			}
		}
		sb.append(inputWord);
	}

	/**
	 * @param sb 
	 * @param outputString
	 */
	private void replaceNumber(StringBuilder sb, String inputNumber) {
		for(Map.Entry<Integer, String> entry : numericTokenMap_.entrySet()) {
			inputNumber = replace(inputNumber, Integer.toString(entry.getKey()), entry.getValue());
		}
		sb.append(inputNumber);
	}

	/**
	 * Creates a map for storing numeric tokens.
	 */
	private void populateNumericTokenMap() {
		numericTokenMap_.put(0, ")");
		numericTokenMap_.put(1, "!");
		numericTokenMap_.put(2, "@");
		numericTokenMap_.put(3, "#");
		numericTokenMap_.put(4, "$");
		numericTokenMap_.put(5, "%");
		numericTokenMap_.put(6, "^");
		numericTokenMap_.put(7, "&");
		numericTokenMap_.put(8, "*");
		numericTokenMap_.put(9, "(");
	}

	/**
	 * Creates map for storing encode pairs.
	 */
	private void populateEncodePairMap() {
		if(null != encodePairs_) {
			for(String pair : encodePairs_.split(ENCODE_PAIRS_DELIM)) {
				String pairs[] = pair.split(ENCODE_PAIR_DELIM);
				if(!pairs[0].isEmpty() && null != pairs[0] && null == tokenMap_.get(pairs[0])) {
					tokenMap_.put(pairs[0], pairs[1]);
				}
			}
		}
	}

	/**
	 * Releases all the resources used by the code.
	 */
	private void releaseResources() {
		tokenMap_.clear();
		tokenMap_ = null;

		actualMsg_ = null;
		encodePairs_ = null;

		numericTokenMap_.clear();
		numericTokenMap_ = null;
	}

	/**
	 * Splits the input string based on '==='.
	 */
	private void splitInputMsg() {
		String temp[] = inputString_.split(IN_MSG_ENC_MSG_DELIMITER);
		switch (temp.length) {
		case 1:
			actualMsg_ = temp[0];
			break;
		case 2:
			actualMsg_ = temp[0];
			encodePairs_ = temp[1].trim();
			break;
			
		default:
			actualMsg_ = "";
			encodePairs_ = "";
			break;
		}
	}

	/**
	 * Method replace.
	 * @param source String
	 * @param os String
	 * @param ns String
	 * @return String
	 */
	private String replace (String source, String os, String ns) {
		if (source == null) {
			return null;
		}
		int i = 0;
		if ((i = source.indexOf(os, i)) >= 0 /*&& !isNumeric(source)*/) {
			// Use char []'s, as they are more efficient to deal with.
			char[] sourceArray = source.toCharArray();
			char[] nsArray = ns.toCharArray();
			int oLength = os.length();
			StringBuilder buf = new StringBuilder (sourceArray.length);
			buf.append (sourceArray, 0, i).append(nsArray);
			i += oLength;
			int j = i;
			// Replace all remaining instances of oldString with newString.
			while ((i = source.indexOf(os, i)) > 0) {
				buf.append (sourceArray, j, i - j).append(nsArray);
				i += oLength;
				j = i;
			}
			buf.append (sourceArray, j, sourceArray.length - j);
			source = buf.toString();
			buf.setLength (0);
		}
		return source;
	}

	/**
	 * Check if the input string is numeric.
	 * @param os 
	 * @return boolean
	 */
	private boolean isNumeric(String os) {
		NumberFormat formatter = NumberFormat.getInstance();
		ParsePosition pos = new ParsePosition(0);
		formatter.parse(os, pos);
		return os.length() == pos.getIndex();
	}

I have performed some test and below are the reults-
Number of input words in string = 120000
Number of total encoding pairs = 4
Number of encoded words in output = 20000
Number of iterations = 1000
Total time in millis = 1009033
Avg time in millis = 1009

but am not happy with the results..I want an avg time of around 600 millis..please help:(

[Winston Gutkowski]

Tejaswi Bm wrote:With the suggestions that i have got from the learned ones in this forum, i tried to alter the code
...
but am not happy with the results..I want an avg time of around 600 millis..please help:(

Well first, your coding style could do with some improvement: Specifically, don't use '_' in field names. It may be great for Python, but it looks awful to most Java programmers. Also, StringTokenizer is a legacy class, and its use is discouraged. You can do exactly the same thing with a Scanner; although either one will be quite a bit slower than the technique I suggested in my previous post.

It seems to me that you're overthinking this thing by a mile. Substitution is very straightforward:
1. Find a token.
2. Check if it's in your HashMap:

if it is, add its substitute to the output.

3. If it isn't, check if it's numeric:

if it is, add its "encrypted" version to the output.

4. Otherwise, add it to the output as is.

It also appears that you're replacing all your delimiters with spaces. That's fine, but I didn't see any suggestion that that's what you wanted.

My advice: Write down ALL the rules for your "replace" in English before you write another line of code.

Also: have a look at String.substring(). In general, its the fastest way of returning a substring (or eliminating part of a String) because it doesn't involve any copying of the internal character array.

I'd also suggest that a numericTokenMap is overkill, and probably a lot slower than simply substituting numeric characters from an array, eg:

private char[] encryptedDigits = ")!@£$%^&*(".toCharArray();

particularly if you're only interested in the characters '0' to '9' (which is NOT the same thing as a 'numeric' character).

HIH

Winston

[William Brogden]

My advice: Write down ALL the rules for your "replace" in English before you write another line of code.

++ good advice

Be sure to include rules for handling recognizing words with differences in case/CASE/Case ...

Your method is slow because it involves creation of a number of objects and tries to start with the full string in memory - for speed go with stream processing as Winston and I suggested.

Bill

[B M Tejaswi]

But i cannot read the input as stream since i need to prepare the encoding pairs..so i have to read the entire input string and then split based on delimiter!correct me if am wrong..if stream can be tokenized then please do guide me with the code.

[William Brogden]

In your OP, you said the "encoding pair" is given. Where does a "encoding pair" come from?

The Java io package has the StringReader class which will let you read a String as a stream of characters.

Have you followed Winston's advice to write down ALL the rules of your desired "replace" function?

Bill

[B M Tejaswi]

Encoding pair is given as part of input string. Encoding pair is separated by "===" in the input string.

[Winston Gutkowski]

B M Tejaswi wrote:Encoding pair is given as part of input string. Encoding pair is separated by "===" in the input string.

Right, so there is some sort of format to your input that your program will have to deal with. This is all part of the "rules" that I mentioned above.

Have you written them ALL down?

Winston