Algorithm for "Synchronization" 2 arrays
Array 1 | Array 2
=================
1 | 2
2 | 3
3 | 4
5 | 5
| 6
What is a good algorithm for synchronizing or combining array 2 into array 1? The following should happen:
- The integers in array 2, but not in array 1, must be added to array 1.
- The integers in both arrays can be left alone.
- The integers in array 1, but not in array 2, must be removed from array 1.
I'll end up coding this in Obj-C, but I'm really just looking for a pseudo-coded representation of an efficient algorithm to solve this problem, so feel free to suggest an answer in any form.
EDIT:
The end result I want is difficult to explain without giving a backstory. I have a Cocoa application that has a Core Data object whose data needs to be updated with data from a web service. I can't just rewrite the contents of array 1 (main data object) with the contents of array 2 (data parsed from the network into an array) because array 1 has a relationship with other core data objects in my application. Therefore, it is mainly important that the integers contained in both arrays are not overwritten in the array.
source to share
I'm kind of guessing since your example leaves some things in the air, but normally in situations like this I would use a set. Here is some sample code in Obj-C.
NSMutableSet *set = [NSMutableSet set];
[set addObjectsFromArray:array1];
[set addObjectsFromArray:array2];
NSArray *finalArray = [[set allObjects] sortedArrayUsingSelector:@selector(compare:)];
source to share
In my approach, you will need Set data structure . Hopefully you can find some implementations in Obj-C.
- Add all elements of Array1 to Set1 and do the same for Array2 to Set2.
- Looping through the elements of an array 1. Check if it is contained in Set2 (using the provided method.) If this did not remove an element from Set1.
- Scrolling through the elements of Array2. If it doesn't already exist in Set1, add it to Set1.
All Set1 elements are now your "synchronized" data.
The complexity of the algorithm "contains", "remove" and "add" the operation "Set" on some good implementation, for example HashSet
, will give you the efficiency you want.
EDIT . Here's a simple implementation that Set
assumes an integer is in a bounded range of 0 to 100, with each element initialized to 0 to give a clearer idea of the Set.
First you need to define a 101 array of arrays. And then for ..
- contains (n) - checks if bucket [n] is equal to 1 or not.
- add (n) - set bucket [n] to 1.
- delete (n) - set bucket [n] to 0.
source to share
(Assuming this is not a trivial question Array1 = Array2
) if the arrays are sorted, you are going through one O (n + m) pass through both arrays. Move the pointer to the beginning of both arrays, then move the pointer that contains the smaller element. Keep comparing items as you go and add / remove items accordingly. The efficiency of this might be worth the cost of sorting the arrays if they aren't already.
source to share
You speak:
What is a good algorithm for synchronizing or combining array 2 into array 1? The following should happen:
- The integers in array 2, but not in array 1, must be added to array 1.
- The integers in both arrays can be left alone.
- The integers in array 1, but not in array 2, must be removed from array 1.
Here are some algorithms to help you (python):
def sync(a, b):
# a is array 1
# b is array 2
c = a + b
for el in c:
if el in b and el not in a:
a.append(el) # add to array 1
elif el in a and el not in b:
a.remove(el) # remove from array 1
# el is in both arrays, skip
return a # done
source to share
Instead of "what should happen here", try describing the requirements in terms of "final condition is required here." From this point of view, it appears that the desired end state for array1
contains exactly the same values as array2
.
If so, why not an equivalent to this pseudocode (if your environment doesn't have a method clone
or copy
)?
array1 = new int[array2.length]
for (int i in 0 .. array2.length - 1) {
array1[i] = array2[i]
}
If order, keeping duplicates, etc. are problems, then please update the question and we can try again.
source to share
Ok, if the order doesn't matter, you already have your own algorithm:
- The integers in array 2, but not in array 1, must be added to array 1.
- The integers in both arrays can be left alone.
- The integers in array 1, but not in array 2, must be removed from array 1.
If the ordering of the integers depends on what you want, this is a variation of the algorithms that determine the "difference" between two strings. The Levenshtein algorithm should fit your requirements.
However, I suspect you really want the first part. In this case, what exactly arises? How do I find integers in an array? Or ... what?
source to share
Your question doesn't say anything about ordering, and if you look at the three requirements, you will see that the postcondition says that Array2 is unchanged and Array1 now contains exactly the same set of integers that is in Array2 . If you don't mention some ordering requirement , you can just make a copy of Array2.
source to share