This week's book giveaway is in the Big Data forum.
We're giving away four copies of Elasticsearch in Action and have Radu Gheorghe & Matthew Lee Hinman on-line!
See this thread for details.
The moose likes Performance and the fly likes Efficient way to remove a pattern from an input String Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Elasticsearch in Action this week in the Big Data forum!
JavaRanch » Java Forums » Java » Performance
Bookmark "Efficient way to remove a pattern from an input String" Watch "Efficient way to remove a pattern from an input String" New topic
Author

Efficient way to remove a pattern from an input String

Shine Sreedharan
Greenhorn

Joined: Feb 23, 2011
Posts: 2
Hi,

In my program I am using the below given while loop to remove all the escape sequences in a String. When I tested my app for performance, this loop came out as a bottle neck by clocking 1500 ms execution time for a String of length 70,000 characters. There were close to 7500 loops executed.



Can anyone suggest a better performing code to achieve this?

Thanks,
Shine.
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24189
    
  34

Hi,

Welcome to JavaRanch!

This is slow because deleting a character will involve copying all the subsequent characters down one place; in the limit of a large number of removed characters, the number of copy operations will be proportional to the square of the number of characters -- i.e., tending towards 70,000 * 70,000 = 5x10^9.

A much faster algorithm would be to create a second StringBuilder, then loop over all the chars in the first one, copying only the valid characters into the new buffer. This algorithm examines and copies each character only once.


[Jess in Action][AskingGoodQuestions]
Shine Sreedharan
Greenhorn

Joined: Feb 23, 2011
Posts: 2
Hi,

Thank you very much for your quick reply. That really helped.

I have changed the code to



Now the execution time has come down from 1500 ms to just 47 ms.

Thanks again for your help,
Shine.
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Efficient way to remove a pattern from an input String