aspose file tools*
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
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: 24187
    
  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.
 
wood burning stoves
 
subject: Efficient way to remove a pattern from an input String