4

I've been working on a search algorithm all afternoon and I'd like some opinions. Some of what I'm doing is specific to iOS, but the general concepts are not.

I'm trying to display a set of data, a directory. In the directory I have departments and people. I know this sounds like a textbook example, hear me out. It's not homework, I promise. (I can provide screenshots of what I'm working on.)

I have an array of entries, where there are those two kinds of directory entries. I need to sort the entries by name, then break up the array into smaller arrays, where each sub-array contains the entries that begin with the same letter.

Additionally, I need to account for a search string that the user may enter.

My general process is this:

  1. Filter all the entries that match the type and search string if there is one. For this step I use an NSPredicate:

    NSPredicate *predicate = [NSPredicate predicateWithFormat:@"type == %i AND searchableContents B[cd] %@", type, searchString];

if (!searchString || searchString.length == 0)
{
    predicate = [NSPredicate predicateWithFormat:@"type == %i", type];
}

NSArray *array = [_directoryContents filteredArrayUsingPredicate:predicate];

  2. Sort the results alphabetically.

    array  = [array sortedArrayUsingComparator:^NSComparisonResult(id obj1, id obj2) {
    return [((BRKDirectoryEntry *)obj1).comperableTitle compare:((BRKDirectoryEntry *)obj2).comperableTitle];
}];

  3. Break up the results into smaller arrays. For performance, I skip this step if we're searching, but it doesn't seem to help. 

    if(alphabetized)
{
    array = [self _alphabetizedArrayFromPresortedArray:array];
}

The performance of this on a total of 950 entries is abysmal.

Now, for my default display, I can get away with simply caching the sorted data in memory, and then display and scrolling performs nicely, but for search-as-I-type, there's simply no way to achieve the smooth performance that users expect.

Any pointers or tips?

Brian Tompsett - 汤莱恩
  • 5,753
  • 72
  • 57
  • 129
Moshe
  • 57,511
  • 78
  • 272
  • 425
  • 2
    I'm still amazed at how many people ask "I'm doing XYZ, and it's too slow. How can I make it faster?" As if other people's guesses have much of a chance. There's a Swiss-army-knife can't-lose method. [*Let the program itself tell you the answer.*](http://stackoverflow.com/a/378024/23771) Here's a [*short example*](http://stackoverflow.com/a/4299378/23771) (in python, but you'll get the idea). – Mike Dunlavey Aug 29 '14 at 00:21
  • Just a small tip: using a predicate is much slower than fast enumeration as shown here: https://www.objc.io/issues/7-foundation/collections/ (section **Enumeration and Higher-Order Messaging**) And i think you can simplify this line of code if (!searchString || searchString.length == 0) to if(!searchString.length) – Duc Dec 19 '15 at 00:26

1 Answers1

1

Yes. Forget files and keep it in a database. Create your indexes Everything becomes a simple SQL statement.

Dan
  • 11
  • 1