yeah, i agree. we could do that. but that's not the big picture.
the big picture is that only one alloc is done in my case. it looks like the commons replace is going to do more than one in many cases.
Gili wrote:
Putting a if (buffer==null) inside the loop seems like a waste and the for() loop conditions look very ugly :) Reminds me back of C++ days where everyone was packing everything into one big for() statement.
Anyway, I think it would actually be cheaper to separate the for loop into two. The first block checks whether there is at least one match and creates the buffer and the second block hits all remaining matches (no need to check the buffer for null over and over again). This would also enable you to move the check for buffer==null at the end of your method up to the top (first block) where you do this check.
Gili
Jonathan Locke wrote:
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
------------------------------------------------------- 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
