aspose file tools*
The moose likes Performance and the fly likes Optimizing string search & replace Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Performance
Bookmark "Optimizing string search & replace" Watch "Optimizing string search & replace" New topic
Author

Optimizing string search & replace

Horaci Macias
Ranch Hand

Joined: Nov 08, 2001
Posts: 74
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

Joined: Oct 30, 2001
Posts: 11
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

Joined: Jul 11, 2001
Posts: 14112
Did you think about trying one of the existing regular expression packages? I would think they are optimized for this kind of task.


The soul is dyed the color of its thoughts. Think only on those things that are in line with your principles and can bear the light of day. The content of your character is your choice. Day by day, what you do is who you become. Your integrity is your destiny - it is the light that guides your way. - Heraclitus
Horaci Macias
Ranch Hand

Joined: Nov 08, 2001
Posts: 74
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

Joined: Nov 29, 2001
Posts: 70
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


Fabrizio Gianneschi<br />SCPJ2, SCWCD, SCBCD
Horaci Macias
Ranch Hand

Joined: Nov 08, 2001
Posts: 74
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

Joined: Nov 29, 2001
Posts: 70
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
 
Consider Paul's rocket mass heater.
 
subject: Optimizing string search & replace