Optimization of percent match code

Question

I have the following method that will take the car parts I searched for and match them to my car object in array. Then it tells me the percent match.

Example:

Car.h has NSSet toCarParts. toCarParts has may car parts.

My array contains 5,000 or so matches.

I will go through each one and match my parts to the car parts and calculate a percent match. If I search for wheel, tire, rim, and Car X has wheel, tire, rim, seat, my % should be 75%.

The method does this, but take about 30 seconds on an iPhone 5 (double or triple on iPhone 4)

How can I optimize it?

I think what slows it down is that I need to open each car object, fire the faults, access the toCarParts set, for each part compare if it matches a part in my search array.

I also think it is slow when doing division (counter/[carPartsArrayFaulted count]=%).

-(NSMutableArray*)calculatePercentagePerFind:(NSMutableArray*)CarArray:(NSMutableArray*)partsArray{
    NSArray*defaultParts =[NSArray arrayWithArray:[[[HelperMethods alloc]init]getObjectUserDefault:@"AvailableDefaultParts"]];

    int lowestPercentMatchInt=[[[HelperMethods alloc]init]getIntegerUserDefault:@"lowestPercentageMatch"];

    NSMutableArray*partsFromCarArray=[[NSMutableArray alloc]init];

    NSMutableArray*returnArray=[[NSMutableArray alloc]init];

    NSMutableArray *partsWithDefaultParts =[NSMutableArray arrayWithArray:partsArray];
    [partsWithDefaultParts addObjectsFromArray:defaultParts];


    for (int i=0; i<[CarArray count]; i++) {
        double matchCount=0;
        Car *CarResult =(Car*)[CarArray objectAtIndex:i];

                //Check if it will at least be 30% match
        double number1 = [partsWithDefaultParts count];
            number1 =(number1/[CarResult.numberOfParts doubleValue])*100;
            if (number1>lowestPercentMatchInt) {
                partsFromCarArray =[NSMutableArray arrayWithArray:[[CarResult toParts]allObjects]];
                NSMutableArray *faultedParts=[[NSMutableArray alloc]init];
                for (int i =0; i<[partsFromCarArray count]; i++) {
                    CarPart*part = (CarPart*)[partsFromCarArray objectAtIndex:i];
                        [faultedParts addObject:part.name];
                }
            // for each part in the Car
            for (NSString *partInCar in partsWithDefaultParts){
                //if the search parts contain that part, add one to count
                if ([faultedParts containsObject:partInCar]) {
                    matchCount++;
                }
            }
            //Calculate percent match
            double percentMatch = matchCount;

            percentMatch =(percentMatch/[CarResult.numberOfParts doubleValue])*100;

            //if at least 30%(user default) then add the percent match to Car result
            if (percentMatch >lowestPercentMatchInt) {
                if (percentMatch>100) {
                    CarResult.percentMatch = [NSNumber numberWithDouble:100.00];
                }else{
                    CarResult.percentMatch = [NSNumber numberWithDouble:percentMatch];
                }
                [returnArray addObject:CarResult];
            }
    }
    }
    NSLog(@"Percent Matched Cars = %i",[returnArray count]);
    return [self arrangeByHighestPercentMatch:returnArray];
}

Answer 1

Currently you are comparing all part against all parts, so you have a squared complexity which causes trouble for bigger numbers.

In the case that you can create your part list as sorted list (i.e. TreeSet in Java, not sure what is available in your language ) you can do the comparison in linear time by stepping through both lists in parallel.

An other idea is to use something like the HashSet in Java where the containsObject don't cost linear time as with the array or a simple list.