Algorithm for 'Syncing' 2 Arrays

Question

Array 1 | Array 2
=================
   1    |   2
   2    |   3
   3    |   4
   5    |   5
        |   6

What is a good algorithm to 'sync' or combine Array 2 into Array 1? The following needs to happen:

1. Integers in Array 2 but not in Array 1 should be added to Array 1.
2. Integers in both Arrays can be left alone.
3. Integers in Array 1 but not in Array 2 should be removed from Array 1.

I'll eventually be coding this in Obj-C, but I'm really just looking for a pseudo-code representation of an efficient algorithm to solve this problem so feel free to suggest an answer in whatever form you'd like.

EDIT:

The end result I need is bit hard to explain without giving the backstory. I have a Cocoa application that has a Core Data entity whose data needs to be updated with data from a web service. I cannot simply overwrite the contents of Array 1 (the core data entity) with the content of Array 2 (the data parsed from the web into an array) because the Array 1 has relationships with other core data entities in my application. So basically it is important that integers contained in both Arrays are not overwritten in array one.

Answer 1

Array1 = Array2.Clone() or some equivalent might be the simplest solution, unless the order of elements is important.

Answer 2

Well, if the order doesn't matter, you already have your algorithm:

1. Integers in Array 2 but not in Array 1 should be added to Array 1.
2. Integers in both Arrays can be left alone.
3. Integers in Array 1 but not in Array 2 should be removed from Array 1.

If the order of the integers matter, what you want is a variation of the algorithms that determine the "difference" between two strings. The Levenshtein algorithm should suit your well.

However, I suspect you actually want the first part. In that case, what exactly is the question? How to find the integers in an array? Or ... what?

Answer 3

In my approach, You will need Set data structure. I hope you can find some implementations in Obj-C.

1. Add all elements of Array1 to Set1 and do the same for Array2 to Set2.
2. Loop through elements of Array1. Check if it is contained in Set2 (using provided method.) If it is not, removed the element from Set1.
3. Loop through elements of Array2. If it is not existed in Set1 yet, add it to Set1.

All elements of Set1 is now your "synced" data.

The algorithm complexity of "contains","delete", and "add" operation of "Set" on some good implementation, such as HashSet, would give you the efficiency you want.

EDIT: Here is a simple implementation of Set assumed that the integer are in limited range of 0 - 100 with every elements initialized to 0, just to give more clear idea about Set.

You first need to define array bucket of size 101. And then for ..

• contains(n) - check if bucket[n] is 1 or not.
• add(n) - set bucket[n] to 1.
• delete(n) - set bucket[n] to 0.

Answer 4

(Assuming this is not a simple Array1 = Array2 question,) if the arrays are sorted, you're looking at a single O(n+m) pass over both arrays. Point to the beginning of both arrays, then advance the pointer containing the smaller element. Keep comparing the elements as you go and add/delete elements accordingly. The efficiency of this might be worth the cost of sorting the arrays, if they aren't already such.

Answer 5

You say:

What is a good algorithm to 'sync' or combine Array 2 into Array 1? The following needs to happen:

1. Integers in Array 2 but not in Array 1 should be added to Array 1.
2. Integers in both Arrays can be left alone.
3. Integers in Array 1 but not in Array 2 should be removed from Array 1.

Here's some literal algorithmic 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

Answer 6

Instead of "here's what needs to happen", try describing the requirements in terms of "here's the required final condition". From that perspective it appears that the desired end-state is for array1 to contain exactly the same values as array2.

If that's the case, then why not the equivalent of this pseudocode (unless your environment has a clone or copy method)?

array1 = new int[array2.length]
for (int i in 0 .. array2.length - 1) {
    array1[i] = array2[i]
}

If order, retention of duplicates, etc. are issues, then please update the question and we can try again.

Answer 7

I'm kind of guessing since your example leaves some things up in the air, but typically in situations like this I would use a set. Here's some example code in Obj-C.

NSMutableSet *set = [NSMutableSet set];
[set addObjectsFromArray:array1];
[set addObjectsFromArray:array2];
NSArray *finalArray = [[set allObjects] sortedArrayUsingSelector:@selector(compare:)];

Answer 8

Your question says nothing about order, and if you examine your three requirements, you'll see that the postcondition says that Array2 is unchanged and Array1 now contains exactly the same set of integers that is in Array2. Unless there's some requirement on the order that you're not telling us about, you may as well just make a copy of Array2.