Re: Fastest way to replace characters in string
Re: Fastest way to replace characters in string
- Subject: Re: Fastest way to replace characters in string
- From: Marcel Weiher <email@hidden>
- Date: Thu, 22 Aug 2013 13:54:03 +0200
Hi Diederik,
On Aug 22, 2013, at 1:44 , Diederik Meijer | Ten Horses <email@hidden> wrote:
> The content is quite large, about 1MB, it is the full text of a law.
Hmm…that isn’t really that large, we have GHz computing buzz-saws!
> The web service returns the list lightning fast, but in order to get the count number added to each of the >300 articles html <h4> header, I am looping through the list and call NSString's stringByReplacingOccurancesOfString:withString: on each item.
>
> There must be a more efficient way to update the html string loaded from the local file, obviously doing more than 300 of these replace actions is slow and inefficient.
The reason this is slow and inefficient is that you are making repeated (small) changes to a (somewhat) large data set, so your running time is n*m, where n is the size of the string and m is the number of substitutions. Probably the simplest way of handling this within the current setup is to aggregate the result incrementally, rather than mutating the original repeatedly, which makes this process linear in n and roughly independent of the number of substitutions. For example, as a rough sketch consider the following:
—— snip ——
NSString *addNumbers( NSString *inhtml ) {
NSMutableString *target=[NSMutableString string];
int inlen=[inhtml length];
int startPos=0;
int done=NO;
int currentNo=1;
do {
NSRange r=[inhtml rangeOfString:@"<h4>" options:NSCaseInsensitiveSearch range:NSMakeRange(startPos,inlen-
if ( r.length > 0 ) {
int curPos=r.location;
[target appendString:[inhtml substringWithRange:NSMakeRange(startPos,curPos-startPos)]];
[target appendFormat:@"<h4>%d ",currentNo++];
startPos=curPos+4;
} else {
done=YES;
}
} while (!done);
[target appendString:[inhtml substringWithRange:NSMakeRange(startPos,inlen-startPos)]];
return target;
}
—— snip ——
This processes a 2.8MB sample file with upwards of 30K substitutions in 70ms on my MacBook Pro, or pretty much exactly 25 ms per MB. On your iPad 3, my guess is that you’ll get it processed in around 1/4 second or so.
If you need to go faster, switching to byte processing instead of string processing (using NSData and C string processing functions) gets you another factor of 5, for 5ms per MB on my MacBook Pro or around 1/20 second on an iPad.
Cheers,
Marcel
_______________________________________________
Cocoa-dev mailing list (email@hidden)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden