Algorithm for finding the difference between two arrays

Question

Given two arrays, is there a fast algorithm for finding all elements in the two that are different? For example, consider two arrays of Keys (as in keyboard keys) structs. One represents the currently depressed keys, and the other represents the keys depressed in the last timestep.

Keys[] oldKeys = LastKeyboardState.GetPressedKeys();
Keys[] currKeys = CurrentKeyboardState.GetPressedKeys();

// the user just pressed these key(s) during the last timestep.
Keys[] diff = ...

Suggestions are much appreciated!

Answer 1

Try this

var diff = oldKeys.Except(currKeys);

This requires C# 3.0

Answer 2

Two bitfields, run binary XOR. Whatever 1s you are left with is what you want.

Answer 3

To followup on JaredPar: that will only show the keys in oldKeys but not in currKeys. So if A is in currKeys but not in oldKeys, it will not appear in diff.

var diff = oldKeys.Union(currKeys).Except(currKeys.Intersect(oldKeys))

Will get those as well.

Answer 4

Well, brute force algorithm would be m*n where m and n are the sizes of your two arrays.

If you're using any sort of a tree instead of a linear array, then your time falls to m * log2(n)

The algorithm for that is

foreach(key ok in oldkeys)
{
    if(!oldKeys.Contains(ok))
    {
        diff.add(ok);
    }
}
foreach(key nk in newkeys)
{
    if(!newKeys.Contains(nk))
    {
        diff.add(nk);
    }
}