{"id":691,"date":"2012-03-30T06:56:33","date_gmt":"2012-03-30T10:56:33","guid":{"rendered":"http:\/\/bruji.com\/articles\/?p=691"},"modified":"2012-03-30T06:56:33","modified_gmt":"2012-03-30T10:56:33","slug":"sorting-titles-without-articles-fast","status":"publish","type":"post","link":"https:\/\/bruji.com\/blog\/2012\/03\/30\/sorting-titles-without-articles-fast\/","title":{"rendered":"Sorting Titles Without Articles Fast"},"content":{"rendered":"

Mark Dalrymple wrote an interesting article about the speed difference between isEqual<\/em>: and isEqualToString<\/em>:<\/a> methods. Choosing between these methods is a small decision programmers make everyday. The article should reaffirm readers beliefs that concentrating on readability is more important than performance.<\/p>\n

The short of it is that he runs the methods 10 million times to show results in a speed difference of 3%<\/strong> to 7%<\/strong>. About .0000000005<\/strong> seconds gained for every call of isEqualToString<\/em> method over isEqual<\/em>. Most of my code would use those methods at most a few tens of times when a user makes a choice in the Pedias and five billionths of a second is certainly not a difference anyone can notice. In fact the difference in results is low enough that they become statistically meaningless. Trying to unravel the implications of compiler optimizations as well as the testing environment is more complex and time consuming than the numbers justify.<\/p>\n

However the article did get me thinking about an old function I optimized a few year back. The Pedias include a bit of code for sorting that ignores the article at the beginning of a title. When sorting a large number of entries this code can be run in the vicinity of a million times. This fits my number one rule about optimization: loops are the place where optimization makes the most difference.<\/p>\n

The original code used the standard NSString hasPrefix<\/em>: method to do the comparison.<\/p>\n

\r\nif ([aString hasPrefix:@"\\""])\r\n    aString = [aString substringFromIndex:1];\r\n\r\nif ([aString hasPrefix:@"The "])\r\n    return [aString substringFromIndex:4];\r\nelse if ([aString hasPrefix:@"A "])\r\n    return [aString substringFromIndex:2];\r\nelse if ([aString hasPrefix:@"An "])\r\n    return [aString substringFromIndex:3];\r\nreturn aString;\r\n<\/pre>\n
On testing collections with 20,000 items the sort felt sluggish. Especially when compared to a sorting that did not take the article into account, hence I knew the article comparison could do with some optimization. I changed the code to do the comparison based on each individual character. (This all started with a much longer version of the code that ignores articles in other languages that take into account a lot more than the possible 3 articles in English.) By looking at the first letter and making chain decisions I thought I would save a lot of time.<\/p>\n
\r\nNSUInteger length = [aString length];\r\nif (length) {\r\n\tunichar aChar = [aString characterAtIndex:0];\r\n\r\n\tif (aChar == '\\"' && length > 1) {\r\n\t\taString = [aString substringFromIndex:1];\r\n\t\taChar = [aString characterAtIndex:0];\r\n\t\tlength--;\r\n\t}\r\n\r\n\tif (aChar == 'T' && length > 4 && [aString characterAtIndex:1] == 'h' && [aString characterAtIndex:2] == 'e' && [aString characterAtIndex:3] == ' ')\r\n\t\taString = [aString substringFromIndex:4];\r\n\telse if (aChar == 'A') {\r\n\t\tif (length > 3) {\r\n            aChar = [aString characterAtIndex:1];\r\n\t\t    if (aChar == ' ')\r\n\t\t\t     aString = [aString substringFromIndex:2];\r\n\t\t    else if (aChar == 'n' && [aString characterAtIndex:2] == ' ')\r\n\t\t\t     aString = [aString substringFromIndex:3];\r\n\t\t    }\r\n\t    }\r\n    }\r\nreturn aString;\r\n<\/pre>\n
With the new code the sorting was blazing fast in testing and it’s been great for actual users ever since. My interest peaked by Mark Dalrymple article and his timing code convenient and thoughtfully in a gist<\/a> I ran my two methods in it to finally get some raw numbers.<\/p>\n
Title “King Kong”:
\nTime for characterAtIndex: 0.300036<\/strong>
\nTime for hasPrefix: 3.165767<\/strong><\/p>\n
Title “The Lord of the Rings”:
\nTime for characterAtIndex: 3.218064<\/strong>
\nTime for hasPrefix: 4.198877<\/strong><\/p>\n
Right off you can see the new code (which is really 5 years old) is 10x faster than the old version when no article is present. For the string with “The<\/em>” the code is much slower in both cases. But this can quickly be attributed to the actual “substringFromIndex:<\/em>” method that both versions need to return the string to be sorted. Removing this operation, since we are only interested in the comparison timing, gives new numbers.<\/p>\n
Title “The Lord of the Rings” with an assignment call instead of substringFromIndex.
\nTime for characterAtIndex: 0.665993<\/strong>
\nTime for hasPrefix: 1.568902<\/strong><\/p>\n
As you can see the difference is still 0.98 seconds between them but the time it takes to do 10 million substringFromIndex: calls has been stripped, better reflecting that in the case of “The<\/em>” article being present the new call is 2x as fast. A title with “An<\/em>” of course is even faster as the original method does not test for just the presence of “A<\/em>” first but the entire “A<\/em> ” and “An<\/em> ” prefix.<\/p>\n
So sometimes it does make sense to write your own versions of the built-in functions and lengthen your code when you can use the internal information in the algorithm to achieve more specific results. However, keep in mind it’s not really worth the time unless making millions of calls to that function.<\/p>\n
As a side note, it’s faster in 32 bit than in their 64 bit counterparts. A meaningless statistic since the code is so basic that there is no advantage or disadvantage in the code itself that would affect the timing depending on the architecture.<\/p>\n
For programmers out there looking to ignore articles when sorting, the above code will do the trick nicely when wrapped in the below category method of NSString and used from a NSSortDescriptor:<\/p>\n
\r\n@implementation NSString (NSStringExtensions)\r\n\r\n- (NSComparisonResult)ignoringArticleCompare:(NSString *)anotherString {\r\n\tNSString *string1 = removeArticleFromString(self);\r\n\tNSString *string2 = removeArticleFromString(anotherString);\r\n\r\n\treturn [string1 compare:string2 options:NSCaseInsensitiveSearch | NSNumericSearch range:NSMakeRange(0,[string1 length]) locale:[NSLocale currentLocale]];\r\n}\r\n\r\n@end\r\n<\/pre>\n
Here is the code for also ignoring articles in English, French, German, Italian and Spanish:<\/p>\n
\r\nstatic inline NSString* removeForeignArticleFromString(NSString *aString) {\r\n\r\n\t\/\/ A faster version than the original below\r\n\tNSUInteger length = [aString length];\r\n\tif (length) {\r\n\t\tunichar aChar = [aString characterAtIndex:0];\r\n\r\n\t\t\/\/ ", The, A, An, El, Ein, Eine, Einen, Einem, Einer, Eines, Un, Una, Une, Des, Der, Dem, Den, Die, Das, L', Lo, La, Le, Les, Los, Las, Il\r\n\t\tif (aChar == '\\"' && length > 1) {\r\n\t\t\taString = [aString substringFromIndex:1];\r\n\t\t\taChar = [aString characterAtIndex:0];\r\n\t\t\tlength--;\r\n\t\t}\r\n\r\n\t\tif (aChar == 'T' && length > 4 && [aString characterAtIndex:1] == 'h' && [aString characterAtIndex:2] == 'e' && [aString characterAtIndex:3] == ' ')\r\n\t\t\treturn [aString substringFromIndex:4];\r\n\t\telse if (aChar == 'A') {\r\n\t\t\tif (length > 3) {\r\n\t\t\t\tif ([aString characterAtIndex:1] == ' ')\r\n\t\t\t\t\treturn [aString substringFromIndex:2];\r\n\t\t\t\telse if ([aString characterAtIndex:1] == 'n' && [aString characterAtIndex:2] == ' ')\r\n\t\t\t\t\treturn [aString substringFromIndex:3];\r\n\t\t\t}\r\n\t\t}\r\n\t\telse if (aChar == 'E') {\r\n\t\t\tif (length > 3) {\r\n\t\t\t\tif ([aString characterAtIndex:1] == 'l' && [aString characterAtIndex:2] == ' ') \/\/ el\r\n\t\t\t\t\treturn [aString substringFromIndex:3];\r\n\t\t\t}\r\n\t\t\tif (length > 4) {\r\n\t\t\t\tif ([aString characterAtIndex:1] == 'i' && [aString characterAtIndex:2] == 'n' && [aString characterAtIndex:3] == ' ') \/\/ ein\r\n\t\t\t\t\treturn [aString substringFromIndex:4];\r\n\t\t\t}\r\n\t\t\tif (length > 5) {\r\n\t\t\t\tif ([aString characterAtIndex:1] == 'i' && [aString characterAtIndex:2] == 'n' && [aString characterAtIndex:3] == 'e' && [aString characterAtIndex:4] == ' ') \/\/ eine\r\n\t\t\t\t\treturn [aString substringFromIndex:5];\r\n\t\t\t}\r\n\t\t\tif (length > 6) {\r\n\t\t\t\tif ([aString characterAtIndex:1] == 'i' && [aString characterAtIndex:2] == 'n' && [aString characterAtIndex:3] == 'e' && [aString characterAtIndex:5] == ' ') {\r\n\t\t\t\t\tif (([aString characterAtIndex:4] == 'n') \/\/ einen\r\n\t\t\t\t\t\t|| ([aString characterAtIndex:4] == 'm') \/\/ einem\r\n\t\t\t\t\t\t|| ([aString characterAtIndex:4] == 'r') \/\/ einer\r\n\t\t\t\t\t\t|| ([aString characterAtIndex:4] == 's') \/\/ eines\r\n\t\t\t\t\t\t)\r\n\t\t\t\t\t\treturn [aString substringFromIndex:6];\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t}\r\n\t\telse if (aChar == 'U') {\r\n\t\t\tif (length > 3) {\r\n\t\t\t\tif ([aString characterAtIndex:1] == 'n' && [aString characterAtIndex:2] == ' ') \/\/ Un\r\n\t\t\t\t\treturn [aString substringFromIndex:3];\r\n\t\t\t}\r\n\t\t\tif (length > 4) {\r\n\t\t\t\tif ([aString characterAtIndex:1] == 'n' && [aString characterAtIndex:3] == ' ') {\r\n\t\t\t\t\tif (([aString characterAtIndex:2] == 'a') \/\/Una\r\n\t\t\t\t\t\t|| ([aString characterAtIndex:2] == 'e') \/\/ Une\r\n\t\t\t\t\t\t)\r\n\t\t\t\t\t\treturn [aString substringFromIndex:4];\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t}\r\n\t\telse if (aChar == 'D') {\r\n\t\t\tif (length > 4) {\r\n\t\t\t\tif ([aString characterAtIndex:1] == 'e' && [aString characterAtIndex:3] == ' ') {\r\n\t\t\t\t\tif (([aString characterAtIndex:2] == 's') \/\/ Des\r\n\t\t\t\t\t\t|| ([aString characterAtIndex:2] == 'r') \/\/ Der\r\n\t\t\t\t\t\t|| ([aString characterAtIndex:2] == 'm') \/\/ Dem\r\n\t\t\t\t\t\t|| ([aString characterAtIndex:2] == 'n') \/\/ Den\r\n\t\t\t\t\t\t)\r\n\t\t\t\t\t\treturn [aString substringFromIndex:4];\r\n\t\t\t\t}\r\n\t\t\t\telse if (([aString characterAtIndex:1] == 'i' && [aString characterAtIndex:2] == 'e' && [aString characterAtIndex:3] == ' ') \/\/ Die\r\n\t\t\t\t\t\t || ([aString characterAtIndex:1] == 'a' && [aString characterAtIndex:2] == 's' && [aString characterAtIndex:3] == ' ') \/\/ Das\r\n\t\t\t\t\t\t )\r\n\t\t\t\t\treturn [aString substringFromIndex:4];\r\n\t\t\t}\r\n\t\t}\r\n\t\telse if (aChar == 'L') {\r\n\r\n\t\t\tif (length > 3) {\r\n\t\t\t\tif ( [aString characterAtIndex:2] == ' ' &&\r\n\t\t\t\t\t([aString characterAtIndex:1] == '\\'' \/\/ L'\r\n\t\t\t\t\t || [aString characterAtIndex:1] == 'o' \/\/ Lo\r\n\t\t\t\t\t || [aString characterAtIndex:1] == 'a' \/\/ La\r\n\t\t\t\t\t || [aString characterAtIndex:1] == 'e')) \/\/ Le\r\n\t\t\t\t\treturn [aString substringFromIndex:3];\r\n\t\t\t\telse if ([aString characterAtIndex:1] == '\\'') \/\/ L' Without space suffix\r\n\t\t\t\t\treturn [aString substringFromIndex:2];\r\n\t\t\t}\r\n\t\t\tif (length > 4) {\r\n\t\t\t\tif ([aString characterAtIndex:2] == 's' && [aString characterAtIndex:3] == ' ') {\r\n\t\t\t\t\tif (([aString characterAtIndex:1] == 'e') \/\/ Les\r\n\t\t\t\t\t\t|| ([aString characterAtIndex:1] == 'o') \/\/ Los\r\n\t\t\t\t\t\t|| ([aString characterAtIndex:1] == 'a' ) \/\/ Las\r\n\t\t\t\t\t\t)\r\n\t\t\t\t\t\treturn [aString substringFromIndex:4];\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t}\r\n\t\telse if (aChar == 'I') {\r\n\t\t\tif (length > 3) {\r\n\t\t\t\tif (([aString characterAtIndex:1] == 'l' && [aString characterAtIndex:2] == ' ') \/\/ il\r\n\t\t\t\t\t)\r\n\t\t\t\t\treturn [aString substringFromIndex:3];\r\n\t\t\t}\r\n\t\t}\r\n\t}\r\n\treturn aString;\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
Mark Dalrymple wrote an interesting article about the speed difference between isEqual: and isEqualToString: methods. Choosing between these methods is a small decision programmers make everyday. The article should reaffirm readers beliefs that concentrating on readability is more important than performance. The short of it is that he runs the methods 10 million times to […]<\/p>\n","protected":false},"author":4,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[92,91],"class_list":["post-691","post","type-post","status-publish","format-standard","hentry","category-cocoa","tag-objective-c-speed","tag-sorting-articles"],"_links":{"self":[{"href":"https:\/\/bruji.com\/blog\/wp-json\/wp\/v2\/posts\/691","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/bruji.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/bruji.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/bruji.com\/blog\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/bruji.com\/blog\/wp-json\/wp\/v2\/comments?post=691"}],"version-history":[{"count":27,"href":"https:\/\/bruji.com\/blog\/wp-json\/wp\/v2\/posts\/691\/revisions"}],"predecessor-version":[{"id":762,"href":"https:\/\/bruji.com\/blog\/wp-json\/wp\/v2\/posts\/691\/revisions\/762"}],"wp:attachment":[{"href":"https:\/\/bruji.com\/blog\/wp-json\/wp\/v2\/media?parent=691"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/bruji.com\/blog\/wp-json\/wp\/v2\/categories?post=691"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/bruji.com\/blog\/wp-json\/wp\/v2\/tags?post=691"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}