Search array of NSObjects containing Arrays

Question

I have an Array full of PhRecords. For simplicity sake, let us consider the structure of object is as follows:

@interface PhRecord : NSObject

@property (nonatomic, strong) NSArray *PhName; //Person's name
@property (nonatomic, strong) NSArray *PhNumbers; //Person will have 2/3 contact numbers
@property (nonatomic, strong) NSArray *PhTypes; //The types of the contact numbers

@end

There is a property in my class which goes through the phone book and collects the names and phone numbers in an array in the format specified above. Let's say the array is the following

@property (nonatomic, strong) NSArray *allContacts;

Also, I have method to get all contacts as PhRecords with the following method

- (NSArray *)getAllContacts;

I have a method where if I give the contact number, it will find the name and type of the contact.

//Assume that both string1 and string2 don't have (,),*,#,+ and "<white space>"
- (void)findContactByPhoneNumber:(NSString *)phNum {
    NSString *string1 = phNum;
    NSArray *contacts = [self getAllContacts];
    for(SDPhoneRecord *record in contacts) {
        for(int j=0;j<record.PhNumbers.count;j++) {
            NSString *string2 = [[record.PhNumbers objectAtIndex:j];
            if([string2 rangeOfString:string1].location!=NSNotFound) {
                NSLog(@"Name:%@,Type:%@",record.PhName,[record.PhTypes objectAtIndex:j];
            }
        }
    }
}

As you can see, this search has time complexity of O(n^2). Is it possible to do a O(1) lookup? If I have to use predicates, how can I use them with this kind of requirement where a "range" of string has to be compared with the string passed argument?

It is possible to get close to O(n). All you need to do is use an NSDictionary or other efficiently searched object for you PhNumbers object. — Hot Licks
– Hot Licks, Commented Dec 25, 2013 at 14:21
Ok, I'll modify the data structure accordingly. Many thanks for the suggestion! — thandasoru
– thandasoru, Commented Dec 25, 2013 at 14:40

Hot Licks · Accepted Answer · 2013-12-25 14:38:04Z

3

To improve the "big O" you need to eliminate loops, not simply hide them. This generally implies using some sort of "look at" mechanism, vs a "look up" mechanism -- a mechanism that uses, eg, a hash table to locate item. The main such mechanism in Objective-C is the NS(Mutable)Dictionary, which internally contains a hash table.

In some cases it's possible to employ properties of the data to improve search efficiency, but absent that the hash table is usually the best (and most general) approach.

answered Dec 25, 2013 at 14:38

Hot Licks

47.8k19 gold badges96 silver badges156 bronze badges

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

Comments

Garrett · Accepted Answer · 2013-12-25 14:14:16Z

0

Use the NSArray objectsPassingTest where the test is if the phone number attribute is equal to the provided string

answered Dec 25, 2013 at 14:14

Garrett

5,6302 gold badges35 silver badges48 bronze badges

2 Comments

thandasoru Over a year ago

Equality can't be the relation. For example, I might provide 1234567 but the contact might have 001-1234567. Can I check range with objectsPassingTest?

Hot Licks Over a year ago

Using objectsPassingTest, et al, will not improve the "big O" of the algorithm, just hide part of it (and generally be somewhat less efficient than the straight-forward loop).

Collectives™ on Stack Overflow

Search array of NSObjects containing Arrays

2 Answers 2

Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related