Searching and Sorting Quickly

Question

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:

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];

Sort the results alphabetically.

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

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?

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. Here's a short example (in python, but you'll get the idea). — Mike Dunlavey
– Mike Dunlavey, Commented Aug 29, 2014 at 0:21
Just a small tip: using a predicate is much slower than fast enumeration as shown here: 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
– Duc, Commented Dec 19, 2015 at 0:26

Dan · Accepted Answer · 2014-08-29 00:23:36Z

1

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

answered Aug 29, 2014 at 0:23

Dan

111 bronze badge

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Searching and Sorting Quickly

1 Answer 1

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Linked

Related