- Any dirty/cheap, lightweight 3d engine, beginner friendly out there ?
- Let the voting begin!
- SIMD optimization
- How to formulate such problem mathematicaly? (line continuation search)
- C# Diff Algorithm for Text
- How do you implement a “Did you mean”?
- What are some uses for linked lists?
- Your Software Can Learn A Lot From ATMs (Justin Etheredge)
- Advice to Aimless, Excited Programmers
- Windows Phone 7, Reactive Extensions, OData, MVVM – John P Alioto shares his experiences building a Windows Phone 7 application making use of MVVM and the Reactive Extensions for Silverlight to access an OData Data source.
- Multitouch Game Loop Inertia Processing
- What is the effect of the /LARGEADDRESSAWARE switch on a DLL?
- Differences between WPF and *Silverlight Rendering Stacks

`1: class Program`

2: {3: static void Main(string[] args)4: {`5: Console.WriteLine("The number of subset pairs that needed to be tested for equality: ");`

6:7: TestBenchSetup();8: TestBenchLoader(using_check_condition_method_from_problem_105_with_modification);9: TestBenchLoader(awesome_mathematical_analysis_with_DyckPath);10:`11: Console.WriteLine("press any key to exit");`

12: Console.ReadKey();13: }14:`15: /// <summary>`

`16: /// since the problem stated that condition ii is already satisifed, and the set contains`

`17: /// n strictly increasing elements.`

`18: /// to check condition i, only two set with equal number of elements would need to be checked`

`19: /// however, since the set is already in sorted order, the set which the ordinal element is always bigger than`

`20: /// the other set can be omitted. The rest of the pairs are the one that need to be compare and checked`

`21: /// </summary>`

22: static int using_check_condition_method_from_problem_105_with_modification()23: {24: var n = 12;25: var mask = new int[n];26: var map = new int[(int)Math.Pow(2, n), n];27: var pos = n - 1;28: var row = 0;29: var col = 0;30:`31: while (pos >= 0)`

32: {`33: if (mask[pos] == 0)`

34: {35: mask[pos] = 1;36: pos = n - 1;37:38: for (int i = 0; i < n; i++)39: {`40: if (mask[i] == 1)`

41: {42: map[row, i] = 1;43: }44: }45: row++;46: }`47: else`

48: {49: mask[pos] = 0;50: pos--;51: }52: }53:54: row = 0;55: col = 0;56: var cur = 0;`57: var bound = (int)Math.Pow(2, n) - 1;`

58: var half = n / 2;59: var result = 0;60: var src_set = new int[n];61: var dest_set = new int[n];`62: for (cur = 0; cur < bound; cur++)`

63: {64: var cur_count = 0;65:`66: // reset the set that holds current start set`

67: src_set[0] = 0; src_set[1] = 0; src_set[2] = 0;68: src_set[3] = 0; src_set[4] = 0; src_set[5] = 0;69:`70: // copy the current start set col index`

`71: for (col = 0; col < n; col++)`

72: {`73: if (map[cur, col] == 1)`

74: {75: src_set[cur_count] = col;76: cur_count++;77: }78: }79:`80: // no point to continue if current start set size is greater than half of the whole set`

`81: if (cur_count > half)`

`82: continue;`

83:`84: for (row = cur + 1; row < bound; row++)`

85: {86: var count = 0;`87: var disjoint = true;`

`88: var possible = false;`

`89: // reset the set that holds current destination set`

90: dest_set[0] = 0; dest_set[1] = 0; dest_set[2] = 0;91: dest_set[3] = 0; dest_set[4] = 0; dest_set[5] = 0;92:`93: for (col = 0; col < n; col++)`

94: {`95: if (map[row, col] == 1)`

96: {`97: if (map[cur, col] == 1 || count > cur_count)`

98: {`99: disjoint = false;`

`100: break;`

101: }102: dest_set[count] = col;`103: // if there are any element in dest set that are bigger than src set`

`104: // which means dest set is not strickly smaller than src set and comparsion is needed`

`105: if (dest_set[count] > src_set[count])`

106: {`107: possible = true;`

108: }109: count++;110: }111: }112: if (disjoint == true && possible == true && count > 1 && count == cur_count)113: {114: result++;115: }116: }117: }`118: return result;`

119: }120:`121: /// <summary>`

`122: /// saw this awesome way of solving this problem using dyck path`

`123: /// </summary>`

124: static int awesome_mathematical_analysis_with_DyckPath()125: {126: Func<int, int, int> C = (left, right) =>127: {`128: if (right > left)`

`129: return 0;`

130: var sum = 1;131: for (int i = 1; i <= right; i++)132: {133: sum = sum * (left - right + i) / i;134: }`135: return sum;`

136: };137:`138: int n = 12, result = 0;`

139: for (int a = 1; a <= n / 2; ++a)140: {141: result += C(n, a * 2) * (C(a * 2, a) / 2 - C(2 * a, a) / (a + 1));142: }`143: return result;`

144: }145:146: static Stopwatch stopwatch = new Stopwatch();147: static void TestBenchSetup()148: {`149: // Uses the second Core or Processor for the Test`

`150: Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);`

`151: // Prevents "Normal" processes from interrupting Threads`

152: Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;`153: // Prevents "Normal" Threads from interrupting this thread`

154: Thread.CurrentThread.Priority = ThreadPriority.Highest;155: }`156: // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx`

157: static void TestBenchLoader(Func<int> test_method)158: {159: stopwatch.Reset();160: stopwatch.Start();`161: long result = 0;`

`162: long avg_tick = 0;`

`163: long avg_ms = 0;`

164: while (stopwatch.ElapsedMilliseconds < 1200) // A Warmup of 1000-1500 ms`165: // stabilizes the CPU cache and pipeline.`

166: {`167: result = test_method(); // Warmup`

168: }169: stopwatch.Stop();170: for (int repeat = 0; repeat < 20; ++repeat)171: {172: stopwatch.Reset();173: stopwatch.Start();174: result = test_method();175: stopwatch.Stop();176: avg_tick += stopwatch.ElapsedTicks;177: avg_ms += stopwatch.ElapsedMilliseconds;178: }179: avg_tick = avg_tick / 20;180: avg_ms = avg_ms / 20;181: Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",182: test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));183: }184: }

Advertisements