Optimize sorting of Array according to Distance (CLLocation)

Question

Currently my below code takes an average 9.27300 every time I run it. This is an iOS application and I can't expect the user to sit there for roughly 10 seconds.

This code takes an array (originalData) of placeObjects and calculates the distance from the selected location (CLLocation* searched). It does by [searched distanceFromLocation:currentLoc]; Each time the distance is calculated, the distance is stored into keysArray. After the first for loop the numbers are then sorted from ascending order.

After that another for loop is made to line up the originalData to follow the same ascending order as the keysArray.

A side note: I am currently doing this for 500 objects in originalData.

I am calling this method [self sortLocations]; from viewDidLoad.

-(void)sortLocations{
    NSLog(@"Start");
    [keysArray removeAllObjects];
    //originalData is an NSMutableArray
    for (int i = 0; i < [originalData count]; i++) {
        /* f is global but its:
         * f = [[NSNumberFormatter alloc] init];
         * [f setNumberStyle:NSNumberFormatterDecimalStyle];
         */
        NSNumber* cLat = [f numberFromString:[[originalData objectAtIndex:i] latitude]];
        NSNumber* cLng = [f numberFromString:[[originalData objectAtIndex:i] longitude]];
        CLLocation* currentLoc = [[CLLocation alloc] initWithLatitude:[cLat doubleValue] longitude:[cLng doubleValue]];
        //searched is a CLLocation
        CLLocationDistance distance = [searched distanceFromLocation:currentLoc];
        NSNumber* num = [NSNumber numberWithInt:distance];
        [keysArray addObject:num];
    }
    //lowToHight is this:  
    // lowToHigh = [NSSortDescriptor sortDescriptorWithKey:@"self" ascending:YES];
    [keysArray sortUsingDescriptors:[NSArray arrayWithObject:lowToHigh]];
    [orderedArray removeAllObjects];
    for (int i = 0; i < [keysArray count]; i++) {
        NSNumber* keyNum = [keysArray objectAtIndex:i];
        for (placeObjects* x in originalData){
            NSNumber* cLat = [f numberFromString:[x latitude]];
            NSNumber* cLng = [f numberFromString:[x longitude]];
            CLLocation *currentLoc = [[CLLocation alloc] initWithLatitude:[cLat doubleValue] longitude:[cLng doubleValue]];
            CLLocationDistance distance = [searched distanceFromLocation:currentLoc];
            NSNumber* num = [NSNumber numberWithInt:distance];
            if ([num intValue] == [keyNum intValue]) {
                [orderedArray addObject:x];
            }
        }
    }
    NSLog(@"End");
}

Answer 1

Your problem is with the code after the actual sort. For each item in the final array you scan over the whole original array recalculating the distance each time. That means that you'll calculate a distance some 500*500=250000 times.

The simplest solution would be to add a distance property to your objects. Then you sort by:

1. Iterating over all objects, setting the distance property
2. Sort on the distance property using sortUsingSelector method

Another solution would be decorate-sort-undecorate pattern. In this method:

1. Create a new array of objects with a distance and originalObject properties.
2. Sort on the distance property
3. Create a new array from the originalObject properties

Another solution would be to define a custom comparator. You write your own function that calculates whether one object is closer then another. You'd pass this function to sortUsingFunction.

Answer 2

Winston's answer points out some improvements to your algorithm. There are other ways in which we can slightly improve the speed of this.

In Objective-C, for loops (and while and do...while) loops are handled one iteration at a time and the exit condition is checked on each iteration of the loop. Meanwhile, a forin loop is handled in batches. When we're dealing with an array for example, a forin loop might cache the first 8 objects and work with them before it goes back and grabs more objects. In this way, we save time by calling fewer messages on the collection. Moreover, when it caches these objects, you've already got a reference to the object, so you don't have to waste yet another message to the collection to grab a reference to the object. Long story short, forin loops are faster than for loops in Objective-C, and you should use them when you can, even if you don't need the reference to the objects in the collection...

In this case though, we're actually wasting tons of execution time making calls back to the collection.

Moreover, NSString has a method called doubleValue which shouldn't have any trouble pulling a double value out of a string...

So let's clean up the first loop to look like this:

for (id object in originalData) {
    double latitude = [[object latitude] doubleValue];
    double longitude = [[object longitude] doubleValue];
    CLLocation* currentLoc = [[CLLocation alloc] initWithLatitude:latitude
                                                        longitude:longitude];

    CLLocationDistance distance = [searched distanceFromLocation:currentLoc];
    NSNumber* num = [NSNumber numberWithInt:distance];
    [keysArray addObject:num];
}

There are some things that are curious to me however.

What's the data type of the objects in the array? Why does it have properties latitude and longitude which you clearly need to do math things with yet they're stored as NSString objects? These should be stored as NSNumber objects or just double primitives preferably.

CLLocationDistance is a typedef for double. Why are we then taking this double and instantiating an NSNumber object with numberWithInt:?