Algorithm/DataStructure/F#/SL/and more…

Project Euler problem 74~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The number of chains contain exactly sixty non-repeating terms: ");
  6:             
  7:             TestBenchLoader(parallel_version_of_brute_force_with_memoization);
  8:             TestBenchSetup(); // moved to here so it wont hinder the multithreaded version 
  9:             TestBenchLoader(brute_force_with_memoization_for_chain_length);
 10: 
 11:             Console.WriteLine("Press any key to exit");
 12:             Console.ReadKey();
 13:         }
 14: 
 15:         /// <summary>
 16:         /// bascially brute force every number to find out its chain length. with the lep of 
 17:         /// memoization, a lot more calculation and drilling down the chains are avoided.
 18:         /// see tracer method for detail
 19:         /// </summary>
 20:         static int brute_force_with_memoization_for_chain_length()
 21:         {
 22:             var result = 0;
 23:             var cache = new Dictionary<int, int>();
 24:             for (int i = 2; i < 1000000; i++)
 25:             {
 26:                 if (tracer(i, i, 0, 0, cache) == 60)
 27:                     result++;
 28:             }
 29:             return result;
 30:         }
 31: 
 32:         /// <summary>
 33:         /// he parallel version of the previous method(7 concurrent thread via threadpool, pick 7 cuz i have 8 cores)
 34:         /// decided to let every concurent work unit to have its own cache, since i dont want to deal with locking the shared cache.
 35:         /// On the down side the memoization would not be as effective.(locking vs cache hit + calculation. Didnt try any benchmark
 36:         /// comparsion, so im not sure) (about 4 times faster than single threaded version)
 37:         /// </summary>
 38:         static int parallel_version_of_brute_force_with_memoization()
 39:         {
 40:             var work_items = Enumerable.Range(0, 7)
 41:                 .Select(w => new WorkItem()
 42:                 {
 43:                     index = w,
 44:                     result = 0,
 45:                     signal = new AutoResetEvent(false)
 46:                 }).ToList();
 47:             foreach (var item in work_items)
 48:             {
 49:                 ThreadPool.QueueUserWorkItem((o) =>
 50:                 {
 51:                     var cache = new Dictionary<int, int>();
 52:                     var work_item = o as WorkItem;
 53:                     var i = work_item.index;
 54:                     while (i < 1000000)
 55:                     {
 56:                         if (tracer(i, i, 0, 0, cache) == 60)
 57:                             work_item.result++;
 58:                         i += 7;
 59:                     }
 60:                     work_item.signal.Set();
 61:                 }, item);
 62:             }
 63:             var total = 0;
 64:             work_items.ForEach(w => { w.signal.WaitOne(); total += w.result; });
 65:             return total;
 66:         }
 67: 
 68:         /// <summary>
 69:         /// basically the recursive method that drills down the chain and stops when repeated pattern is found.
 70:         /// since the question stated that pattern's dept at most is 3. so r1, r2, and r3 is used to save previous
 71:         /// 3 numbers in the chain. memoization is used(the cache variable)
 72:         /// </summary>
 73:         static int tracer(int num, int r1, int r2, int r3, Dictionary<int, int> cache)
 74:         {
 75:             if (cache.ContainsKey(num))
 76:                 return cache[num];
 77:             else
 78:             {
 79:                 var digit_sum = calculate_digits_sum(num);
 80:                 if (digit_sum == r1 || digit_sum == r2 || digit_sum == r3)
 81:                     return 1;
 82: 
 83:                 if (r1 == 0) // since sum of digits factorial can never be zero, this is a good way to start the initial accumulation
 84:                     r1 = digit_sum;
 85:                 else if (r2 == 0)
 86:                     r2 = digit_sum;
 87:                 else if (r3 == 0)
 88:                     r3 = digit_sum;
 89:                 else
 90:                 {
 91:                     r1 = r2;
 92:                     r2 = r3;
 93:                     r3 = digit_sum;
 94:                 }
 95:                 return (cache[num] = 1 + tracer(digit_sum, r1, r2, r3, cache));
 96:             }
 97:         }
 98: 
 99:         class WorkItem
100:         {
101:             public int index;
102:             public int result;
103:             public AutoResetEvent signal;
104:         }
105: 
106:         // precalculate each digit's factorial sum
107:         static int[] factorial_map =
108:             Enumerable.Range(0, 10).Select(n => n == 0 ? 1 : Enumerable.Range(1, n).Aggregate((a, b) => a *= b)).ToArray();
109: 
110:         /// <summary>
111:         /// break down num into digits and sum up each digit's factorial sum
112:         /// </summary>
113:         static int calculate_digits_sum(int num)
114:         {
115:             var rem = 0;
116:             var sum = 0;
117:             while (num > 0)
118:             {
119:                 num = Math.DivRem(num, 10, out rem);
120:                 sum += factorial_map[rem];
121:             }
122:             return sum;
123:         }
124: 
125:         static Stopwatch stopwatch = new Stopwatch();
126:         static void TestBenchSetup()
127:         {
128:             // Uses the second Core or Processor for the Test
129:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
130:             // Prevents "Normal" processes from interrupting Threads
131:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
132:             // Prevents "Normal" Threads from interrupting this thread
133:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
134:         }
135:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
136:         static void TestBenchLoader(Func<int> test_method)
137:         {
138:             stopwatch.Reset();
139:             stopwatch.Start();
140:             var result = 0;
141:             long avg_tick = 0;
142:             long avg_ms = 0;
143:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
144:             // stabilizes the CPU cache and pipeline.
145:             {
146:                 result = test_method(); // Warmup
147:             }
148:             stopwatch.Stop();
149:             for (int repeat = 0; repeat < 20; ++repeat)
150:             {
151:                 stopwatch.Reset();
152:                 stopwatch.Start();
153:                 result = test_method();
154:                 stopwatch.Stop();
155:                 avg_tick += stopwatch.ElapsedTicks;
156:                 avg_ms += stopwatch.ElapsedMilliseconds;
157:             }
158:             avg_tick = avg_tick / 20;
159:             avg_ms = avg_ms / 20;
160:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
161:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
162:         }
163:     }

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