fork(2) download
copy 
  1. using System;
  2. using System.Collections;
  3. using System.Collections.Generic;
  4. using System.Diagnostics;
  5. using System.Linq;
  6.  
  7. public class Test
  8. {
  9. 	public static void Main()
  10. 	{
  11. 		var candidates = new Dictionary<string, Func<IEnumerable<IEnumerable<int>>, IEnumerable<int>>>
  12. 			{
  13. 				{ "Original", Candidates.UOIOriginal<int> },
  14. 				{ "DoomerOneLine", Candidates.UOIDoomerOneLine<int> },
  15. 				{ "DoomerSqlLike", Candidates.UOIDoomerSqlLike<int> },
  16. 				{ "Schmelter", Candidates.UOISchmelter<int> },
  17. 				{ "Svinja", Candidates.UOISvinja<int> },
  18. 				{ "Adricadar", Candidates.UOIAdricadar<int> },
  19.  
  20. 			};
  21.  
  22. 		var testData = new int[][][]
  23. 			{
  24. 				new int[][]
  25. 				{
  26. 					new[] { 1, 1, 2, 3, 4, 5, 7 },
  27. 					new[] { 5, 6, 7 },
  28. 					new[] { 2, 6, 7, 9 },
  29. 					new[] { 4 }
  30. 				},
  31. 				new int[][]
  32. 				{
  33. 					new[] { 1, 2, 3 }
  34. 				},
  35. 				new int[][]
  36. 				{
  37. 					new int[0] 
  38. 				},
  39. 				new int[][]
  40. 				{}
  41. 			};
  42.  
  43. 		var validResult = new[] { 2, 4, 5, 6, 7 };
  44.  
  45. 		var results = new IEnumerable<int>[1000];
  46.  
  47. 		foreach(var pair in candidates)
  48. 		{
  49. 			var valid = true;
  50. 			for (var i = 0; i < testData.Length; i++)
  51. 			{
  52. 				if (i == 0)
  53. 				{
  54. 					var timer = Stopwatch.StartNew();
  55. 					valid = pair.Value(testData[i]).OrderBy(d => d).SequenceEqual(validResult);
  56. 					timer.Stop();
  57. 				}
  58. 				else
  59. 				{
  60. 					valid = pair.Value(testData[i]).OrderBy(d => d).SequenceEqual(new int[0]);	
  61. 				}
  62.  
  63. 				if (!valid)
  64. 				{
  65. 					break;
  66. 				}
  67. 			}
  68.  
  69. 			Console.WriteLine("{0} valid:{1}", pair.Key, valid);
  70. 		}
  71.  
  72. 		foreach(var pair in candidates)
  73. 		{
  74. 			var valid = true;
  75. 			var timer = Stopwatch.StartNew();
  76. 			for (var i = 0; i < 100000; i++)
  77. 			{
  78. 				results[i % 1000] = pair.Value(testData[0]);
  79. 			}
  80. 			timer.Stop();
  81.  
  82. 			Console.WriteLine("{0} 100000 iterations in {1}ms", pair.Key, timer.ElapsedMilliseconds);
  83. 		}
  84. 	}
  85. }
  86.  
  87. public static class Candidates
  88. {
  89. 	public static IEnumerable<T> UOIOriginal<T>(
  90.                                   IEnumerable<IEnumerable<T>> source)
  91. 	{
  92. 		var pairs =
  93.             from s1 in source
  94.             from s2 in source
  95.             select new { s1 , s2 };
  96.  
  97.     	var intersects = pairs
  98.         	.Where(p => p.s1 != p.s2)
  99.         	.Select(p => p.s1.Intersect(p.s2));
  100.  
  101.     	return intersects.SelectMany(i => i).Distinct();
  102. 	}
  103.  
  104. 	public static IEnumerable<T> UOIDoomerOneLine<T>(
  105.                                   IEnumerable<IEnumerable<T>> source)
  106. 	{
  107. 		return source
  108. 			.SelectMany(e => e.Distinct())
  109.     		.GroupBy(e => e)
  110.     		.Where(e => e.Count() > 1)
  111.     		.Select(e => e.Key);
  112. 	}
  113.  
  114. 	public static IEnumerable<T> UOIDoomerSqlLike<T>(
  115.                                   IEnumerable<IEnumerable<T>> source)
  116. 	{
  117. 		return from e in source.SelectMany(e => e.Distinct())
  118.           group e by e into g
  119.           where g.Count() > 1
  120.           orderby g.Key
  121.           select g.Key;
  122. 	}
  123.  
  124. 	public static IEnumerable<T> UOISvinja<T>(
  125.                                   IEnumerable<IEnumerable<T>> source)
  126. 	{
  127. 		var seenElements = new HashSet<T>();
  128.         var repeatedElements = new HashSet<T>();
  129.  
  130.         foreach (var list in source)
  131.         {
  132.             foreach (var element in list.Distinct())
  133.             {
  134.                 if (seenElements.Contains(element))
  135.                 {
  136.                     repeatedElements.Add(element);
  137.                 }
  138.                 else
  139.                 {
  140.                     seenElements.Add(element);
  141.                 }
  142.             }
  143.         }
  144.  
  145.         return repeatedElements;
  146. 	}
  147.  
  148. 	public static IEnumerable<T> UOIAdricadar<T>(
  149.                                   IEnumerable<IEnumerable<T>> source)
  150. 	{
  151. 		var result = new List<T>();
  152. 	    var sequences = source.ToList();
  153. 	    for (int sequenceIdx = 0; sequenceIdx < sequences.Count(); sequenceIdx++)
  154. 	    {
  155. 	        var sequence = sequences[sequenceIdx];
  156.  
  157. 	        for (
  158. 	        		int targetSequenceIdx = sequenceIdx + 1; 
  159. 	        		targetSequenceIdx < sequences.Count; 
  160. 	        		targetSequenceIdx++)
  161. 	        {
  162. 	            var targetSequence = sequences[targetSequenceIdx];
  163. 	            var intersections = sequence.Intersect(targetSequence);
  164. 	            result.AddRange(intersections);
  165. 	        }
  166. 	    }
  167.  
  168. 	    return result.Distinct();
  169. 	}
  170.  
  171. 	public static IEnumerable<T> UOISchmelter<T>(
  172.                                   IEnumerable<IEnumerable<T>> source)
  173. 	{
  174. 		const int minCount = 2;
  175. 		var comparer = EqualityComparer<T>.Default;
  176. 	    foreach (T item in source.SelectMany(s => s).Distinct(comparer))
  177. 	    {
  178. 	        int containedInHowManySequences = 0;
  179. 	        foreach (IEnumerable<T> seq in source)
  180. 	        {
  181. 	            bool contained = seq.Contains(item, comparer);
  182. 	            if (contained) containedInHowManySequences++;
  183. 	            if (containedInHowManySequences == minCount)
  184. 	            {
  185. 	                yield return item;
  186. 	                break;
  187. 	            }
  188. 	        }
  189. 	    }
  190. 	}
  191. }
Success #stdin #stdout 2.01s 30192KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Original valid:True
DoomerOneLine valid:True
DoomerSqlLike valid:True
Schmelter valid:True
Svinja valid:True
Adricadar valid:True
Original 100000 iterations in 80ms
DoomerOneLine 100000 iterations in 57ms
DoomerSqlLike 100000 iterations in 81ms
Schmelter 100000 iterations in 9ms
Svinja 100000 iterations in 868ms
Adricadar 100000 iterations in 830ms
https://ideone.com/YAHeJE
language:
C# (gmcs 5.20.1)
created:
10 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!