CODEWITHSUNDEEP
objective-calgorithmsearchnsstringnsmutablearray
thandasoru
thandasoru

Reputation: 1558

Optimise searching in an array, search by comparison of 2 strings in Objective C

I have a list of contacts retrieved from Address book stored inside a MutableArray contactList. Each contact is an object which has properties like "contactName, contactImage.... etc".

dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_BACKGROUND, 0),^{
    //getAllContacts is a method which returns a Mutable array of Objects
    self.contactList = [NSMutableArray arrayWithArray:[instance getAllContacts]];

    //groupLetterToLoad could be "DEF"
    for(int j=0; j<self.groupLetterToLoad.length;j++) { 
        //1st iteration D, 2nd iteration E and 3rd iteration F
        NSString *testChar = [NSString stringWithFormat:@"%c",[self.groupLetterToLoad characterAtIndex:j]];
        //check D,E,F with contact name property's first letter of the contact list array
        for(int i=0;i<self.contactList.count;i++) {
            NSString *firstChar =[[[self.contactList objectAtIndex:i] contactName] substringToIndex:1];
            if([testChar isEqualToString: firstChar]) {
                pos=i; //retrieve the index of the matched position
                break;
            }
        }
        if(pos!=-1) break;
    }
});

Now this has two for loops (Time O(n^2)).. The disadvantage here is, if the groupLetterToLoad is "WXYZ", then comparison will start from W with A to W with Z.. How can I optimise it?

Upvotes: 1

Views: 254

Answers (2)

justin
justin

Reputation: 104718

Ordering your array by contactName and performing a half interval search will reduce your complexity greatly if can avoid sorting every time you search (hint: keep [instance getAllContacts] sorted).

http://rosettacode.org/wiki/Binary_search#Objective-C - that's a starting point. you could replace the compare: with your first character comparison.

Upvotes: 2

Catfish_Man
Catfish_Man

Reputation: 41831

This isn't an algorithmic improvement, but the way you're handling characters is about the slowest way possible. If your group letters are really ASCII letters as you indicate, try this (I include the "if" in my answer because doing correct comparison of non-ASCII is really best left up to NSString):

1) Instead of using -substringToIndex to get the first character, use -characterAtIndex:0 and store a unichar

2) Instead of using +stringWithFormat:@"%c" to make a single character string, just use -characterAtIndex: and store it in a unichar

3) Instead of using -isEqualToString:, use == on the unichars

Unrelated, I'm pretty suspicious of the thread-safety of this. Are all those properties on self and instance you're accessing really not accessed on any other queue or thread?

Upvotes: 0

Related Questions