This week's book giveaway is in the OO, Patterns, UML and Refactoring forum.
We're giving away four copies of Refactoring for Software Design Smells: Managing Technical Debt and have Girish Suryanarayana, Ganesh Samarthyam & Tushar Sharma 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


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.
 
I’ve looked at a lot of different solutions, and in my humble opinion Aspose is the way to go. Here’s the link: http://aspose.com
 
subject: Efficient way to remove a pattern from an input String
 
It's not a secret anymore!