Fastest way to check if an array contains the same objects of another array

Question

The goal is to compare two arrays as and check if they contain the same objects (as fast as possible - there are lots of objects in the arrays). The arrays cannot be checked with isEqual: as they are differently sorted.

I already tried the solution posted here (https://stackoverflow.com/a/1138417 - see last code snippet of the post by Peter Hosey). But this doesn't work with differently sorted arrays.

The code I'm using now is the following:

+ (BOOL)arraysContainSameObjects:(NSArray *)array1 andOtherArray:(NSArray *)array2 {
    // quit if array count is different
    if ([array1 count] != [array2 count]) return NO;

    BOOL bothArraysContainTheSameObjects = YES;
    for (id objectInArray1 in array1) {
        BOOL objectFoundInArray2 = NO;
        for (id objectInArray2 in array2) {
            if ([objectInArray1 isEqual:objectInArray2]) {
                objectFoundInArray2 = YES;
                break;
            }
        }
        if (!objectFoundInArray2) {
            bothArraysContainTheSameObjects = NO;
            break;
        }
    }

    return bothArraysContainTheSameObjects;
}

This works, but those are two nested fast enumerations. Is there a way to do a faster comparison?

Do you also have to verify that it has the same number of matching objects? For example if array 1 has 2 instances of X, but array 2 only has 1 then it fails? — borrrden, Feb 18 '13 at 11:33
In that case you have no choice but to sort them both and compare them. — borrrden, Feb 18 '13 at 11:40
Does this help: http://www.cocoabuilder.com/archive/cocoa/168144-finding-out-if-an-nsarray-contents-are-all-equal.html - `- (unsigned)numberOfDistinctObjects { return [[NSSet setWithArray:self] count]; }` — petert, Feb 18 '13 at 11:44
@borrrden: OK, how about time complexity when sorting both arrays and comparing them afterwards with `isEqualToArray:`? — FrankZp, Feb 18 '13 at 11:47
Well, it would be O(n) for the comparision, plus the efficiency of the sort algorithm. — borrrden, Feb 18 '13 at 11:49
If unequal is fairly likely you can do a quick check for that by hashing each entry and xoring the hash values, then comparing. Not much help if unequal is rare, though. — Hot Licks, Feb 18 '13 at 16:40
Try this [solution](http://stackoverflow.com/a/15269497/1635315). Its really helpful. — Kirti Nikam, Dec 06 '15 at 19:59

Anoop Vaidya · Accepted Answer · 2016-07-18T16:57:20.553

43

As per your code, you are strict to same number of elements and each object of first array should be there in second array and vice versa.

The fastest way would be to sort both the array and compare them.

Ex:

NSArray *array1=@[@"a",@"b",@"c"];
NSArray *array2=@[@"c",@"b",@"a"];

array1=[array1 sortedArrayUsingSelector:@selector(compare:)];
array2=[array2 sortedArrayUsingSelector:@selector(compare:)];

if ([array1 isEqualToArray:array2]) {
    NSLog(@"both have same elements");
}
else{
    NSLog(@"both having different elements");
}

edited Jul 18 '16 at 16:57

answered Feb 18 '13 at 11:45

Anoop Vaidya

46,283
15
111
140

Oh yes, I just noticed... similar thoughts. – Anoop Vaidya Feb 18 '13 at 11:58
1

@AKV Hmmm I analysed and later understood that its the best method and alternatives also take same time. :) – Pushpak Narasimhan Feb 18 '13 at 12:20
@FrankZp : You can also check like this, but not suggested as vague. – Anoop Vaidya Feb 18 '13 at 12:21
NSMutableArray *a1=[NSMutableArray arrayWithArray:array1]; NSMutableArray *a2=[NSMutableArray arrayWithArray:array2]; [a2 removeObjectsInArray:a1]; if ([a2 count]) { NSLog(@"Both are same"); } else{ NSLog(@"Both are different"); } – Anoop Vaidya Feb 18 '13 at 12:22
@AKV : Thanks for this comment - but I think I'm using the sorting and comparing with `isEqualToArray:` as this works really fine. – FrankZp Feb 18 '13 at 12:27
then how can i filter elements, say i have to add the elements into array1 from array2 like array2 = @[@"c",@"d",@"e",@"d"]; something like this..! – Majid Bashir Nov 28 '16 at 05:31

score 13 · Answer 2 · answered Feb 18 '13 at 11:36

13

How about converting both arrays to sets and comparing them.

NSSet *set1 = [NSSet setWithArray:arr1];
NSSet *set2 = [NSSet setWithArray:arr2];

Compare the two using

if([set1 isEqualToSet:set2]) {

}

answered Feb 18 '13 at 11:36

Shashank

1,743
1
14
20

2

I also considered this way, but it won't work if the conditions of my comment are valid. – borrrden Feb 18 '13 at 11:37
U were a step ahead @borrden :) – Shashank Feb 18 '13 at 11:48
This is the right answer if you aren't concerned about multiple instances of the same object in an array. – Luke The Obscure Jan 24 '14 at 00:38

Pushpak Narasimhan · Answer 3 · 2013-02-18T11:56:42.203

3

Use containsObject: method instead of iterating the whole array.

NSArray *array;
array = [NSArray arrayWithObjects: @"Nicola", @"Margherita",                                       @"Luciano", @"Silvia", nil];
if ([array containsObject: @"Nicola"]) // YES
  {
    // Do something
  }

like this

+ (BOOL)arraysContainSameObjects:(NSArray *)array1 andOtherArray:(NSArray *)array2 {
    // quit if array count is different
    if ([array1 count] != [array2 count]) return NO;

    BOOL bothArraysContainTheSameObjects = YES;

    for (id objectInArray1 in array1) {

        if (![array2 containsObject:objectInArray1])
        {
            bothArraysContainTheSameObjects = NO;
            break;
        }

    }

    return bothArraysContainTheSameObjects;
}

edited Feb 18 '13 at 11:56

answered Feb 18 '13 at 11:45

Pushpak Narasimhan

456
6
19

1

`containsObject`'s complexity is often linear in the worst case (even when the arrays are sorted), so this is not asymptotically more efficient than the two nested fast enumerations. – Daniel Martín Feb 18 '13 at 12:01
@DanielMartín Hmmm I agree. And as borrrden rightly said , only option is to sort and compare. – Pushpak Narasimhan Feb 18 '13 at 12:12
1

However, this approach can potentially exit much sooner, if it's highly likely that arrays are unequal. – Hot Licks Feb 18 '13 at 16:43

score 3 · Answer 4 · edited May 23 '17 at 10:31

Tried to get the accepted answer working but it wasn't quite the best fit for my situation.

I found this answer and all credit goes to @joel kravets for the method.

Basically sorting using a comparator enables you to sort using objects more easily - hence the problem I was facing when trying to use the above solution.

NSArray * array1 = [NSArray arrayWithArray:users];
NSArray * array2 = [NSArray arrayWithArray:threadUsers];

id mySort = ^(BUser * user1, BUser * user2){
    return [user1.name compare:user2.name];
};

array1 = [array1 sortedArrayUsingComparator:mySort];
array2 = [array2 sortedArrayUsingComparator:mySort];

if ([array1 isEqualToArray:array2]) {
    NSLog(@"both are same");
}
else{
    NSLog(@"both are different");
}

Previously I had tried to use other answers like those above, using break to go through loops but in the end this answer came out easiest probably due to its speed and also that in the end we have the if statement allowing us to put code depending on if they are the same or different.

Thanks to Anoop for getting me on the right track and Joel for helping me to tighten the efficiency of it

gnasher729 · Answer 5 · 2014-03-12T17:23:30.363

If you want to check whether both arrays contain the same duplicates, just use NSCountedSet. It's like an NSSet, but each object in the set also has a count telling you how often it has been added. So

BOOL same = (array1.count == array2.count);
if (same && array.count > 0)
{
    NSCountedSet* set1 = [[NSCountedSet alloc] initWithArray:array1];
    NSCountedSet* set2 = [[NSCountedSet alloc] initWithArray:array2];
    same = ([set1 isEqual: set2]);
}

No matter how you do it, this will be time consuming, so you might consider if there are special cases that can be handled quicker. Are these arrays usually the same, or almost the same, or is it true 99% of the time that they are different and that 99% of the time a random element of array1 is not in array2? Are the arrays often sorted? In that case, you could check whether there are identical objects in identical positions, and then consider only those objects that are not the same. If one array contains objects a, b, c, d, e and the other contains a, b, x, d, y, then you only need to compare the array [c, e] vs. [x, y].

Ramy Al Zuhouri · Answer 6 · 2013-02-18T12:33:23.380

1

This way the complexity is O(N^2), if you follow this approach you can't do it with a lower complexity. While instead you can do it with O(N log(N)) if you sort both arrays and then compare them. This way after having them sorted you will do it using isEqualToArray: in other N operations.

edited Feb 18 '13 at 12:33

answered Feb 18 '13 at 11:36

Ramy Al Zuhouri

21,580
26
105
187

I suppose that I'll have to sort both arrays? If the first array is unsorted and the other array is sorted, I guess that `isEqualToArray` will not return YES if the same objects are contained? (edit: just saw that borrrden added this as a comment to the first post ;) ) – FrankZp Feb 18 '13 at 11:42
Sorry, I thought that one was sorted, fixing it. – Ramy Al Zuhouri Feb 18 '13 at 12:32

score 1 · Answer 7 · answered Feb 18 '13 at 11:39

1

[docTypes containsObject:@"Object"];

It will works for your req. As early as fast it will return boolean value for it.

answered Feb 18 '13 at 11:39

Madhu

1,542
1
14
30

score 1 · Answer 8 · answered Feb 18 '13 at 16:36

NSArray *filtered = [someArray filteredArrayUsingPredicate:[NSPredicate predicateWithFormat:@"someParamter == %@", paramValue]]];
if (filtered.count) {

}

the main plus is you can use it for any kind of objects: custom, system, NSDictionary. for example I need to know is my UINavigationController's stack contains MySearchResultsVC and MyTopMenuItemsVC or not:

    NSArray *filtered = [self.navigationController.viewControllers filteredArrayUsingPredicate:
                                     [NSPredicate predicateWithFormat:@"class IN %@",
                                      [NSArray arrayWithObjects:
                                       [MySearchResultsVC class],
                                       [MyTopMenuItemsVC class],
                                       nil]]];
if (filtered) {
/* ok, now we can handle it! */
}

score 0 · Answer 9 · answered May 15 '15 at 11:01

I know it's late but i just wanna share what i did..

NSString *stringArr1 = [NSString stringWithFormat:@"%@", array1];
NSString *stringArr2 = [NSString stringWithFormat:@"%@", array2];

if ([stringArr1 isEqual: stringArr2])
    NSLog(@"identical");
else
    NSLog(@"not");

this is just like comparing "@[@1,@2,@3,@4]" == "[@3,@2,@1,@4]".. which is obviously false..

score -5 · Answer 10 · answered Feb 18 '13 at 11:33

-5

i guess this will do:

[array1 isEqualToArray:array2];

returns bool;

answered Feb 18 '13 at 11:33

spider1983

1,098
1
7
14

2

NSArray class reference says for `isEqualToArray:`: "Two arrays have equal contents if they each hold the same number of objects and objects at a given index in each array satisfy the isEqual: test." - As the arrays are differently sorted I suppose the method will return NO even when the same objects are in both arrays but with a different sort. – FrankZp Feb 18 '13 at 11:36

Fastest way to check if an array contains the same objects of another array

10 Answers10

Linked