LINQ for different sets

Question

I have the following arrays:

var original= new int[] { 2, 1, 3 };
var target = new int[] { 1, 3, 4 };
enum Operation {Added,Removed}

I would like to execute a LINQ query that returns the following:

{{2,Removed},{4,Added}}

Limitation: I would like LINQ to do this very efficiently and avoid O (n ^ 2) style algorithms.

Answer 1

Perhaps LINQ is not the best option in this case.

This will lead to the creation of a dictionary with the desired result.

Dictionary<int, Operation> difference = new Dictionary<int,Operation>();
foreach (int value in original) {
    difference.Add(value, Operation.Removed);
}
foreach (int value in target) {
    if (difference.ContainsKey(value)) {
        difference.Remove(value);
    } else {
        difference.Add(value, Operation.Added);
    }
}

To reduce the size of the dictionary, perhaps you can copy the enumerations in parallel. I will look at that ...

Edit:
Here it is:

Dictionary<int, Operation> difference = new Dictionary<int,Operation>();
IEnumerator<int> o = ((IEnumerable<int>)original).GetEnumerator();
IEnumerator<int> t = ((IEnumerable<int>)target).GetEnumerator();
bool oActive=true, tActive=true;
while (oActive || tActive) {
    if (oActive && (oActive = o.MoveNext())) {
        if (difference.ContainsKey(o.Current)) {
            difference.Remove(o.Current);
        } else {
            difference.Add(o.Current, Operation.Removed);
        }
    }
    if (tActive && (tActive = t.MoveNext())) {
        if (difference.ContainsKey(t.Current)) {
            difference.Remove(t.Current);
        } else {
            difference.Add(t.Current, Operation.Added);
        }
    }
}

Edit2:
. 10% -20% , , .

1 100000, 10% . 16 .

Answer 2

enum Operation { Added, Removed, }

static void Main(string[] args)
{
    var original = new int[] { 2, 1, 3 };
    var target = new int[] { 1, 3, 4 };

    var result = original.Except(target)
        .Select(i => new { Value = i, Operation = Operation.Removed, })
        .Concat(
            target.Except(original)
            .Select(i => new { Value = i, Operation = Operation.Added, })
            );

    foreach (var item in result)
        Console.WriteLine("{0}, {1}", item.Value, item.Operation);
}

, LINQ, , LINK, , , . . .

Answer 3

. , , , , , . :

{ 1, 2, 3, 4, 5, 6, 7, ...
{ 1, 2, 3, 6, 7, 8, 9, ...

At the moment when the first difference in the meetings (4 vs 6) is impossible to determine whether you are looking at deleting 4 and 5 (as in the case if both lists are monotonously increasing, or insert 6, 7, 8 and 9, as it would be in case the lists went on like this:

{ 1, 2, 3,             4, 5, 6, 7, 8, 9,...
{ 1, 2, 3, 6, 7, 8, 9, 4, 5, 6, 7, 8, 9,...

Answer 4

This will produce a single pass result, however, I am not sure about the complexity of the GroupBy operation.

var original= new int[] { 1, 2, 3 };
var target = new int[] { 1, 3, 4 };

var output = original.Select( i => new { I = i, L = "o" } )
    .Concat( target.Select( i => new { I = i, L = "t" } ) )
    .GroupBy( i => i.I ).Where( i => i.Count() == 1 )
.Select( i => new { I = i.Key, S = (i.ElementAt( 0 ).L == "o" ? Operation.Removed : Operation.Added) } );