• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Efficient way to remove a pattern from an input String

 
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
author and iconoclast
Posts: 24207
46
Mac OS X Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Consider Paul's rocket mass heater.
reply
    Bookmark Topic Watch Topic
  • New Topic