fork download
copy 
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Diagnostics;
  4. using System.Linq;
  5.  
  6. public class Test
  7. {
  8. 	public static void Main()
  9. 	{
  10. 	    //TimeSolution(new HashSetSolution());
  11. 	    TimeSolution(new OriginalSolution());
  12. 	    TimeSolution(new MySolution());
  13. 	    TimeSolution(new ListSolution());
  14. 	}
  15.  
  16. 	private static void TimeSolution(ISolution solution)
  17. 	{
  18. 	    Random random = new Random(7);
  19. 	    var sw = new Stopwatch();
  20. 	    var count = 0;
  21. 	    const int iterations = 20;
  22. 	    const int arraySize = 10000;
  23. 	    for (int i = 0; i < iterations; i++)
  24. 	    {
  25. 	        var input = GetRandomArray(arraySize, random);
  26. 	        var shuffled = new int[arraySize];
  27. 	        Array.Copy(input, shuffled, arraySize);
  28. 	        Shuffle(input, random);
  29.  
  30. 	        sw.Start();
  31. 	        var areEqual = solution.SetEqual(input, shuffled, null);
  32. 	        sw.Stop();
  33.  
  34. 	        if (areEqual)
  35. 	        {
  36. 	            count++;
  37. 	        }
  38. 	    }
  39.  
  40. 	    Console.WriteLine("{0} / {1}: {2}", count, iterations, sw.Elapsed);
  41. 	}
  42.  
  43. 	private static int[] GetRandomArray(int size, Random random)
  44. 	{
  45. 	    int[] result = new int[size];
  46. 	    for (int i = 0; i < size; i++)
  47. 	    {
  48. 	        result[i] = random.Next();
  49. 	    }
  50.  
  51. 	    return result;
  52. 	}
  53.  
  54. 	private static void Shuffle(int[] input, Random random)
  55. 	{
  56. 	    for (int i = input.Length - 1; i > 0; i--)
  57. 	    {
  58. 	        var j = random.Next(i + 1);
  59. 	        var swap = input[i];
  60. 	        input[i] = input[j];
  61. 	        input[j] = swap;
  62. 	    }
  63. 	}
  64.  
  65. 	interface ISolution
  66. 	{
  67. 	    bool SetEqual<T>(IEnumerable<T> source, IEnumerable<T> other, IEqualityComparer<T> comparer);
  68. 	}
  69.  
  70. 	class HashSetSolution : ISolution
  71. 	{
  72. 	    public bool SetEqual<T>(IEnumerable<T> source, IEnumerable<T> other, IEqualityComparer<T> comparer = null)
  73. 	    {
  74. 	        if (source == null) {
  75. 	            throw new ArgumentNullException("source");
  76. 	        }
  77.  
  78. 	        if (other == null) {
  79. 	            throw new ArgumentNullException("other");
  80. 	        }
  81.  
  82. 	        return new HashSet<T>(source, comparer).SetEquals(other);
  83. 	    }
  84. 	}
  85.  
  86. 	class OriginalSolution : ISolution
  87. 	{
  88. 	    public bool SetEqual<T>(IEnumerable<T> source, IEnumerable<T> other, IEqualityComparer<T> comparer = null)
  89. 	    {
  90. 	        if (source == null) {
  91. 	            throw new ArgumentNullException("source");
  92. 	        }
  93.  
  94. 	        if (other == null) {
  95. 	            throw new ArgumentNullException("other");
  96. 	        }
  97.  
  98. 	        ICollection<T> sourceCollection = source as ICollection<T> ?? source.ToArray();
  99. 	        ICollection<T> otherCollection = other as ICollection<T> ?? other.ToArray();
  100.  
  101. 	        if (sourceCollection.Count != otherCollection.Count) {
  102. 	            return false;
  103. 	        }
  104.  
  105. 	        if (sourceCollection.Except(otherCollection, comparer).Any()) {
  106. 	            return false;
  107. 	        }
  108.  
  109. 	        if (otherCollection.Except(sourceCollection, comparer).Any()) {
  110. 	            return false;
  111. 	        }
  112.  
  113. 	        return true;
  114. 	    }
  115. 	}
  116.  
  117. 	class MySolution : ISolution
  118. 	{
  119. 	    public bool SetEqual<T>(IEnumerable<T> source, IEnumerable<T> other, IEqualityComparer<T> comparer = null)
  120. 	    {
  121. 	        if (source == null)
  122. 	        {
  123. 	            return other == null;
  124. 	        }
  125.  
  126. 	        if (other == null)
  127. 	        {
  128. 	            return false;
  129. 	        }
  130.  
  131. 	        int sourceLength = source.Count();
  132. 	        int otherLength = other.Count();
  133.  
  134. 	        if (sourceLength != otherLength)
  135. 	        {
  136. 	            return false;
  137. 	        }
  138.  
  139. 	        // Create our dictionary.
  140. 	        // Keys - 'source' elements.
  141. 	        // Values - their counts in the 'source'.
  142. 	        Dictionary<T, int> counts = comparer == null
  143. 	            ? new Dictionary<T, int>(sourceLength)
  144. 	            : new Dictionary<T, int>(sourceLength, comparer);
  145.  
  146. 	        // Fill the dictionary with 'source' items and their counts:
  147. 	        foreach(T item in source)
  148. 	        {
  149. 	            int value;
  150. 	            if (counts.TryGetValue(item, out value))
  151. 	                counts[item] = value + 1;  // Item already exists? Add 1 to counts.
  152. 	            else
  153. 	                counts.Add(item, 1); // Add new item with count = 1.
  154. 	        }
  155.  
  156. 	        // Remove `other` items from the dictionary:
  157. 	        foreach (T item in other)
  158. 	        {
  159. 	            int value;
  160. 	            if (counts.TryGetValue(item, out value))
  161. 	            {
  162.                     if (value == 1)  // If the count == 1, remove the item from the dictionary
  163.                         counts.Remove(item);
  164.                     else  // If the item exists, decrease its count:
  165.                         counts[item] = value - 1;
  166. 	            }
  167. 	            else
  168. 	            {
  169. 	                // No such item? Collections are not equal.
  170. 	                return false;
  171. 	            }
  172. 	        }
  173.  
  174. 	        // Is there any items left in the dictionary?
  175. 	        // If no, collections are equal.
  176. 	        return counts.Count == 0;
  177. 		}
  178. 	}
  179. 	class ListSolution : ISolution
  180. 	{
  181. 	    public bool SetEqual<T>(IEnumerable<T> source, IEnumerable<T> other, IEqualityComparer<T> comparer = null)
  182. 	    {
  183.             if (source == null)
  184.             {
  185.                 return other == null;
  186.             }
  187.  
  188.             if (other == null)
  189.             {
  190.                 return false;
  191.             }
  192.  
  193.             ICollection<T> sourceCollection = source as ICollection<T>;
  194.             ICollection<T> otherCollection = other as ICollection<T>;
  195.  
  196.             if (sourceCollection != null && otherCollection != null)
  197.             {
  198.                 if (sourceCollection.Count != otherCollection.Count)
  199.                 {
  200.                     return false;
  201.                 }
  202.             }
  203.  
  204.             IList<T> sourceList = new List<T>(source);
  205.  
  206.             foreach (T item in other)
  207.             {
  208.                 if (!sourceList.Remove(item)) { return false; }
  209.             }
  210.             return sourceList.Count == 0;
  211. 	    }
  212. 	}
  213. }
Success #stdin #stdout 4.02s 35264KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
20 / 20: 00:00:00.1015607
20 / 20: 00:00:00.0620284
20 / 20: 00:00:03.7846245
https://ideone.com/CSRMdc
language:
C# (gmcs 5.20.1)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!