HashSet/Pattern/C#/and more…

Project Euler problem 44~

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The smallest pair of pentagonal numbers whose sum and difference is pentagonal:");
  6: 
  7:             //TestBenchSetup();
  8:             TestBenchLoader(brute_force_with_precal_pentagonals_and_loop_every_combination);
  9:             TestBenchLoader(parallel_version_with_on_fly_check_for_sum_and_diff);
 10: 
 11:             Console.WriteLine("Press any key to exit");
 12:             Console.ReadKey();
 13:         }
 14: 
 15:         /// <summary>
 16:         /// pre-calculate all the pentagonal numbers to 3000 (randomly picked) and save to hashset
 17:         /// loop through all possible combinations and return 1st result as answer.
 18:         /// as to why 1st result happens to be the answer? i am not sure
 19:         /// Originally i thought this question has something to do with pentagonal number theorem
 20:         /// (http://en.wikipedia.org/wiki/Pentagonal_number_theorem), but i guess not.
 21:         /// </summary>
 22:         /// <returns></returns>
 23:         static int brute_force_with_precal_pentagonals_and_loop_every_combination()
 24:         {
 25:             Func<int, int> pn = (n) => n * (3 * n - 1) / 2;
 26:             var numbers = new HashSet<int>();
 27:             Enumerable.Range(1, 3000)
 28:                 .Select(l => pn(l))
 29:                 .ToList()
 30:                 .ForEach(l => numbers.Add(l));
 31: 
 32:             foreach (var j in numbers)
 33:             {
 34:                 foreach (var k in numbers)
 35:                 {
 36:                     if (numbers.Contains(j + k) && numbers.Contains(Math.Abs(j - k)))
 37:                         return Math.Abs(j - k);
 38:                 }
 39:             }
 40: 
 41:             return 0;
 42:         }
 43: 
 44:         /// <summary>
 45:         /// the parallelized version. the only differences are the following:
 46:         /// 1. didnt use pre-calculated hashset, the hashset contain part make the whole thing even slower than linear way
 47:         /// 2. using the forumla to check sum and diff (http://en.wikipedia.org/wiki/Pentagonal_number)
 48:         /// 3. interesting read on how to check if sqrt of a number is natural or not
 49:         ///    (http://stackoverflow.com/questions/295579), ah the John Carmack hack, read about it
 50:         ///    on hacker news, still not sure who was the original author of that magical number
 51:         /// 4. only slightly faster compared with linear way: 120ish vs 88ish
 52:         /// </summary>
 53:         /// <returns></returns>
 54:         static int parallel_version_with_on_fly_check_for_sum_and_diff()
 55:         {
 56:             var limit = 3000;
 57:             var size = limit / 7;
 58:             var list = Enumerable.Range(1, limit)
 59:                 .Select(n => n * (3 * n - 1) / 2).ToList<int>();
 60:             var work_items = Enumerable.Range(1, 7)
 61:                 .Select(l => new WorkItem
 62:                     {
 63:                         from = l == 1 ? 0 : (l - 1) * size + 1,
 64:                         to = l == 7 ? limit - 1 : l * size,
 65:                         signal = new AutoResetEvent(false),
 66:                         result = int.MaxValue
 67:                     }).ToList();
 68:             foreach (var item in work_items)
 69:             {
 70:                 ThreadPool.QueueUserWorkItem((o) =>
 71:                 {
 72:                     int i, j;
 73:                     double sum, diff;
 74:                     var found = false;
 75:                     var work_item = o as WorkItem;
 76:                     for (i = work_item.from; i <= work_item.to; i++)
 77:                     {
 78:                         j = list[i];
 79:                         foreach (var k in list)
 80:                         {
 81:                             sum = (Math.Sqrt(24 * (j + k) + 1) + 1) / 6;
 82:                             diff = (Math.Sqrt(24 * Math.Abs(j - k) + 1) + 1) / 6;
 83:                             if (sum - (int)sum < 0.00001 && diff - (int)diff < 0.00001)
 84:                             {
 85:                                 work_item.result = Math.Abs(j - k);
 86:                                 found = true;
 87:                                 break;
 88:                             }
 89:                         }
 90:                         if (found) break;
 91:                     }
 92:                     work_item.signal.Set();
 93:                 }, item);
 94:             }
 95:             var result = int.MaxValue;
 96:             work_items.ForEach(w => { w.signal.WaitOne(); result = w.result < result ? w.result : result; });
 97:             return result;
 98:         }
 99: 
100:         class WorkItem
101:         {
102:             public int from;
103:             public int to;
104:             public AutoResetEvent signal;
105:             public int result;
106:         }
107: 
108:         static Stopwatch stopwatch = new Stopwatch();
109:         static void TestBenchSetup()
110:         {
111:             // Uses the second Core or Processor for the Test
112:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
113:             // Prevents "Normal" processes from interrupting Threads
114:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
115:             // Prevents "Normal" Threads from interrupting this thread
116:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
117:         }
118:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
119:         static void TestBenchLoader(Func<int> test_method)
120:         {
121:             stopwatch.Reset();
122:             stopwatch.Start();
123:             var result = 0;
124:             long avg_tick = 0;
125:             long avg_ms = 0;
126:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
127:             // stabilizes the CPU cache and pipeline.
128:             {
129:                 result = test_method(); // Warmup
130:             }
131:             stopwatch.Stop();
132:             for (int repeat = 0; repeat < 20; ++repeat)
133:             {
134:                 stopwatch.Reset();
135:                 stopwatch.Start();
136:                 result = test_method();
137:                 stopwatch.Stop();
138:                 avg_tick += stopwatch.ElapsedTicks;
139:                 avg_ms += stopwatch.ElapsedMilliseconds;
140:             }
141:             avg_tick = avg_tick / 20;
142:             avg_ms = avg_ms / 20;
143:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
144:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
145:         }
146:     }

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