using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
public class Test
{
public static void Main()
{
//TimeSolution(new HashSetSolution());
TimeSolution(new OriginalSolution());
TimeSolution(new MySolution());
TimeSolution(new ListSolution());
}
private static void TimeSolution(ISolution solution)
{
Random random = new Random(7);
var sw = new Stopwatch();
var count = 0;
const int iterations = 20;
const int arraySize = 10000;
for (int i = 0; i < iterations; i++)
{
var input = GetRandomArray(arraySize, random);
var shuffled = new int[arraySize];
Array.Copy(input, shuffled, arraySize);
Shuffle(input, random);
sw.Start();
var areEqual = solution.SetEqual(input, shuffled, null);
sw.Stop();
if (areEqual)
{
count++;
}
}
Console.WriteLine("{0} / {1}: {2}", count, iterations, sw.Elapsed);
}
private static int[] GetRandomArray(int size, Random random)
{
int[] result = new int[size];
for (int i = 0; i < size; i++)
{
result[i] = random.Next();
}
return result;
}
private static void Shuffle(int[] input, Random random)
{
for (int i = input.Length - 1; i > 0; i--)
{
var j = random.Next(i + 1);
var swap = input[i];
input[i] = input[j];
input[j] = swap;
}
}
interface ISolution
{
bool SetEqual<T>(IEnumerable<T> source, IEnumerable<T> other, IEqualityComparer<T> comparer);
}
class HashSetSolution : ISolution
{
public bool SetEqual<T>(IEnumerable<T> source, IEnumerable<T> other, IEqualityComparer<T> comparer = null)
{
if (source == null) {
throw new ArgumentNullException("source");
}
if (other == null) {
throw new ArgumentNullException("other");
}
return new HashSet<T>(source, comparer).SetEquals(other);
}
}
class OriginalSolution : ISolution
{
public bool SetEqual<T>(IEnumerable<T> source, IEnumerable<T> other, IEqualityComparer<T> comparer = null)
{
if (source == null) {
throw new ArgumentNullException("source");
}
if (other == null) {
throw new ArgumentNullException("other");
}
ICollection<T> sourceCollection = source as ICollection<T> ?? source.ToArray();
ICollection<T> otherCollection = other as ICollection<T> ?? other.ToArray();
if (sourceCollection.Count != otherCollection.Count) {
return false;
}
if (sourceCollection.Except(otherCollection, comparer).Any()) {
return false;
}
if (otherCollection.Except(sourceCollection, comparer).Any()) {
return false;
}
return true;
}
}
class MySolution : ISolution
{
public bool SetEqual<T>(IEnumerable<T> source, IEnumerable<T> other, IEqualityComparer<T> comparer = null)
{
if (source == null)
{
return other == null;
}
if (other == null)
{
return false;
}
int sourceLength = source.Count();
int otherLength = other.Count();
if (sourceLength != otherLength)
{
return false;
}
// Create our dictionary.
// Keys - 'source' elements.
// Values - their counts in the 'source'.
Dictionary<T, int> counts = comparer == null
? new Dictionary<T, int>(sourceLength)
: new Dictionary<T, int>(sourceLength, comparer);
// Fill the dictionary with 'source' items and their counts:
foreach(T item in source)
{
int value;
if (counts.TryGetValue(item, out value))
counts[item] = value + 1; // Item already exists? Add 1 to counts.
else
counts.Add(item, 1); // Add new item with count = 1.
}
// Remove `other` items from the dictionary:
foreach (T item in other)
{
int value;
if (counts.TryGetValue(item, out value))
{
if (value == 1) // If the count == 1, remove the item from the dictionary
counts.Remove(item);
else // If the item exists, decrease its count:
counts[item] = value - 1;
}
else
{
// No such item? Collections are not equal.
return false;
}
}
// Is there any items left in the dictionary?
// If no, collections are equal.
return counts.Count == 0;
}
}
class ListSolution : ISolution
{
public bool SetEqual<T>(IEnumerable<T> source, IEnumerable<T> other, IEqualityComparer<T> comparer = null)
{
if (source == null)
{
return other == null;
}
if (other == null)
{
return false;
}
ICollection<T> sourceCollection = source as ICollection<T>;
ICollection<T> otherCollection = other as ICollection<T>;
if (sourceCollection != null && otherCollection != null)
{
if (sourceCollection.Count != otherCollection.Count)
{
return false;
}
}
IList<T> sourceList = new List<T>(source);
foreach (T item in other)
{
if (!sourceList.Remove(item)) { return false; }
}
return sourceList.Count == 0;
}
}
}