• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Optimizing string search & replace

 
Horaci Macias
Ranch Hand
Posts: 74
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm trying to optimize a peace of code that replaces a string in a larger string or stringbuffer. I'd read that Boyer-Moore was one of the best algorithms to do this, but I've found a Java implementation of B-M and if I make some tests, String.indexOf is faster than B-M! (not taking into account preprocess of internal tables) Preprocess time is not a problem because I've to replace the same pattern in 400 - 500 strings or stringbuffers...
My strings are 3k-5k length and the word I want to replace is 10-15 length. I'm using java 1.2.2. Could anyone give me some help ?
Is there any optimum length for B-M ? Where can I find the best algorithm to my replaces ?
Thanks in advance,
Horaci Macias
 
Brian Daniel
Greenhorn
Posts: 11
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you're using B-M on a char[], it is faster in my experience. Make sure you're not including transformation from a String to a char[] in your calculation - there's a System.arraycopy call in there along with memory allocation.
 
Ilja Preuss
author
Sheriff
Posts: 14112
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Did you think about trying one of the existing regular expression packages? I would think they are optimized for this kind of task.
 
Horaci Macias
Ranch Hand
Posts: 74
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I've found the problem... I had a wrong version of BM algorithm ;D Now I've tested with another one and it works fine.
Thanks for all,
Horaci Macias
 
Fabrizio Gianneschi
Ranch Hand
Posts: 70
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Horaci Macias:
I've found the problem... I had a wrong version of BM algorithm ;D Now I've tested with another one and it works fine.
Thanks for all,
Horaci Macias

I'm very interested on search&replace algorithms applied on the String class. Could you send me the java version of the BM you mentioned?
Thanks a lot
------------------
Fabrizio Gianneschi
Sun Certified Programmer for Java2 Platform
 
Horaci Macias
Ranch Hand
Posts: 74
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I've sent you the source code I used. It's a little modification of Roedy Green's code (look at http://mindprod.com if you want to see original version). Feel free to change it, copy it, or make everything you want with it, for any purpose but military. If you find a mistake, error or a better solution please tell me so.
This code is usefull for String search. I'm working for a class that uses that String search to make a replace of all occurrences, if you're interested I'll send you a draft, or if you want to collaborate (or somebody else) I think it would be a nice topic for this forum.
Regards,
Horaci Macias
[This message has been edited by Horaci Macias (edited December 21, 2001).]
 
Fabrizio Gianneschi
Ranch Hand
Posts: 70
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Horaci Macias:
I've sent you the source code I used.

Thanks a lot, Horaci!


This code is usefull for String search. I'm working for a class that uses that String search to make a replace of all occurrences, if you're interested I'll send you a draft, or if you want to collaborate (or somebody else) I think it would be a nice topic for this forum.


I've worked a lot on String replacements... now my interest are going down due to the new jdk1.4 replaceAll() method of the String class. I think that benefits gained by having a such method in the core classes are bigger than those generated by using an extremely performanced (but non standard) method.
However, I'm still interested. If the moderator agrees, I could post here my personal routine that does String replacements. Suggestions and improvements will be very appreciated.
regards,
------------------
Fabrizio Gianneschi
Sun Certified Programmer for Java2 Platform
 
I agree. Here's the link: http://aspose.com/file-tools
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic