okay, my entry is this (checking it in now...)
/**
* Replace all occurrences of one string replaceWith another string
*
* @param s
* The string to process
* @param searchFor
* The value to search for
* @param replaceWith
* The value to searchFor replaceWith
* @return The resulting string with searchFor replaced with replaceWith
*/
public static String replaceAll(final String s, final String searchFor, final String replaceWith)
{
// Check arguments
if (s == null)
{
throw new IllegalArgumentException("Cannot pass null target string to replaceAll");
}
if (searchFor == null)
{
throw new IllegalArgumentException("Cannot pass null searchFor string to replaceAll");
}
if (replaceWith == null)
{
throw new IllegalArgumentException("Cannot pass null replaceWith string to replaceAll");
}
// Go through the string
StringBuffer buffer = null;
final int searchForLength = searchFor.length();
int pos = 0;
for (int matchIndex; -1 != (matchIndex = s.indexOf(searchFor, pos)); pos = matchIndex
+ searchForLength)
{
// Start a replace operation?
if (buffer == null)
{
// Determine a buffer size so we don't need to
// reallocate if there's just one replacement.
int size = s.length();
final int replaceWithLength = replaceWith.length();
if (replaceWithLength > searchForLength)
{
size += (replaceWithLength - searchForLength);
}
buffer = new StringBuffer(size + 16);
}
// Found a match. Append up to the match
buffer.append(s.substring(pos, matchIndex)); // Add replaceWith
buffer.append(replaceWith);
}// If no replace was required
if (buffer == null)
{
// return original string
return s;
}
else
{
// add tail of s
buffer.append(s.substring(pos));
// return processed buffer
return buffer.toString();
}
}
Jonathan Locke wrote:
i also think our replaceAll method should throw an illegal argument exception when asked to replace in a null string... i'm going to make that change too.
Jonathan Locke wrote:
as long as we're racing algorithms, let me have one more crack at it.
the commons code is a bit obtuse to me and i can't see how it would outperform my code with a couple of tweaks (famous last words).
will check in a change in a second...
jon
Christopher Turner wrote:
Hi all,
I've been having a play with alternative implementations of the replaceAll method. The results are very interesting. I tried six different implementations:
- java.lang.String.replaceAll
- Jon's algorithm from the Wicket code
- My own alternative algorithm
- The algorithm used by jakarta-commons
- 2 other algorithms that I found on the Internet which claimed to be the fastest!
Conclusions:
Each algorithm had very different performance characterisics depending on what sort of replace you are trying to do! The test data variations included different length source strings, different numbers of replacement matches, single character replacements and substring replacements. I also tested our most common use of replaceAll - replaceAll("&", "&"). Comments on each:
java.lang.String.replaceAll - The only certantity from my results was that this always performed slower than all the others. In fact, the variation was between 2.9 and 4.7 times slower than the fastest algorithm for each test
Jon's wicket algorithm - Performed very consistently, but came out 3rd or 4th fastest in every test except for the ones where there were no replacements, where it came a narrow second
My alternative algorithm - Was fastest at replacing a single character with a string (e.g. "&" with "&") when there were many occurences of the single character. However it was useless at all the other tests, being almost as slow as java.lang.String.replaceAll in some cases
Jakarta-commons algorithm - Performed consistently well and was always the fastest or second fastest algorithm in all tests. In particular it was the fastest for our most common replaceAll call and for the case where there were no replaces
Internet algorithm 1 - Useless, was 3rd, 4th or 5th fastest in all tests and often by a significant margin
Internet algorithm 2 - Performed consistently well and was always the fastest or second fastest algorithm in all tests except those where there were no replacements when it cam 4th. However, it was beaten by the jakarta-commons algorithm for our most common replaceAll call
Recommendation: We change all calls from java.lang.String.replaceAll() to wicket.util.string.Strings.replaceAll, but we change the implementation of this method to use the jakarta-commons algorithm:
public static String replaceAll(final String s, final String searchFor, final String replaceWith) {
if ( s != null ) {
try {
final StringBuffer stringBuffer = new StringBuffer(s);
int index = s.length();
final int offset = searchFor.length();
while ( (index = s.lastIndexOf(searchFor, index - 1)) > -1 ) {
stringBuffer.replace(index, index + offset, replaceWith);
}
return stringBuffer.toString(); } catch (StringIndexOutOfBoundsException e) { return s; } } return null; }
If anyone would like the source code to explore the algorithms or validate the tests then please let me know.
Regards,
Chris
------------------------------------------------------- SF email is sponsored by - The IT Product Guide Read honest & candid reviews on hundreds of IT Products from real users. Discover which products truly live up to the hype. Start reading now. http://ads.osdn.com/?ad_id=6595&alloc_id=14396&op=click _______________________________________________ Wicket-develop mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/wicket-develop
------------------------------------------------------- SF email is sponsored by - The IT Product Guide Read honest & candid reviews on hundreds of IT Products from real users. Discover which products truly live up to the hype. Start reading now. http://ads.osdn.com/?ad_id=6595&alloc_id=14396&op=click _______________________________________________ Wicket-develop mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/wicket-develop
------------------------------------------------------- SF email is sponsored by - The IT Product Guide Read honest & candid reviews on hundreds of IT Products from real users. Discover which products truly live up to the hype. Start reading now. http://ads.osdn.com/?ad_id=6595&alloc_id=14396&op=click _______________________________________________ Wicket-develop mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/wicket-develop
