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.");
}
}
