fork download
copy 
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Diagnostics;
  4.  
  5. public class Test
  6. {
  7.     public static void Main()
  8.     {
  9. 		List<int> results;
  10. 		List<int> m;
  11. 		List<int> n;
  12.         int x;
  13.         Stopwatch sw;
  14.  
  15.         // warmup
  16.         results = new List<int>(200);
  17.         for(x = 0; x < 100; x++) {
  18.         	results.Add(SortedExcept(Make(10, 13), Make(100, 7)).Count);
  19.         	results.Add(SortedExcept(Make(10, 13), Make(100, 7)).Count);
  20.         }
  21.  
  22.         // test M * Ln(N)
  23.         sw = new Stopwatch();
  24.         results = new List<int>(200);
  25.         m = Make(50, 3);
  26.         n = Make(10000000, 2);
  27.         sw.Start();
  28.         for(x = 0; x < 100; x++) {
  29.         	results.Add(SortedExcept(m, n).Count);
  30.         	results.Add(SortedExcept(m, n).Count);
  31.         }
  32.         sw.Stop();
  33.         Console.WriteLine("M * LN( N ) : " + results[0]);
  34.         Console.WriteLine(sw.Elapsed.TotalSeconds.ToString());
  35.  
  36. 		// test N * Ln(M)
  37.         sw = new Stopwatch();
  38.         results = new List<int>(200);
  39.         m = Make(10000000, 2);
  40.         n = Make(50, 3);
  41.         sw.Start();
  42.         for(x = 0; x < 100; x++) {
  43.         	results.Add(SortedExcept(n, m).Count);
  44.         	results.Add(SortedExcept(n, m).Count);
  45.         }
  46.         sw.Stop();
  47.         Console.WriteLine("N * LN( M ) : " + results[0]);
  48.         Console.WriteLine(sw.Elapsed.TotalSeconds.ToString());
  49.  
  50. 		// test M + N
  51. 		sw = new Stopwatch();
  52.         results = new List<int>(200);
  53.         m = Make(50, 3);
  54.         n = Make(10000000, 2);
  55.         sw.Start();
  56.         for(x = 0; x < 100; x++) {
  57.         	results.Add(SortedExcept2(m, n).Count);
  58.         	results.Add(SortedExcept2(m, n).Count);
  59.         }
  60.         sw.Stop();
  61.         Console.WriteLine("M + N : " + results[0]);
  62.         Console.WriteLine(sw.Elapsed.TotalSeconds.ToString());
  63.     }
  64.  
  65.     public static List<int> Make(int size, int stride) {
  66.     	List<int> result = new List<int>();
  67.     	for(int i = 0, x = 0; x < size; i+=stride, x++) { 
  68.             result.Add(i);
  69.         }
  70.         return result;
  71.     }
  72.  
  73.     public static List<T> SortedExcept<T>(List<T> m, List<T> n) {
  74.         var result = new List<T>();
  75.         int i, index;
  76.         for(i = 0; i < m.Count; i++) {
  77.             index = n.BinarySearch(m[i]);
  78.             if(index < 0) { 
  79.                 result.Add(m[i]); 
  80.             }
  81.         }
  82.         return result;
  83.     }
  84.  
  85.     public static List<T> SortedExcept2<T>(List<T> m, List<T> n) where T : IComparable<T> {
  86.         var result = new List<T>();
  87.         int i = 0, j = 0;
  88.         if(n.Count == 0) {
  89.         	result.AddRange(m);
  90.         	return result;
  91.         }
  92.         while(i < m.Count) {
  93.         	if(m[i].CompareTo(n[j]) < 0) {
  94.         		result.Add(m[i]);
  95.         		i++;
  96.         	} else if(m[i].CompareTo(n[j]) > 0) {
  97.         		j++;
  98.         	} else {
  99.         		i++;
  100.         	}
  101.         	if(j >= n.Count) {
  102.         		for(; i < m.Count; i++) { 
  103.         			result.Add(m[i]); 
  104.         		}
  105. 				break;
  106.         	}
  107.         }
  108.         return result;
  109.     }
  110. }
Success #stdin #stdout 0.76s 24104KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
M * LN( N ) : 25
0.006553
N * LN( M ) : 25
0.0063569
M + N : 25
0.0020164
https://ideone.com/Y2oEQD
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!