C# .NET Get difference between two unordered not unique lists using BitArrays for super fast speed

Here's how to get the difference between two lists preserving duplicates in each list that is super fast, using BitArrays. 

It's a counter intuitive approach since it loops over the lists 3 times, but since we are just setting a bit, it's super efficient. Definitely, interesting idea to use for other situations. 

As in my previous post, i dismiss all the Stack Overflow solutions with live code, and I presented my 1st attempt at the solution. 

This post demonstrates my super fast implementation, enjoy! 

//UNORDERED, NOT UNIQUE lists, lists with duplicates 

string[] arrA = new string[] { "1", "1", "2", "3", "4", "5", "9", "7", "7", "7" };
string[] arrB = new string[] { "1", "1", "2", "2", "3", "4", "5", "5", "5", "5" };

//DESIRED RESULT

2,5,5,5,7,7,7,9 OR 2,5,5,5,9,7,7,7 OR 9,7,7,7,2,5,5,5  //UNORDERED IS SUFFICIENT

NOTE: Linq Except but it's designed as a set command, and as a consequence it removes duplicates.

IEnumerable<string> AminuBdifference = arrA.Except(arrB); //removes dups
IEnumerable<string> BminuAdifference = arrB.Except(arrA); //remove dups

IEnumerable<string> Uniondifference = arrA.Union(arrb); //ideally, but no good because dups are removed

See https://dotnetfiddle.net/oHOms5  which demonstrates Linq Except use.

Below is my super fast implementation, using a pure BitArray implementations, enjoy!

Use case: For list with less than 100 values, otherwise use ExceptIndistinct.

 

Source Code

using System;
using System.Collections; 
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics; 

//CHALLENGE - Get difference between two unorderd, not unique lists, duplicates allowed within a list and across both lists.
//SOLUTION - https://metadataconsulting.blogspot.com/2021/02/CSharp-dotNet-Get-difference-between-two-unordered-not-unique-lists-aka-duplicates-allowed-within-a-list-and-across-both-lists.html
//OPTIMIZE - THIS IS IT using BitArray - https://metadataconsulting.blogspot.com/2021/02/CSharp-dotNet-Get-difference-between-two-unordered-not-unique-lists-lightning-fast-optimized.html
//OPTIMIZEv2 - All BitArray imp - https://metadataconsulting.blogspot.com/2021/02/CSharp-dotNet-Get-difference-between-two-unordered-not-unique-lists-using-BitArrays-for-super-fast-speed.html
//           - use ExceptIndistinct for >100 items 
public static class Program
{
	public static int loopcnt = 0;
	
	//https://stackoverflow.com/questions/2975944/except-has-similar-effect-to-distinct
	public static IEnumerable<T> ExceptFrom<T>(
		this IEnumerable<T> first,
		IEnumerable<T> second) //,
		//IEqualityComparer<TSource> comparer)
		{
			if (first == null)
				throw new ArgumentNullException();

			if (second == null)
				throw new ArgumentNullException();

			//var secondSet = second as HashSet<TSource> ?? // this trick ignore the comparer
			//				second.ToHashSet(comparer ?? EqualityComparer<TSource>.Default);

		    var secondSet = second as HashSet<T> ?? // this trick ignore the comparer
							second.ToHashSet(EqualityComparer<T>.Default);

			// Contains is O(1) for HashSet.
			return first.Where(v => !secondSet.Equals(v)); //change to equals, not Contains
		}

	//use after 100 items
    public static IEnumerable<T> ExceptIndistinct<T>(this IEnumerable<T> first, IEnumerable<T> second) 
	{
		if(first == null) { throw new ArgumentNullException("first"); }
		if(second == null) { throw new ArgumentNullException("second"); }

		var secondCounts = new Dictionary<T, int>(EqualityComparer<T>.Default);
		int count;
		int nullCount = 0;

		foreach(var item in second)
		{
			loopcnt++; 
			if(item == null) { nullCount++; }
			else if(secondCounts.TryGetValue(item, out count)) { secondCounts[item] = count + 1; }
			else { secondCounts.Add(item, 1); }
			
		}

		foreach(var item in first)
		{
			loopcnt++; 
			if(item == null)
			{
				nullCount--;
				if(nullCount < 0) { yield return item; }
			}
			else if(secondCounts.TryGetValue(item, out count))
			{
				if(count == 0)
				{
					secondCounts.Remove(item);
					yield return item;
				}
				else { secondCounts[item] = count - 1; }
			}
			else { yield return item; }
		}
	}

	public static void Main()
	{
			Stopwatch sw = new Stopwatch();
			

			//RANDOM case - typical use
			string[] arrA = new string[] { "a", "7", "1", "2", "3", "4", "5", "9", "7", "7", "1","222222222222222222","22222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222323" };
			string[] arrB = new string[] { "a", "1", "1", "2", "2", "3", "4", "5", "5", "5", "5","999999999999999999","22222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222323" };
			
			sw.Start(); 
			//WANT           2,5,5,5,9,7,7,7

			//WORST case - entirely different, but have 1 value in common to make it interesting
			//string[] arrA = new string[] { "1", "1", "2", "3", "4", "5", "6", "7", "7", "7" };//1st list
			//string[] arrB = new string[] { "8", "9", "10", "12", "1", "14", "15", "15", "11", "9" };//2nd list

			//BEST case - identical
			//string[] arrA = new string[] { "1", "1", "2", "3", "4", "5", "6", "7", "7", "7" };//1st list
			//string[] arrB = new string[] { "1", "1", "2", "3", "4", "5", "6", "7", "7", "7" };//2nd list


			sw.Stop();
			Console.WriteLine("RANDOM CASE -two unorderd, not unique lists ");
			Console.WriteLine("A  = " + string.Join(",", arrA));
			Console.WriteLine("B  = " + string.Join(",", arrB));
	    	Console.WriteLine("A count = " + arrA.Count());
			Console.WriteLine("B count = " + arrB.Count());
			
			sw.Restart();

			string[] arrBminusA = new string[arrB.Length];
			string[] arrAminuB = new string[arrA.Length];   
			BitArray bitArrAminusB = new BitArray(arrA.Length);
			BitArray bitarrBminusA = new BitArray(arrB.Length);
			
			//May seem counter intuitive to run this over 3 loop but it's faster ~ 10 ticks
			int a = 0;
            for (int b = 0; b < arrB.Length; b++)
            {
                for (a = 0; a < arrA.Length; a++)
                {
                    loopcnt++;//not need for timing analysis 

                    if (!bitArrAminusB[a] && arrA[a].Length == arrB[b].Length && arrA[a] == arrB[b])
                    {
                        bitArrAminusB.Set(a, true); //A-B, list A difference/subtract of list B  
                        bitarrBminusA.Set(b, true); //B-A, list B difference/subtract of list A  
                        break;

                    }
                }
            }

            int idxa = 0;
            for (int aa = 0; aa < arrA.Length; aa++)
            {
                if (!bitArrAminusB[aa])
                    arrAminuB[idxa++] = arrA[aa];
                
            }

            int idxb = 0;
            for (int bb = 0; bb < arrB.Length; bb++)
            {
                if (!bitarrBminusA[bb])
                    arrBminusA[idxb++] = arrB[bb];

            }
			sw.Stop();

           Console.WriteLine("(A-B) Result = " + string.Join(",", arrAminuB).Trim(','));
           //Console.WriteLine("D  = " + string.Join(",", D));
           //Console.WriteLine("E  = " + string.Join(",", E)); 

           Console.WriteLine("(B-A) Result = " + string.Join(",", arrBminusA).TrimEnd(','));

           Console.WriteLine("No. of loops = " + loopcnt);
           Console.WriteLine("No. of loops = " + arrA.Length*2 + " - Post copy using BitArray to a sized array");

		   //Un	
           Console.WriteLine("Result Unorderd Final A then B = " + (string.Join(",", arrAminuB)).Trim(',') + "," + string.Join(",", arrBminusA).Trim(',') + " in " + sw.ElapsedTicks + " ticks.");
           Console.WriteLine("Result Unorderd Final B then A = " + (string.Join(",",  arrBminusA)).Trim(',') + "," + string.Join(",",arrAminuB).Trim(',') + " in " + sw.ElapsedTicks + " ticks.");
 		   Console.WriteLine("Note: In a VS solution this is 47 ticks.");
           
           List<string> D = arrBminusA.ToList().Concat(arrAminuB.ToList()).ToList();
           D.Sort();

           Console.WriteLine("Result  Ordered Final = " + string.Join(",", D).TrimStart(','));
		   Console.WriteLine("Result  O(n^2+2n) but very fast - can you beat it?"); 
		
		   loopcnt = 0; 
		   Console.WriteLine("\n\nExceptIndistinct - Reddit Solution by UninformedPleb\n"); 
           sw.Reset(); 
		   
		   
		   List<string> listA = new List<string> { "a", "7", "1", "2", "3", "4", "5", "9", "7", "7", "1","222222222222222222","22222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222323" };
		   List<string> listB = new List<string>  { "1", "1", "2", "2", "3", "4", "5", "5", "5", "5" };
		   
		   sw.Start(); 
           List<string> listC =  listA.ExceptIndistinct(listB).ToList();
		   List<string> listD =  listB.ExceptIndistinct(listA).ToList();

     	   sw.Stop();

		   Console.WriteLine("No. of loops = " + loopcnt);
		   Console.WriteLine("Result Unorderd Final A then B = " + (string.Join(",", listC)).Trim(',') + "," + string.Join(",", listD).Trim(',') + " in " + sw.ElapsedTicks + " ticks.");
			
		   loopcnt = 0; 
		   Console.WriteLine("\n\nExceptIndistinct - Reddit Solution by UninformedPleb using arrays\n"); 
           sw.Reset(); 
		   
		   string[] arrAA = new string[] { "a", "7", "1", "2", "3", "4", "5", "9", "7", "7", "1","222222222222222222","22222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222323" };
    	   string[] arrBB = new string[] { "1", "1", "2", "2", "3", "4", "5", "5", "5", "5","999999999999999999","22222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222" };
  		   sw.Start(); 
		   
           string[] listCC =  arrAA.ExceptIndistinct(arrBB).ToArray(); 
		   string[] listDD =  arrBB.ExceptIndistinct(arrAA).ToArray(); 

     	   sw.Stop();
		
		   Console.WriteLine("No. of loops = " + loopcnt);
		   Console.WriteLine("Result Unorderd Final A then B = " + (string.Join(",", listC)).Trim(',') + "," + string.Join(",", listD).Trim(',') + " in " + sw.ElapsedTicks + " ticks.");
		
		
		
		   loopcnt = 0; 
		   Console.WriteLine("\n\nStackOverflow ExceptFrom\n"); 
           sw.Reset(); 
		 
		   string[] arrAAA = new string[] { "a", "7", "1", "2", "3", "4", "5", "9", "7", "7", "1","222222222222222222","22222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222323" };
    	   string[] arrBBB = new string[] { "1", "1", "2", "2", "3", "4", "5", "5", "5", "5","999999999999999999","22222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222" };
  		   sw.Start(); 
		   
           string[] listCCC =  arrAAA.ExceptFrom(arrBBB).ToArray(); 
		   string[] listDDD =  arrBBB.ExceptFrom(arrAAA).ToArray(); 

     	   sw.Stop();
		
		   Console.WriteLine("No. of loops = " + loopcnt);
		   Console.WriteLine("Result Unorderd Final A then B = " + (string.Join(",", listC)).Trim(',') + "," + string.Join(",", listD).Trim(',') + " in " + sw.ElapsedTicks + " ticks.");
		
		
		
			
	}
}

C# .NET Get difference between two unordered not unique lists, lightning fast, optimized

Here's how to get the difference between two lists preserving duplicates in each list that is super fast. 

As in my previous post, i dismiss all the Stack Overflow solutions with live code, and I presented my 1st attempt at the solution. 

This post demonstrates my super fast implementation, enjoy! 

//UNORDERED, NOT UNIQUE lists, lists with duplicates 

string[] arrA = new string[] { "1", "1", "2", "3", "4", "5", "9", "7", "7", "7" };
string[] arrB = new string[] { "1", "1", "2", "2", "3", "4", "5", "5", "5", "5" };

//DESIRED RESULT

2,5,5,5,7,7,7,9 OR 2,5,5,5,9,7,7,7 OR 9,7,7,7,2,5,5,5  //UNORDERED IS SUFFICIENT

NOTE: Linq Except but it's designed as a set command, and as a consequence it removes duplicates.

IEnumerable<string> AminuBdifference = arrA.Except(arrB); //removes dups
IEnumerable<string> BminuAdifference = arrB.Except(arrA); //remove dups

IEnumerable<string> Uniondifference = arrA.Union(arrb); //ideally, but no good dups removed

See https://dotnetfiddle.net/oHOms5  which demonstrates Linq Except use.

Update : C# .NET Get difference between two unordered not unique lists using 2 BitArrays for super fast speed - handles worst case scenario

Below is my super fast implementation, enjoy!

 

Source Code

using System;
using System.Collections; 
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics; 

//CHALLENGE - Get difference between two unorderd, not unique lists, duplicates allowed within a list and across both lists.
//SOLUTION - https://metadataconsulting.blogspot.com/2021/02/CSharp-dotNet-Get-difference-between-two-unordered-not-unique-lists-aka-duplicates-allowed-within-a-list-and-across-both-lists.html
//OPTIMIZE - THIS IS IT using BitArray - https://metadataconsulting.blogspot.com/2021/02/CSharp-dotNet-Get-difference-between-two-unordered-not-unique-lists-lightning-fast-optimized.html
                    
public class Program
{
    public static int loopcnt = 0;
    
    public static void Main()
    {
            Stopwatch sw = new Stopwatch();
            sw.Start(); 
            
            //RANDOM case - typical use ~ 78 ticks 
            string[] arrA = new string[] { "7", "1", "2", "3", "4", "5", "9", "7", "7", "1" };
            string[] arrB = new string[] { "1", "1", "2", "2", "3", "4", "5", "5", "5", "5" };

            //WANT           2,5,5,5,9,7,7,7
        
            //WORST case - entirely different, but have 1 value in common to make it interesting ~ 88 ticks
            //string[] arrA = new string[] { "1", "1", "2", "3", "4", "5", "6", "7", "7", "7" };//1st list
            //string[] arrB = new string[] { "8", "9", "10", "12", "1", "14", "15", "15", "11", "9" };//2nd list
        
            //BEST case - identical ~ 24 ticks
            //string[] arrA = new string[] { "1", "1", "2", "3", "4", "5", "6", "7", "7", "7" };//1st list
            //string[] arrB = new string[] { "1", "1", "2", "3", "4", "5", "6", "7", "7", "7" };//2nd list
        
        
            sw.Stop();
            Console.WriteLine("RANDOM CASE -two unorderd, not unique lists ");
            Console.WriteLine("A  = " + string.Join(",", arrA));
            Console.WriteLine("B  = " + string.Join(",", arrB));
            sw.Restart();
            
            string[] diffAminusB = new string[arrA.Length];      
            string[] diffBminusA = new string[arrB.Length];
             
            BitArray bitarrRemoveA = new BitArray(arrA.Length); 
                        
            int d = 0; //index for diff list
            int a = 0; 
            bool nf = true; //not found 

            //bitarrRemove.Set(a, true);  version -> 13 ticks blazing fast, 19 ticks for worst case identical sets on my computer!
            for (int b = 0; b < arrB.Length; b++)
            {
                nf = true;

                for (a = 0; a < arrA.Length; a++)
                {
                    loopcnt++; //not require for metrics
                    //diffAminusB[a] = arrA[a]; //Tried to preload this array, and remove items using speedy BitArray, but slow             

                    if (!bitarrRemoveA[a] && arrA[a] == arrB[b])
                    {
                        nf = false;
                        bitarrRemoveA.Set(a, true); //magic - A-B = diffsA - flag removals for post processing
                        break;

                    }
                }

                if (nf) //not found in set B 
                    diffBminusA[d++] = arrB[b]; //diffs B not found in A, mathematically B-A = diffsB (order important here, driven by B, so those results appear)
                    
                
                
            }
            
            //Get A-B = diffsA, some memory savings (but very slight) here since it's a sized array
            int idx = 0;
            for (a = 0; a < arrA.Length; a++)
            {
                if (!bitarrRemoveA[a])
                    diffAminusB[idx++] = arrA[a];
               
            }

    
           sw.Stop();

           Console.WriteLine("(A-B) Result = " + string.Join(",", diffAminusB).Trim(','));
           //Console.WriteLine("D  = " + string.Join(",", D));
           //Console.WriteLine("E  = " + string.Join(",", E)); 

           Console.WriteLine("(B-A) Result = " + string.Join(",", diffBminusA).TrimEnd(','));

           Console.WriteLine("No. of loops = " + loopcnt);
           Console.WriteLine("No. of loops = " + arrA.Length + " - Post copy using BitArray to a sized array");

           //Un 
           Console.WriteLine("Result Unorderd Final A then B = " + (string.Join(",", diffAminusB)).Trim(',') + "," + string.Join(",", diffBminusA).Trim(',') + " in " + sw.ElapsedTicks + " ticks.");
           Console.WriteLine("Result Unorderd Final B then A = " + (string.Join(",",  diffBminusA)).Trim(',') + "," + string.Join(",",diffAminusB).Trim(',') + " in " + sw.ElapsedTicks + " ticks.");

            
           List<string> C = diffBminusA.ToList();

           List<string> D = diffBminusA.ToList().Concat(diffAminusB.ToList()).ToList();
           D.Sort();

           Console.WriteLine("Result  Ordered Final = " + string.Join(",", D).TrimStart(','));
           Console.WriteLine("Result  O(n^2) but very fast - can you beat it?"); 
    
    }
}

C# .NET Get difference between two unordered not unique lists aka duplicates allowed within a list and across both lists

Here's how to get the difference between two lists preserving duplicates in each list.

Update: C# .NET Get difference between two unordered not unique lists using 2 BitArrays for super fast speed - handles worst case scenario

//UNORDERED, NOT UNIQUE lists, lists with duplicates 

string[] arrA = new string[] { "1", "1", "2", "3", "4", "5", "9", "7", "7", "7" };
string[] arrB = new string[] { "1", "1", "2", "2", "3", "4", "5", "5", "5", "5" };

//DESIRED RESULT

2,5,5,5,7,7,7,9 OR 2,5,5,5,9,7,7,7 OR 9,7,7,7,2,5,5,5  //UNORDERED IS SUFFICIENT

NOTE: Tried Linq Except but it's designed as a set command, and as a consequence it removes duplicates.

IEnumerable<string> AminuBdifference = arrA.Except(arrB); //removes dups
IEnumerable<string> BminuAdifference = arrB.Except(arrA); //remove dups

IEnumerable<string> Uniondifference = arrA.Union(arrb); //ideally, but no good dups removed

See https://dotnetfiddle.net/kzjUJi  for quick example.

Briefly, some highlights of set theory, since most Linq commands are designed to be set commands. 

In the image below, it shows a representation for sets (distinct values, can be unordered), and it demonstrates one important fact about sets.  

The order of difference ("subtraction") is important in set theory.

List1 - List2 <> List2 - List1 

See https://dotnetfiddle.net/kzjUJi  for a demonstration of this.

So hence in image below, you see difference produce in order between upper and lower sets. 
If we take union we get [3,2,1,7,8] vs [8,7,3,2,1]  reflecting the difference order choice.

This is important when you look at all the solutions that were attempted on Stack Overflow, because the generally only do 1 difference 'subtraction' only.

All the implementation on this question were wrong on Stack Overflow.

c# - Difference between two lists preserving duplicates - Stack Overflow

For the required solution, we are using lists with duplicates so order is unimportant and should yield same result, since we are getting the union of the two list differences.

Here's my 1st pass at this implementation and it's faster then all mentioned in Stack Overflow post.

Update : Massive speed improvement - see my post here.

Update 2: C# .NET Get difference between two unordered not unique lists using 2 BitArrays for super fast speed - handles worst case scenario

Source Code

using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics; 
                    
public static class Program
{
     public static int loopcnt = 0; 
     public static IEnumerable<T> RemoveRange<T>(this IEnumerable<T> source, IEnumerable<T> second)
     {
         var tempList = source.ToList();

         foreach (var item in second)
         {
             tempList.Remove(item); //this is cause a copy like RemoveAt below
         }

         return tempList;
     }

    //RemoveAt for arrays, this is problematic copy and shrink time consuming - see my next post on how to fix this!
    public static void RemoveAt<T>(ref T[] arr, int index)
    {
        for (int a = index; a < arr.Length - 1; a++)
        {
            // moving elements downwards, to fill the gap at [index]
            arr[a] = arr[a + 1];
            loopcnt++; //not required but here for time anaylsis
        }
        // finally, let's decrement Array's size by one
        Array.Resize(ref arr, arr.Length - 1);
    }
    
    //CHALLENGE - Get difference between two unorderd, not unique lists, duplicates allowed within a list and across both lists.
    //Will demonstrate all solutions from https://stackoverflow.com/questions/15801655/difference-between-two-lists-preserving-duplicates 
    //are WRONG!
    //SOLUTION - https://metadataconsulting.blogspot.com/2021/02/CSharp-dotNet-Get-difference-between-two-unordered-not-unique-lists-aka-duplicates-allowed-within-a-list-and-across-both-lists.html
    //OPTIMIZE - Next blog post will drastically reduce increase the speed of this
    public static void Main()
    {
        
            Console.WriteLine("Get difference between two unordered, not unique (duplicates) lists!");
            Console.WriteLine("Solution by https://metadataconsulting.blogspot.com/2021/02/CSharp-dotNet-Get-difference-between-two-unordered-not-unique-lists-aka-duplicates-allowed-within-a-list-and-across-both-lists.html");
            Console.WriteLine();
        
            Stopwatch sw = new Stopwatch();
            sw.Start(); 

            //UNORDERED, NOT UNIQUE lists, lists with duplicates 
            string[] arrA = new string[] { "1", "1", "2", "3", "4", "5", "9", "7", "7", "7" };
            string[] arrB = new string[] { "1", "1", "2", "2", "3", "4", "5", "5", "5", "5" };

            //DESIRED RESULT = 2,5,5,5,7,7,7,9 OR 2,5,5,5,9,7,7,7 OR 9,7,7,7,2,5,5,5 UNORDERED IS SUFFICIENT, WE LOOKING FOR SPEED
        
            sw.Stop();
            Console.WriteLine("A  = " + string.Join(",", arrA));
            Console.WriteLine("B  = " + string.Join(",", arrB));
            Console.WriteLine("A Count  = " + arrA.Length);    
            Console.WriteLine("B Count  = " + arrB.Length);
            Console.WriteLine();
            sw.Restart();

            //MY IMPLEMENTATION PURE ARRAY SOLUTION -     
        
            string[] diff = new string[arrA.Length+arrB.Length]; //contains B-A 
                        
            int d = 0; //index for diff list
            bool nf = true; //not found 
            loopcnt = 0; 
        
            int a = 0;  
            for (int b = 0; b < arrB.Length; b++)
            {
                nf = true;

                for (a = 0; a < arrA.Length; a++)
                {
                    loopcnt++; //not required but here for time anaylsis                
                    if (arrA[a] == arrB[b])
                    {
                        nf = false;

                        RemoveAt(ref arrA, a); //magic - removes instance found, A is left with differences not found in B, mathematically A-B = diffsA 

                        break;

                    }
                    
                }

                if (nf) //not found in set B 
                {
                    diff[d] = arrB[b]; //diffs B not found in A, mathematically B-A = diffsB (order important here, driven by B, so those results appear)
                    d++;
                }
                
            }
            
            sw.Stop(); 
            Console.WriteLine("No. of loops = " + loopcnt);
            Console.WriteLine("(A-B) Result = " + string.Join(",", arrA).TrimEnd(','));
            Console.WriteLine("(B-A) Result = " + string.Join(",", diff).TrimEnd(','));
            Console.WriteLine("Result Unorderd Final = " + (string.Join(",", diff)).TrimEnd(',') + "," + string.Join(",", arrA) + " in " + sw.ElapsedTicks + " ticks.");

            List<string> C = diff.ToList();

            List<string> D = diff.ToList().Concat(arrA.ToList()).ToList();
            D.Sort();

            Console.WriteLine("Result  Ordered Final = " + string.Join(",", D).TrimStart(','));
            
            sw.Reset();
            sw.Start();
            
            Console.WriteLine(); 
            Console.WriteLine("000 StackOverflow answers all wrong 000");
            Console.WriteLine("https://stackoverflow.com/questions/15801655/difference-between-two-lists-preserving-duplicates"); 
            Console.WriteLine("000 I don't post on StackOverflow because of the idiotic moderators and comments 000");
            Console.WriteLine(); 

            //https://stackoverflow.com/questions/15801655/difference-between-two-lists-preserving-duplicates
            //Dustin Kingen
            List<string> M = new List<string>() { "1", "1", "2", "3", "4", "5", "9", "7", "7", "7" };
            List<string> N = new List<string>() { "1", "1", "2", "2", "3", "4", "5", "5", "5", "5" };
         
            var ListDiffs = M.RemoveRange(N);
            sw.Stop();  
            Console.WriteLine("RemoveRage Result = " + string.Join(",", ListDiffs) + " in " + sw.ElapsedTicks + " ticks.");

            sw.Reset();
            sw.Start();
            
            //https://stackoverflow.com/questions/15801655/difference-between-two-lists-preserving-duplicates
            //Ani
            List<string> list2 = new List<string>() { "1", "1", "2", "3", "4", "5", "9", "7", "7", "7" };
            List<string> list1 = new List<string>() { "1", "1", "2", "2", "3", "4", "5", "5", "5", "5" };
            
            var lookup2 = list2.ToLookup(str => str);

            var result = from str in list1
                         group str by str into strGroup
                         let missingCount
                              = Math.Max(0, strGroup.Count() - lookup2[strGroup.Key].Count())
                         from missingStr in strGroup.Take(missingCount)
                         select missingStr;
            sw.Stop();
            Console.WriteLine("Lookup Result = " + string.Join(",", result) + " in " + sw.ElapsedTicks + " ticks.");
            sw.Reset();
            sw.Start();
            
            List<string> AA = new List<string>() { "1", "1", "2", "3", "4", "5", "9", "7", "7", "7" };
            List<string> BB = new List<string>() { "1", "1", "2", "2", "3", "4", "5", "5", "5", "5" };
         
            //https://stackoverflow.com/questions/15801655/difference-between-two-lists-preserving-duplicates
            //Sergey Kalinichenko 
            var diffLinq = AA.Select(e => new { Key = e, Val = 1 })
                    .Concat(BB.Select(e => new { Key = e, Val = -1 }))
                    .GroupBy(e => e.Key, e => e.Val)
                    .SelectMany(g => Enumerable.Repeat(g.Key, Math.Max(0, g.Sum())))
                    .ToList();

            sw.Stop();
            Console.WriteLine("diffLinq Result = " + string.Join(",", diffLinq) + " in " + sw.ElapsedTicks + " ticks.");




    }
}