CODEWITHSUNDEEP
iphoneobjective-cios
user1007895
user1007895

Reputation: 3965

What is the fastest way to search through strings in Objective-C?

I am implementing a sort of autocomplete for an iOS app. The data I am using for the autocomplete values is a comma-separated text file with about 100,000 strings. This is what I am doing now:

  1. Read the text file, and create an NSArray with 100,000 NSString.
  2. As the user types, do [array containsObject:text]

Surely there is a better/faster way to do this lookup. Any thoughts?

Upvotes: 8

Views: 3389

Answers (2)

tc.
tc.

Reputation: 33592

The simplest is probably binary search. See -[NSArray indexOfObject:inSortedRange:options:usingComparator:].

In particular, I'd try something like this:

  • Pre-sort the array that you save to the file
  • When you load the array, possibly @selector(compare:) (if you are worried about it being accidentally unsorted or the Unicode sort order changing for some edge cases). This should be approximately O(n) assuming the array is mostly sorted already.
  • To find the first potential match, [array indexOfObject:searchString inSortedRange:(NSRange){0,[array count]} options:NSBinarySearchingInsertionIndex|NSBinarySearchingFirstEqual usingComparator:@selector(compare:)]
  • Walk down the array until the entries no longer contain searchString as a prefix. You probably want to do case/diacritic/width-insensitive comparisons to determine whether it is a prefix (NSAnchoredSearch|NSCaseInsensitiveSearch|NSDiacriticInsensitiveSearch|NSWidthInsensitiveSearch)

This may not "correctly" handle all locales (Turkish in particular), but neither will replacing compare: with localizedCompare:, nor will naïve string-folding. (It is only 9 lines long, but took about a day of work time to get right and has about 40 lines of code and 200 lines of test, so I probably shouldn't share it here.)

Upvotes: 2

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726509

Absolutely, there is! It's not "in Objective-C" though: most likely, you would need to code it yourself.

The idea is to convert your list of string to a suffix tree, a data structure that lets you search by prefix very quickly. Searching for possible completions in a suffix tree are very fast, but the structure itself is not easy to build. A quick search on the internet revealed that there is no readily available implementation in Objective C, but you may be able to port an implementation in another language, use a C implementation, or even write your own if you are not particularly pressed for time.

Perhaps an easier approach would be to sort your strings alphabetically, and run a binary search on the prefix that has been entered so far. Though not as efficient as a suffix tree, the sorted array approach will be acceptable for 100K strings, because you get to the right spot in under seventeen checks.

Upvotes: 20

Related Questions