Merge NSMutableArray with NSArray, duplicate filtering

Question

I have two arrays: NSMutableArray and NSArray. NSMutableArray is a "repository", it stores the results from an NSArrays source. Every 5 minutes a new NSArray appears, and the data needs to be filtered and sorted.

Sorting by date is pretty simple, so I managed to get an NSArray sorted by NSDate. Sorting another array is optional, as this can cause confusion with the user.

What I want to do: NSArray has many different objects that everyone answers to - [object name], returning an NSString. NSArray must be merged into NSMutableArray by adding only new objects.

Merging itself is not a problem, but performance. NSMutableArray can contain up to 3000 elements, and NSArray can contain up to 250 elements, although usually only 5 or 6 of them should be combined into an NSMutableArray.

So my question is: how do you combine two arrays in Objective-C, filtering duplicates, without repeating (250 * 3000) times?

Tom

Edited to clarify something
A duplicate is objects that duplicate a user, not a code. They have the same name, but not the same address.

Additional explanation: @"value" != @"value" // true

Answer 1

Is name property of objects stored in arrays? If so, you can use the fairly simple NSPredicate to filter the immutable array before adding the results to the mutable. Here is an example:

 NSPredicate *predicate = [NSPredicate predicateWithFormat:@"NONE name == %@.name", mutableArray]; resultsArray = [immutableArray filteredArrayUsingPredicate:predicate]; [mutableArray addObjectsFromArray:immutableArray]; 

Answer 2

How about this:

 [mutable removeObjectsInArray:newArray]; [mutable addObjectsFromArray:newArray]; 

It is not the thickest, but it is easy to implement :)

Answer 3

Edited to remove some nonsense (much remains, though)

Several variants:

• Remove all matching objects from NSMutableArray using removeObjectIdenticalTo . This requires iteration through a smaller array, but as you noticed, they are usually small. Then,

• Add all elements from the new array using addObjectsFromArray

Or ... well, actually it could be faster:

• Go through the new array, looking for matches with indexOfObjectIdenticalTo , using addObject to add to inappropriate objects.

Expensive anyway, but doable.

Answer 4

Can you use NSSet and NSMutableSet instead? This can help solve the problem with duplicates.

Edit:

Based on your comments, you can use NSSet to quickly and quickly determine membership in an object in addition to your array. This will require a bit more memory, but if you don't mind, it may allow you to quickly check. You will have a backup storage of NSMutableArray and then NSSet to track the ownership of the object. You would keep the invariant that NSMutableArray does not contain duplicates. You can use this code:

 // Assume that arrayStore is an NSMutableArray * instance variable // Also, storeSet is an NSMutableSet * ivar - (void)addObjectsFromArray:(NSArray *)data { for (id item in data) { if (![storeSet member:item]) { // Will have to keep arrayStore sorted somehow [arrayStore addObject:item]; [storeSet addObject:item]; } } } 

You only need to iterate through NSArray . I'm not sure how NSSet is implemented from my point of view, but membership verification will not be such an O (n) operation as for an unsorted array.

This is not the most efficient method, but it works well with what you already have, with minor changes.

Answer 5

I would probably start by creating a new mutable array that contains the contents of your NSMutableArray and NSArray. Then sort the new array based on the name property, and then run the array once, pulling out the unique elements.

Answer 6

There are probably many ways to significantly improve performance, but in order to be able to offer any, we really need to know more about what objects in arrays “have”: what do they represent? How are they used? (For example, are items in the storage array displayed as a table?)

NSMutableDictionary , NSMutableSet etc. can be combined with NSMutableArray to efficiently and efficiently implement the model.

For example, let's say we know that an object represents a person: MDPerson . A person has a gender, date of birth, name, unique identifier and a set of attributes that can change. Given this higher understanding of what the object represents, we know that 2 people are equal only if their unique identifiers are the same (in other words, 2 different people can have the same name, gender and date of birth). Say your main NSMutableArray consists of a list of 3,000 people. The incoming array consists of 500 people who are already in the main NSMutableArray . Some of these 500 people may have “updated” attributes, which means that their instance in the main array must be updated with this information.

Given this understanding, it is clear that the main list should be implemented as an NSMutableDictionary , not an NSMutableArray . In the dictionary, the only key will be the unique identifier of the person, and his copy for the person will be the value for the key. Then you can scroll through an incoming array of 500 people only once:

  // main dictionary is called personIDsAndPersons for (MDPerson *person in incomingPersons) { MDPerson *existingPerson = [personIDsAndPersons objectForKey:[person uniqueID]]; // if nil, the person doesn't exist if (existingPerson) { // update the existing person attributes [existingPerson setUniqueAttributes:[person uniqueAttributes]]; } } 

Again, without knowing more details or a higher level of understanding of objects, we really shoot in the dark.

You mentioned that 2 elements are the same if they have the same name. Does this mean that each element in the main array of 3000 objects has a unique name? If so, you can use NSMutableDictionary to provide access to objects in an efficient way, having keys in the dictionary as a name and values ​​as an instance of the object. Then you can use a separate NSMutableArray , which is used only for display purposes: it allows an ordered, sorted organization of the same objects that are stored in NSMutableDictionary . Remember that when you add an object to an array or a dictionary, usually you do not create a new copy, you just save the existing object.