Win a copy of Think Java: How to Think Like a Computer Scientist this week in the Java in General forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Efficient way to remove a pattern from an input String

 
Shine Sreedharan
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 24211
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Shine Sreedharan
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic