WP7/DataStructure/Algorithm/C#/and more…

Project Euler problem 95~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The smallest member of the longest amicable chain: ");
  6: 
  7:             //TestBenchSetup(); // since theres parallel code
  8:             TestBenchLoader(calculate_divisors_sum_using_sieve_and_find_out_longest_chain_in_parallel);
  9: 
 10:             Console.WriteLine("Press any key to exit");
 11:             Console.ReadKey();
 12:         }
 13: 
 14:         static int calculate_divisors_sum_using_sieve_and_find_out_longest_chain_in_parallel()
 15:         {
 16:             var max = 1000000;
 17:             var sum_map = new int[max + 1];
 18:             var bound = (int)Math.Sqrt(max);
 19:             int n, d, q;
 20:             // since the sieve method will not be able to encounter 1, so add 1 to every number's divisor sum first
 21:             for (n = 1; n <= max; n++)
 22:             {
 23:                 sum_map[n]++;
 24:             }
 25:             // sieve for calculating sum of divisors for each number 
 26:             for (d = 2; d <= bound; d++)
 27:             {
 28:                 n = d * d;
 29:                 sum_map[n] += d;
 30:                 for (n = n + d, q = d + 1; n <= max; n += d, q++)
 31:                 {
 32:                     sum_map[n] += (d + q);
 33:                 }
 34:             }
 35:             // find out the chain length for each number in parallel and record the longest chain number and its min
 36:             var THREAD_COUNT = Environment.ProcessorCount - 1;
 37:             var wait_handles = Enumerable.Range(0, THREAD_COUNT).Select(w => new AutoResetEvent(false)).ToArray();
 38:             var results = new int[THREAD_COUNT];
 39:             for (int i = 0; i < THREAD_COUNT; i++)
 40:             {
 41:                 ThreadPool.QueueUserWorkItem(o =>
 42:                 {
 43:                     var nth = (int)o;
 44:                     var longest = new HashSet<int>();
 45:                     var longest_num = 0;
 46:                     for (int num = nth; num <= max; num += THREAD_COUNT)
 47:                     {
 48:                         var accum = new HashSet<int>();
 49:                         var cur = num;
 50:                         while (accum.Add(cur) == true && cur <= max)
 51:                         {
 52:                             cur = sum_map[cur];
 53:                         }
 54:                         if (cur == num && accum.Count > longest.Count)
 55:                         {
 56:                             longest = accum;
 57:                             longest_num = num;
 58:                         }
 59:                     }
 60:                     results[nth] = longest.Min();
 61:                     wait_handles[nth].Set();
 62:                 }, i);
 63:             }
 64:             for (int i = 0; i < THREAD_COUNT; i++)
 65:             {
 66:                 wait_handles[i].WaitOne();
 67:             }
 68:             return results.Min();
 69:         }
 70: 
 71:         static Stopwatch stopwatch = new Stopwatch();
 72:         static void TestBenchSetup()
 73:         {
 74:             // Uses the second Core or Processor for the Test
 75:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
 76:             // Prevents "Normal" processes from interrupting Threads
 77:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
 78:             // Prevents "Normal" Threads from interrupting this thread
 79:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
 80:         }
 81:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
 82:         static void TestBenchLoader(Func<int> test_method)
 83:         {
 84:             stopwatch.Reset();
 85:             stopwatch.Start();
 86:             var result = 0;
 87:             long avg_tick = 0;
 88:             long avg_ms = 0;
 89:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
 90:             // stabilizes the CPU cache and pipeline.
 91:             {
 92:                 result = test_method(); // Warmup
 93:             }
 94:             stopwatch.Stop();
 95:             for (int repeat = 0; repeat < 20; ++repeat)
 96:             {
 97:                 stopwatch.Reset();
 98:                 stopwatch.Start();
 99:                 result = test_method();
100:                 stopwatch.Stop();
101:                 avg_tick += stopwatch.ElapsedTicks;
102:                 avg_ms += stopwatch.ElapsedMilliseconds;
103:             }
104:             avg_tick = avg_tick / 20;
105:             avg_ms = avg_ms / 20;
106:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
107:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
108:         }
109:     }

c++

Advertisements
This entry was posted in Programming. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s