fork download
copy 
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Diagnostics;
  4. using System.Linq;
  5. using System.Text;
  6. using System.Threading;
  7. using System.Threading.Tasks;
  8.  
  9. public class Test
  10. {
  11. 	class Program
  12.     {
  13.         public static Mutex mux = new Mutex();
  14.         static void Main(string[] args)
  15.         {
  16.             int number = 10000000;
  17.             //int number = 10000;
  18.             //int number = 100;
  19.             var sw = Stopwatch.StartNew();
  20.  
  21.             int testIterations = 100;
  22.             //int testIterations = 100000;
  23.             //int testIterations = 1000000;
  24.  
  25.             int testCount = 0;
  26.  
  27.             while (testCount++ < testIterations)
  28.             {
  29.                 //parallel(number);
  30.                 //parallelNoList(number);
  31.                 //notParallel(number);
  32.                 //opSolution2(number);                
  33.                 //counting(number);
  34.                 //multiPersonalize(number);
  35.                 //multi(number, new[] { 3, 5 });
  36.                 //multiPersonalizeEnhanted(number);
  37.                 //multiEnhanted(number, new[] { 3, 5 });
  38.                 unrolled(number);
  39.             }
  40.  
  41.             sw.Stop();
  42.             Console.Write("Elapsed " + sw.ElapsedMilliseconds / testCount + "ms"); //avr
  43.             //Console.Write("Elapsed " + sw.ElapsedMilliseconds + "ms"); //total
  44.  
  45.             Console.ReadKey();
  46.         }
  47.  
  48.         static List<int> parallel(int limit)       //434ms, 85447ms , 348600ms
  49.         {
  50.             return Enumerable.Range(0, limit+1).AsParallel().Where(n => n % 3 == 0 || n % 5 == 0).OrderBy(x => x).ToList();
  51.         }
  52.  
  53.         static List<int> parallelEnhanted(int limit)   
  54.         {
  55.             List<int> finalResult = new List<int>();
  56.             var result = Enumerable.Range(0, limit + 1).AsParallel().Where(n => n % 3 == 0 || n % 5 == 0).OrderBy(x => x);
  57.             result.ForAll(x => 
  58.             {
  59.                 //mux.WaitOne();
  60.                 finalResult.Add(x);
  61.                 //mux.ReleaseMutex();
  62.             });
  63.             return finalResult;
  64.         }
  65.  
  66.         static void parallelNoList(int limit)      //136ms, 51266ms, 273409ms
  67.         {
  68.             Enumerable.Range(0, limit+1).AsParallel().Where(n => n % 3 == 0 || n % 5 == 0).OrderBy(x => x).ForAll(x => { });
  69.         }
  70.  
  71.         static List<int> notParallel(int number)     //154ms, 14559ms, 1985ms
  72.         {
  73.             return Enumerable.Range(0, number+1).Where(n => n % 3 == 0 || n % 5 == 0).ToList();
  74.         }
  75.  
  76.         static List<int> opSolution2(int number)        //69ms, 5791ms, 879ms
  77.         {
  78.             List<int> list = new List<int>();
  79.             for (var i = 0; i <= number; i++)
  80.             {
  81.                 if (i % 3 == 0 || i % 5 == 0)
  82.                 {
  83.                     list.Add(i);
  84.                 }
  85.             }
  86.             return list;
  87.         }
  88.  
  89.         static List<int> counting(int number)        //34ms, 2398ms, 521ms
  90.         {
  91.             List<int> list = new List<int> { 0 };
  92.             int count3 = 0;
  93.             int count5 = 0;
  94.             int step3 = 3;
  95.             int step5 = 5;
  96.             while (count3 < number || count5 < number)
  97.             {
  98.                 if ((count3 + step3) <= (count5 + step5))
  99.                 {
  100.                     count3 += step3;
  101.  
  102.                     if(count3 == (count5 + step5)) count5 += step5;
  103.  
  104.                     if (count3 <= number)
  105.                     {
  106.                         list.Add(count3);
  107.                     }
  108.                 }
  109.                 else
  110.                 {
  111.                     count5 += step5;
  112.                     if (count5 <= number)
  113.                     {
  114.                         list.Add(count5);
  115.                     }
  116.                 }
  117.  
  118.             }
  119.             return list;
  120.         }
  121.  
  122.         static List<int> unrolled(int max)      //32ms, 2072ms, 464ms
  123.         {
  124.             List<int> result = new List<int> { 0 };
  125.  
  126.             int i = 0;
  127.             while (true)
  128.             {
  129.                 i += 3;
  130.                 if (i > max) break;
  131.                 result.Add(i);
  132.                 i += 2;
  133.                 if (i > max) break;
  134.                 result.Add(i);
  135.                 i += 1;
  136.                 if (i > max) break;
  137.                 result.Add(i);
  138.                 i += 3;
  139.                 if (i > max) break;
  140.                 result.Add(i);
  141.                 i += 1;
  142.                 if (i > max) break;
  143.                 result.Add(i);
  144.                 i += 2;
  145.                 if (i > max) break;
  146.                 result.Add(i);
  147.                 i += 3;
  148.                 if (i > max) break;
  149.                 result.Add(i);
  150.             }
  151.  
  152.             return result;
  153.         }
  154.  
  155.         static List<int> multiPersonalizeEnhanted(int max)      //37ms, 2655ms, 501ms
  156.         {
  157.             int[] deltas = { 3, 2, 1, 3, 1, 2, 3 };
  158.  
  159.             List<int> result = new List<int> { 0 };
  160.  
  161.             int i = 0;
  162.             do
  163.             {
  164.                 foreach (int delta in deltas)
  165.                 {
  166.                     i += delta;
  167.                     if (i > max) break;
  168.                     result.Add(i);
  169.                 }
  170.             } while (i < max);
  171.  
  172.             return result;
  173.         }
  174.  
  175.         static List<int> multiPersonalize(int max)      //43ms, 3498ms, 654ms
  176.         {
  177.             int[] deltas = { 3, 2, 1, 3, 1, 2, 3 };
  178.  
  179.             List<int> result = new List<int>();
  180.  
  181.             int j = 0;
  182.             for (int i = 0; i <= max; i += deltas[j++ % deltas.Length])
  183.             {
  184.                 result.Add(i);
  185.             }
  186.  
  187.             return result;
  188.         }
  189.  
  190.         static List<int> multiEnhanted(int max, int[] divs)      //37ms, 2701ms, 1149ms
  191.         {
  192.             int[] deltas = calcDeltas(divs);
  193.  
  194.             List<int> result = new List<int> { 0 };
  195.  
  196.             int i = 0;
  197.             do
  198.             {
  199.                 foreach (int delta in deltas)
  200.                 {
  201.                     i += delta;
  202.                     if (i > max) break;
  203.                     result.Add(i);
  204.                 }
  205.             } while (i < max);
  206.  
  207.             return result;
  208.         }
  209.  
  210.         static List<int> multi(int max, int[] divs)      //47ms, 3529ms, 1270ms
  211.         {                                              
  212.             int[] deltas = calcDeltas(divs);
  213.  
  214.             List<int> result = new List<int>();
  215.  
  216.             int j = 0;
  217.             for (int i = 0; i <= max; i += deltas[j++ % deltas.Length])
  218.             {
  219.                 result.Add(i);
  220.             }
  221.  
  222.             return result;
  223.         }
  224.  
  225.         static int[] calcDeltas(int[] divs)
  226.         {
  227.             long max = 1;
  228.             foreach (int div in divs)
  229.                 max = lcm(max, div);
  230.  
  231.             List<long> ret = new List<long>();
  232.  
  233.             foreach (int div in divs)
  234.             {
  235.                 for (int i = div; i <= max; i += div)
  236.                 {
  237.                     int idx = ret.BinarySearch(i);
  238.                     if (idx < 0)
  239.                     {
  240.                         ret.Insert(~idx, i);
  241.                     }
  242.                 }
  243.             }
  244.  
  245.             for (int i = ret.Count - 1; i > 0; i--)
  246.                 ret[i] -= ret[i - 1];
  247.  
  248.             return ret.ConvertAll(x => (int)x).ToArray();
  249.         }
  250.  
  251.         static long gcf(long a, long b)
  252.         {
  253.             while (b != 0)
  254.             {
  255.                 long temp = b;
  256.                 b = a % b;
  257.                 a = temp;
  258.             }
  259.             return a;
  260.         }
  261.  
  262.         static long lcm(long a, long b)
  263.         {
  264.             return (a / gcf(a, b)) * b;
  265.         }
  266.  
  267.     }
  268. }
Success #stdin #stdout 2.7s 131648KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Elapsed 26ms
https://ideone.com/lUjP2e
language:
C# (gmcs 5.20.1)
created:
8 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!