CODEWITHSUNDEEP
iosobjective-cnsarraynsdictionarynspredicate
Harsh
Harsh

Reputation: 2908

Searching an Array of Strings in Array of Dictionaries

I have an array of combinations which needs to be searched in another array of dictionaries

Array Of Dictionaries is as follows:

self.listOfAllContacts

({
    name = "William";
    recordId = 541;
},
{
    name = "Soan";
    recordId = 541;
},
{
    name = "kamal";
    recordId = 541;
},
{
    name = "Elisia";
    recordId = 541;
},  
{
    name = "Ben";
    recordId = 541;
},
{
    name = "Loki";
    recordId = 541;
},
{
    name = "Fraser";
    recordId = 541;
});

Array Of Combinations are as follows : array named as

self.arrayOfSearchCombinationsFormed

  <__NSArrayM 0x1702518b0>(
    ABCD,
    JK,
    AND,
    MIKE,
    ELI,
    STEV,
    FRASE,
    WIILIA
    )

Present Code in work:

self.filteredContacts = [[NSMutableArray alloc] init];
    NSArray *arrayToTraversed = [[NSArray alloc] initWithArray:self.arrayOfSearchCombinationsFormed];
    for(NSString *combination in arrayToTraversed){
        NSPredicate *predicateInsideLoop = [NSPredicate predicateWithFormat:@"name CONTAINS[cd] %@", combination];
        NSArray *filteredContactByName = [self.listOfAllContacts filteredArrayUsingPredicate:predicateInsideLoop];
        if([filteredContactByName count]>0){
            [self.filteredContacts addObjectsFromArray:filteredContactByName];
        }
        else{
            [self.arrayOfSearchCombinationsFormed removeObject:combination];
        }
    }

Presently this solution is inefficient and consuming a lot of memory. Any help would be appreciated.

Also note that any combination not found in the dictionary needs to be removed from the combinations array.

So my question is that i want the most efficient way of searching the names in terms of memory allocation. So that it uses minimum memory.

Upvotes: 4

Views: 1662

Answers (5)

Kevin Crain
Kevin Crain

Reputation: 1935

Why not implement a binary search algorithm to search array.

The link provided below gives you full details on how to implement binary search.

See: http://oleb.net/blog/2013/07/nsarray-binary-search/

Upvotes: 0

Lord Zsolt
Lord Zsolt

Reputation: 6557

I may have misunderstood the question, but wouldn't using an NSPredicate with a set work?

NSSet *contactsToSearchFor = [NSSet setWithArray:self.arrayOfSearchCombinationsFormed];
NSPredicate *prediate = [NSPredicate predicateWithFormat:@"name IN[cd] %@", contactsToSearchFor];
NSArray *results = [self.listOfAllContacts filteredArrayUsingPredicate:predicate];

I haven't tested this in XCode, but it should work.

Upvotes: 1

bteapot
bteapot

Reputation: 2027

This should do the trick:

NSString *sourceRegexp =
    [NSString stringWithFormat:@".*%@.*", 
        [combinations componentsJoinedByString:@".*|.*"]];

NSPredicate *sourcePredicate =
    [NSPredicate predicateWithFormat:@"name MATCHES[c] %@", sourceRegexp];

NSArray *filteredSource =
    [source filteredArrayUsingPredicate:sourcePredicate];

NSPredicate *combinationsPredicate =
    [NSPredicate predicateWithFormat:
        @"SUBQUERY(%@, $s, $s.name CONTAINS[c] SELF).@count > 0",
        filteredSource];

NSArray *filteredCombinations =
    [combinations filteredArrayUsingPredicate:combinationsPredicate];

Upvotes: 1

Nikita Arkhipov
Nikita Arkhipov

Reputation: 1258

I would recommend you to use swift for this purposes: it is much faster and allocates much less memory. Here is a solution in Swift:

func filterContacts(contacts: [Dictionary<String, String>], searchCombinations: [String]) -> [Dictionary<String, String>]{
   return contacts.filter { dict in
      let name = dict["name"]!
      for string in searchCombinations{
         if name.rangeOfString(string) != nil { return true }
      }
      return false
   }
}

Another much more complex solution would involve using Suffix Tree for storing your contacts data if duration of searching is important.

Upvotes: -1

gabbler
gabbler

Reputation: 13766

It might be helpful to use (NSPredicate*)predicateWithBlock: method to speed up searching.

Suppose you have a keys array and a source array, you want to filter the source array with the keys array. 

NSArray *keysArray = @[@"1",@"2",@"3"];    
NSArray *sourceArray = @[@"12",@"2",@"3",@"1",@"2"];

For the first object @"12" in sourceArray, looking at the keysArray, since @"12" contains @"1", you can stop filtering and keep the first object of both arrays. But original code uses @"1" to filter the sourceArray, result is @"12" and @"1", each element needs to be checked.

You can refer to the below code:

- (void)searchWithBlock:(NSArray*)keysArray
{
    NSDate *beginDate = [NSDate date];

    NSMutableSet *keySet = [NSMutableSet set];
    NSPredicate *intersectPredicate = [NSPredicate predicateWithBlock:^BOOL(id evaluatedObject, NSDictionary *bindings) {
        for (NSString *str in keysArray) {
            NSString *name = evaluatedObject[@"name"];
            NSRange r = [name rangeOfString:str options:NSCaseInsensitiveSearch];
            if (r.location != NSNotFound) {
                [keySet addObject:str];
                return true;
            }
        }
        return false;
    }];

    NSArray *intersect = [self.listOfAllContacts filteredArrayUsingPredicate:intersectPredicate];
    self.filteredContacts = [[NSMutableArray alloc] initWithArray:intersect];

    self.arrayOfSearchCombinationsFormed = [NSMutableArray arrayWithArray:[keySet allObjects]];

    NSDate *endDate = [NSDate date];
    NSTimeInterval interval = [endDate timeIntervalSinceDate:beginDate];
    NSLog(@"interval is %f",interval);

    NSLog(@"intersect %@\n, filtered key array is %@\n", intersect,keySet);
}

It needs about 1/3 of the original time for filtering, memory allocation is a little bit less. I suggest you split the larger data source to smaller chunks to use less memory.

Upvotes: 2

Related Questions