非确定性计算引擎转化为C#版本并重构

比眉伴天荒 2022-03-28 04:23 183阅读 0赞

这是之前我写的原始的 VB.NET 版本：

http://www.cnblogs.com/RChen/archive/2010/05/17/1737587.html

转化为 C# 版本后，还进行了一些重构。包括修改成了强类型，以及使用了 Parallel.ForEach，但是发现没有收到预期的效果。性能提升比较少。

研究后发现，其实问题的关键在于要通过某种方式对遍历的可能性进行剪枝，这样才能减少遍历次数，从而提升性能。而且，由于结果是通过 yield return 和 IEnumerable 实现的，并没有实现 IList 或者 Array. 所以它本质上并不支持按索引范围拆分的 Parallel.ForEach 工作方式，而实际估计是使用的几个 chunk 轮番读取的低效方式，这样在各个 chunk 之间就有线程同步的开销，如前文所说。这个性能优化只好留待后面有空再继续研究。

下面是目前的状况的实现代码：

  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Threading.Tasks;
  6. using System.Collections;
  8. namespace NonDeterministicEngineCS
  9. {
  10.     class Program
  11.     {
  12.         static void Main(string[] args)
  13.         {
  14.             Benchmarking(new Action(Test1), "Test1() 执行完成，花费：{0}毫秒。");
  15.             Console.WriteLine("====================================================");
  16.             Benchmarking(new Action(Test2), "Test2() 执行完成，花费：{0}毫秒。");
  17.             Console.WriteLine("====================================================");
  18.             Benchmarking(new Action(Test3), "Test3() 执行完成，花费：{0}毫秒。");
  19.             Console.ReadLine();
  20.         }
  22.         // 一个简单的测试例子
  23.         public static void Test1()
  24.         {
  25.             NonDeterministicEngine engine = new NonDeterministicEngine();
  27.             engine.AddParam("a", new int[] { 1, 2, 3, 4, 5, 6 });
  28.             engine.AddParam("b", new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });
  30.             engine.AddRequire((int a) => a > 2 && a < 9);
  31.             engine.AddRequire((int b) => b > 5 && b <= 10);
  32.             engine.AddRequire((int a, int b) => a == b - 1);
  34.             engine.EachResult(
  35.                 result => Console.WriteLine("a = {0}, b = {1}", result["a"], result["b"]));
  36.         }
  38.         // 爱因斯坦谜题
  39.         public static void Test2()
  40.         {
  41.             NonDeterministicEngine engine = new NonDeterministicEngine();
  43.             engine.AddParam("baker", new int[] { 1, 2, 3, 4, 5 });
  44.             engine.AddParam("cooper", new int[] { 1, 2, 3, 4, 5 });
  45.             engine.AddParam("fletcher", new int[] { 1, 2, 3, 4, 5 });
  46.             engine.AddParam("miller", new int[] { 1, 2, 3, 4, 5 });
  47.             engine.AddParam("smith", new int[] { 1, 2, 3, 4, 5 });
  49.             engine.AddRequire((int baker) => baker != 5);
  50.             engine.AddRequire((int cooper) => cooper != 1);
  51.             engine.AddRequire((int fletcher) => fletcher != 1 && fletcher != 5);
  52.             engine.AddRequire((int miller, int cooper) => miller > cooper);
  53.             engine.AddRequire((int smith, int fletcher) =>
  54.                 smith != fletcher + 1
  55.                 && smith != fletcher - 1);
  57.             engine.AddRequire((int fletcher, int cooper) => fletcher != cooper + 1
  58.                 && fletcher != cooper - 1);
  60.             engine.AddRequire((int baker, int cooper, int fletcher, int miller, int smith) =>
  61.                 baker != cooper && baker != fletcher && baker != miller
  62.                 && baker != smith && cooper != fletcher && cooper != miller
  63.                 && cooper != smith && fletcher != miller && fletcher != smith && miller != smith);
  65.             engine.EachResult(
  66.              result =>
  67.                  Console.WriteLine("baker: {0}, cooper: {1}, fletcher: {2}, miller: {3}, smith: {4}",
  68.                          result["baker"],
  69.                          result["cooper"],
  70.                          result["fletcher"],
  71.                          result["miller"],
  72.                          result["smith"])
  73.             );
  74.         }
  76.         // 八皇后问题的解法
  77.         public static void Test3()
  78.         {
  79.             var engine = new NonDeterministicEngine();
  81.             engine.AddParam("a", new int[] { 1, 2, 3, 4, 5, 6, 7, 8 });
  82.             engine.AddParam("b", new int[] { 1, 2, 3, 4, 5, 6, 7, 8 });
  83.             engine.AddParam("c", new int[] { 1, 2, 3, 4, 5, 6, 7, 8 });
  84.             engine.AddParam("d", new int[] { 1, 2, 3, 4, 5, 6, 7, 8 });
  85.             engine.AddParam("e", new int[] { 1, 2, 3, 4, 5, 6, 7, 8 });
  86.             engine.AddParam("f", new int[] { 1, 2, 3, 4, 5, 6, 7, 8 });
  87.             engine.AddParam("g", new int[] { 1, 2, 3, 4, 5, 6, 7, 8 });
  88.             engine.AddParam("h", new int[] { 1, 2, 3, 4, 5, 6, 7, 8 });
  90.             engine.AddRequire((int a, int b, int c, int d, int e, int f, int g, int h) =>
  91.                 a != b && a != c && a != d
  92.                 && a != e && a != f && a != g && a != h
  93.                 && b != c && b != d && b != e && b != f && b != g && b != h
  94.                 && c != d && c != e && c != f && c != g && c != h
  95.                 && d != e && d != f && d != g && d != h
  96.                 && e != f && e != g && e != h
  97.                 && f != g && f != h
  98.                 && g != h
  99.                 && NotInTheSameDiagonalLine(new int[] { a, b, c, d, e, f, g, h }));
  101.             engine.EachResult(
  102.                result =>
  103.                    Console.WriteLine("(1,{0}), (2,{1}), (3,{2}), (4,{3}), (5,{4}), (6,{5}), (7,{6}), (8,{7})",
  104.                    result["a"],
  105.                    result["b"],
  106.                    result["c"],
  107.                    result["d"],
  108.                    result["e"],
  109.                    result["f"],
  110.                    result["g"],
  111.                    result["h"])
  112.                    );
  113.         }
  115.         static bool NotInTheSameDiagonalLine(int[] cols)
  116.         {
  117.             for (int i = 0; i < cols.Length - 1; i++)
  118.             {
  119.                 for (int j = i + 1; j < cols.Length; j++)
  120.                 {
  121.                     if (j - i == Math.Abs(cols[j] - cols[i]))
  122.                         return false;
  123.                 }
  124.             }
  125.             return true;
  126.         }
  128.         public static void Benchmarking(Action f, string messageFormat)
  129.         {
  130.             DateTime time1 = DateTime.Now;
  131.             f();
  132.             DateTime time2 = DateTime.Now;
  133.             Console.WriteLine(messageFormat, (time2 - time1).TotalMilliseconds);
  134.         }
  135.     }
  136. }
  138. using System;
  139. using System.Collections.Generic;
  140. using System.Linq;
  141. using System.Text;
  142. using System.Collections;
  144. namespace NonDeterministicEngineCS
  145. {
  146.     public class Param
  147.     {
  148.         public string Name
  149.         {
  150.             get;
  151.             set;
  152.         }
  153.         public IEnumerator Values
  154.         {
  155.             get;
  156.             set;
  157.         }
  158.     }
  159. }
  161. using System;
  162. using System.Collections.Generic;
  163. using System.Linq;
  164. using System.Text;
  166. namespace NonDeterministicEngineCS
  167. {
  168.     public abstract class Condition
  169.     {
  170.         public IList<string> ParamNames
  171.         {
  172.             get;
  173.             protected set;
  174.         }
  176.         public abstract bool Call(params object[] args);
  178.         public Condition(Delegate predicate)
  179.         {
  180.             ParamNames = predicate.Method.GetParameters().Select(p => p.Name).ToArray();
  181.         }
  182.     }
  184.     public class Condition<T> : Condition
  185.     {
  186.         public Condition(Func<T, bool> predicate)
  187.             : base(predicate)
  188.         {
  189.             m_func = predicate;
  190.         }
  192.         Func<T, bool> m_func;
  194.         public override bool Call(params object[] args)
  195.         {
  196.             return m_func((T)args[0]);
  197.         }
  198.     }
  200.     public class Condition<T1, T2> : Condition
  201.     {
  202.         public Condition(Func<T1, T2, bool> predicate)
  203.             : base(predicate)
  204.         {
  205.             m_func = predicate;
  206.         }
  208.         Func<T1, T2, bool> m_func;
  210.         public override bool Call(params object[] args)
  211.         {
  212.             return m_func((T1)args[0], (T2)args[1]);
  213.         }
  214.     }
  216.     public class Condition<T1, T2, T3> : Condition
  217.     {
  218.         public Condition(Func<T1, T2, T3, bool> predicate)
  219.             : base(predicate)
  220.         {
  221.             m_func = predicate;
  222.         }
  224.         Func<T1, T2, T3, bool> m_func;
  226.         public override bool Call(params object[] args)
  227.         {
  228.             return m_func((T1)args[0], (T2)args[1], (T3)args[2]);
  229.         }
  230.     }
  232.     public class Condition<T1, T2, T3, T4> : Condition
  233.     {
  234.         public Condition(Func<T1, T2, T3, T4, bool> predicate)
  235.             : base(predicate)
  236.         {
  237.             m_func = predicate;
  238.         }
  240.         Func<T1, T2, T3, T4, bool> m_func;
  242.         public override bool Call(params object[] args)
  243.         {
  244.             return m_func((T1)args[0], (T2)args[1], (T3)args[2], (T4) args[3]);
  245.         }
  246.     }
  248.     public class Condition<T1, T2, T3, T4, T5> : Condition
  249.     {
  250.         public Condition(Func<T1, T2, T3, T4, T5, bool> predicate)
  251.             : base(predicate)
  252.         {
  253.             m_func = predicate;
  254.         }
  256.         Func<T1, T2, T3, T4, T5, bool> m_func;
  258.         public override bool Call(params object[] args)
  259.         {
  260.             return m_func((T1)args[0], (T2)args[1], (T3)args[2], (T4)args[3], (T5)args[4]);
  261.         }
  262.     }
  264.     public class Condition<T1, T2, T3, T4, T5, T6> : Condition
  265.     {
  266.         public Condition(Func<T1, T2, T3, T4, T5, T6, bool> predicate)
  267.             : base(predicate)
  268.         {
  269.             m_func = predicate;
  270.         }
  272.         Func<T1, T2, T3, T4, T5, T6, bool> m_func;
  274.         public override bool Call(params object[] args)
  275.         {
  276.             return m_func((T1)args[0], (T2)args[1], (T3)args[2], (T4)args[3], (T5)args[4], (T6)args[5]);
  277.         }
  278.     }
  280.     public class Condition<T1, T2, T3, T4, T5, T6, T7> : Condition
  281.     {
  282.         public Condition(Func<T1, T2, T3, T4, T5, T6, T7, bool> predicate)
  283.             : base(predicate)
  284.         {
  285.             m_func = predicate;
  286.         }
  288.         Func<T1, T2, T3, T4, T5, T6, T7, bool> m_func;
  290.         public override bool Call(params object[] args)
  291.         {
  292.             return m_func((T1)args[0], (T2)args[1], (T3)args[2], (T4)args[3], (T5)args[4], (T6)args[5], (T7)args[6]);
  293.         }
  294.     }
  296.     public class Condition<T1, T2, T3, T4, T5, T6, T7, T8> : Condition
  297.     {
  298.         public Condition(Func<T1, T2, T3, T4, T5, T6, T7, T8, bool> predicate)
  299.             : base(predicate)
  300.         {
  301.             m_func = predicate;
  302.         }
  304.         Func<T1, T2, T3, T4, T5, T6, T7, T8, bool> m_func;
  306.         public override bool Call(params object[] args)
  307.         {
  308.             return m_func((T1)args[0], (T2)args[1], (T3)args[2], (T4)args[3], (T5)args[4], (T6)args[5], (T7)args[6], (T8)args[7]);
  309.         }
  310.     }
  311. }
  313. using System;
  314. using System.Collections.Generic;
  315. using System.Linq;
  316. using System.Text;
  317. using System.Collections;
  318. using System.Threading.Tasks;
  319. using System.Linq.Expressions;
  321. namespace NonDeterministicEngineCS
  322. {
  323.     public class NonDeterministicEngine
  324.     {
  325.         private List<Param> m_paramDict = new List<Param>();
  326.         private List<Condition> m_predicateDict = new List<Condition>();
  328.         public void AddParam(string name, IEnumerable values)
  329.         {
  330.             m_paramDict.Add(new Param { Name = name, Values = values.GetEnumerator() });
  331.         }
  333.         #region Add Require
  334.         public void AddRequire<T>(Func<T, bool> predicate)
  335.         {
  336.             m_predicateDict.Add(new Condition<T>(predicate));
  337.         }
  339.         public void AddRequire<T1, T2>(Func<T1, T2, bool> predicate)
  340.         {
  341.             m_predicateDict.Add(new Condition<T1, T2>(predicate));
  342.         }
  344.         public void AddRequire<T1, T2, T3>(Func<T1, T2, T3, bool> predicate)
  345.         {
  346.             m_predicateDict.Add(new Condition<T1, T2, T3>(predicate));
  347.         }
  349.         public void AddRequire<T1, T2, T3, T4>(Func<T1, T2, T3, T4, bool> predicate)
  350.         {
  351.             m_predicateDict.Add(new Condition<T1, T2, T3, T4>(predicate));
  352.         }
  354.         public void AddRequire<T1, T2, T3, T4, T5>(Func<T1, T2, T3, T4, T5, bool> predicate)
  355.         {
  356.             m_predicateDict.Add(new Condition<T1, T2, T3, T4, T5>(predicate));
  357.         }
  359.         public void AddRequire<T1, T2, T3, T4, T5, T6>(Func<T1, T2, T3, T4, T5, T6, bool> predicate)
  360.         {
  361.             m_predicateDict.Add(new Condition<T1, T2, T3, T4, T5, T6>(predicate));
  362.         }
  364.         public void AddRequire<T1, T2, T3, T4, T5, T6, T7>(Func<T1, T2, T3, T4, T5, T6, T7, bool> predicate)
  365.         {
  366.             m_predicateDict.Add(new Condition<T1, T2, T3, T4, T5, T6, T7>(predicate));
  367.         }
  369.         public void AddRequire<T1, T2, T3, T4, T5, T6, T7, T8>(Func<T1, T2, T3, T4, T5, T6, T7, T8, bool> predicate)
  370.         {
  371.             m_predicateDict.Add(new Condition<T1, T2, T3, T4, T5, T6, T7, T8>(predicate));
  372.         } 
  373.         #endregion
  375.         public IEnumerable<Dictionary<string, object>> GetResults()
  376.         {
  377.             var em = new CombinationEnumerable(this);
  379.             foreach (var item in em)
  380.             {
  381.                 if (Satisfy(item))
  382.                     yield return item;
  383.             }
  384.         }
  386.         public void EachResult(Action<Dictionary<string, object>> action)
  387.         {
  388.             var em = new CombinationEnumerable(this);
  390.             Parallel.ForEach(
  391.                 em,
  392.                 result =>
  393.                 {
  394.                     if (Satisfy(result))
  395.                     {
  396.                         action(result);
  397.                     }
  398.                 }
  399.             );
  400.         }
  402.         bool Satisfy(Dictionary<string, object> result)
  403.         {
  404.             foreach (Condition item in m_predicateDict)
  405.             {
  406.                 var args = item.ParamNames.Select(
  407.                     name => result[name]
  408.                         ).ToArray();
  410.                 if (item.Call(args))
  411.                     continue;
  413.                 return false;
  414.             }
  415.             return true;
  416.         }
  418.         private class CombinationEnumerable : IEnumerable<Dictionary<string, object>>
  419.         {
  420.             NonDeterministicEngine m_engine;
  422.             public CombinationEnumerable(NonDeterministicEngine engine)
  423.             {
  424.                 m_engine = engine;
  425.             }
  427.             public IEnumerator<Dictionary<string, object>> GetEnumerator()
  428.             {
  429.                 return new CombinationEnumerator(m_engine);
  430.             }
  432.             IEnumerator IEnumerable.GetEnumerator()
  433.             {
  434.                 return new CombinationEnumerator(m_engine);
  435.             }
  436.         }
  438.         /// <summary>
  439.         /// 组合多个 iterator 为一个复合的 iterator.
  440.         /// MoveNext 实现为：移动到下一个所有变量值可能的组合。
  441.         /// </summary>
  442.         private class CombinationEnumerator : IEnumerator<Dictionary<string, object>>
  443.         {
  444.             private bool m_firstTime = true;
  445.             private NonDeterministicEngine m_target;
  447.             public CombinationEnumerator(NonDeterministicEngine engine)
  448.             {
  449.                 m_target = engine;
  450.             }
  452.             public void Dispose()
  453.             {
  454.             }
  456.             public Dictionary<string, object> GetCurrent()
  457.             {
  458.                 if (IterationOver)
  459.                     return null;
  461.                 return m_target.m_paramDict.ToDictionary
  462.                     (param => param.Name, param => param.Values.Current);
  463.             }
  465.             public bool MoveNext()
  466.             {
  467.                 if (IterationOver)
  468.                     return false;
  470.                 if (m_firstTime)
  471.                 {
  472.                     // 首次执行时，需要将所有变量的 enumerator 都前进到起始位置
  473.                     foreach (Param item in m_target.m_paramDict)
  474.                     {
  475.                         item.Values.MoveNext();
  476.                     }
  477.                     m_firstTime = false;
  478.                     return true;
  479.                 }
  481.                 // 首先尝试最后一个变量的 iterator，看能否 MoveNext() （是否还有没有尝试过的值）。
  482.                 int iterIndex = m_target.m_paramDict.Count - 1;
  483.                 bool canMoveNext = m_target.m_paramDict[iterIndex].Values.MoveNext();
  484.                 if (canMoveNext)
  485.                     return true;
  487.                 // 否则依次回溯到前一个变量，看该变量的 iterator 能否 MoveNext()
  488.                 while (!canMoveNext)
  489.                 {
  490.                     iterIndex--;
  492.                     // 表明已尝试了所有变量的所有可能值，退无可退，则终止枚举过程。
  493.                     if (iterIndex == -1)
  494.                     {
  495.                         IterationOver = true;
  496.                         return false;
  497.                     }
  499.                     canMoveNext = m_target.m_paramDict[iterIndex].Values.MoveNext();
  500.                     // 如果往前退到某个可以前进的位置
  501.                     if (canMoveNext)
  502.                     {
  503.                         // 则需要将这个位置之后的所有其他变量的 iterator 复位，并前进到第一种可能性。
  504.                         for (int i = iterIndex + 1; i < m_target.m_paramDict.Count; i++)
  505.                         {
  506.                             var iter = m_target.m_paramDict[i].Values;
  507.                             iter.Reset();
  508.                             iter.MoveNext();
  509.                         }
  510.                         return true;
  511.                     }
  512.                 }
  513.                 return false;
  514.             }
  516.             public void Reset()
  517.             {
  518.                 IterationOver = false;
  519.                 m_firstTime = true;
  521.                 foreach (var param in m_target.m_paramDict)
  522.                 {
  523.                     param.Values.Reset();
  524.                 }
  525.             }
  527.             public Dictionary<string, object> Current
  528.             {
  529.                 get
  530.                 {
  531.                     return GetCurrent();
  532.                 }
  533.             }
  535.             /// <summary>
  536.             /// 标记枚举是否已经结束
  537.             /// </summary>
  538.             public bool IterationOver
  539.             {
  540.                 get;
  541.                 set;
  542.             }
  544.             object IEnumerator.Current
  545.             {
  546.                 get
  547.                 {
  548.                     return GetCurrent();
  549.                 }
  550.             }
  551.         }
  552.     }
  553. }

发表评论

表情：
评论列表 （有 0 条评论，183人围观）

还没有评论，来说两句吧...

相关阅读

    相关 确定性函数和非确定性函数

    比如：ABS 返回给定数字表达式的绝对值，每次输入相同的参数值，所得的结果都是相同的，所以它是确定函数；而 GETDATA 返回当前系统时间，每次调用的结果都不同，所以它是非确

    傷城~傷城~/ 0 赞/ 272 阅读