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

比眉伴天荒 2022-03-28 04:23 117阅读 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 之间就有线程同步的开销，如[前文][Link 1]所说。这个性能优化只好留待后面有空再继续研究。

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

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    using System.Collections;
    
    namespace NonDeterministicEngineCS
    {
        class Program
        {
            static void Main(string[] args)
            {
                Benchmarking(new Action(Test1), "Test1() 执行完成，花费：{0}毫秒。");
                Console.WriteLine("====================================================");
                Benchmarking(new Action(Test2), "Test2() 执行完成，花费：{0}毫秒。");
                Console.WriteLine("====================================================");
                Benchmarking(new Action(Test3), "Test3() 执行完成，花费：{0}毫秒。");
                Console.ReadLine();
            }
    
            // 一个简单的测试例子
            public static void Test1()
            {
                NonDeterministicEngine engine = new NonDeterministicEngine();
    
                engine.AddParam("a", new int[] { 1, 2, 3, 4, 5, 6 });
                engine.AddParam("b", new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });
    
                engine.AddRequire((int a) => a > 2 && a < 9);
                engine.AddRequire((int b) => b > 5 && b <= 10);
                engine.AddRequire((int a, int b) => a == b - 1);
    
                engine.EachResult(
                    result => Console.WriteLine("a = {0}, b = {1}", result["a"], result["b"]));
            }
    
            // 爱因斯坦谜题
            public static void Test2()
            {
                NonDeterministicEngine engine = new NonDeterministicEngine();
    
                engine.AddParam("baker", new int[] { 1, 2, 3, 4, 5 });
                engine.AddParam("cooper", new int[] { 1, 2, 3, 4, 5 });
                engine.AddParam("fletcher", new int[] { 1, 2, 3, 4, 5 });
                engine.AddParam("miller", new int[] { 1, 2, 3, 4, 5 });
                engine.AddParam("smith", new int[] { 1, 2, 3, 4, 5 });
    
                engine.AddRequire((int baker) => baker != 5);
                engine.AddRequire((int cooper) => cooper != 1);
                engine.AddRequire((int fletcher) => fletcher != 1 && fletcher != 5);
                engine.AddRequire((int miller, int cooper) => miller > cooper);
                engine.AddRequire((int smith, int fletcher) =>
                    smith != fletcher + 1
                    && smith != fletcher - 1);
    
                engine.AddRequire((int fletcher, int cooper) => fletcher != cooper + 1
                    && fletcher != cooper - 1);
    
                engine.AddRequire((int baker, int cooper, int fletcher, int miller, int smith) =>
                    baker != cooper && baker != fletcher && baker != miller
                    && baker != smith && cooper != fletcher && cooper != miller
                    && cooper != smith && fletcher != miller && fletcher != smith && miller != smith);
    
                engine.EachResult(
                 result =>
                     Console.WriteLine("baker: {0}, cooper: {1}, fletcher: {2}, miller: {3}, smith: {4}",
                             result["baker"],
                             result["cooper"],
                             result["fletcher"],
                             result["miller"],
                             result["smith"])
                );
            }
    
            // 八皇后问题的解法
            public static void Test3()
            {
                var engine = new NonDeterministicEngine();
    
                engine.AddParam("a", new int[] { 1, 2, 3, 4, 5, 6, 7, 8 });
                engine.AddParam("b", new int[] { 1, 2, 3, 4, 5, 6, 7, 8 });
                engine.AddParam("c", new int[] { 1, 2, 3, 4, 5, 6, 7, 8 });
                engine.AddParam("d", new int[] { 1, 2, 3, 4, 5, 6, 7, 8 });
                engine.AddParam("e", new int[] { 1, 2, 3, 4, 5, 6, 7, 8 });
                engine.AddParam("f", new int[] { 1, 2, 3, 4, 5, 6, 7, 8 });
                engine.AddParam("g", new int[] { 1, 2, 3, 4, 5, 6, 7, 8 });
                engine.AddParam("h", new int[] { 1, 2, 3, 4, 5, 6, 7, 8 });
    
                engine.AddRequire((int a, int b, int c, int d, int e, int f, int g, int h) =>
                    a != b && a != c && a != d
                    && a != e && a != f && a != g && a != h
                    && b != c && b != d && b != e && b != f && b != g && b != h
                    && c != d && c != e && c != f && c != g && c != h
                    && d != e && d != f && d != g && d != h
                    && e != f && e != g && e != h
                    && f != g && f != h
                    && g != h
                    && NotInTheSameDiagonalLine(new int[] { a, b, c, d, e, f, g, h }));
    
                engine.EachResult(
                   result =>
                       Console.WriteLine("(1,{0}), (2,{1}), (3,{2}), (4,{3}), (5,{4}), (6,{5}), (7,{6}), (8,{7})",
                       result["a"],
                       result["b"],
                       result["c"],
                       result["d"],
                       result["e"],
                       result["f"],
                       result["g"],
                       result["h"])
                       );
            }
    
            static bool NotInTheSameDiagonalLine(int[] cols)
            {
                for (int i = 0; i < cols.Length - 1; i++)
                {
                    for (int j = i + 1; j < cols.Length; j++)
                    {
                        if (j - i == Math.Abs(cols[j] - cols[i]))
                            return false;
                    }
                }
                return true;
            }
    
            public static void Benchmarking(Action f, string messageFormat)
            {
                DateTime time1 = DateTime.Now;
                f();
                DateTime time2 = DateTime.Now;
                Console.WriteLine(messageFormat, (time2 - time1).TotalMilliseconds);
            }
        }
    }

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Collections;
    
    namespace NonDeterministicEngineCS
    {
        public class Param
        {
            public string Name
            {
                get;
                set;
            }
            public IEnumerator Values
            {
                get;
                set;
            }
        }
    }

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    
    namespace NonDeterministicEngineCS
    {
        public abstract class Condition
        {
            public IList<string> ParamNames
            {
                get;
                protected set;
            }
            
            public abstract bool Call(params object[] args);
    
            public Condition(Delegate predicate)
            {
                ParamNames = predicate.Method.GetParameters().Select(p => p.Name).ToArray();
            }
        }
    
        public class Condition<T> : Condition
        {
            public Condition(Func<T, bool> predicate)
                : base(predicate)
            {
                m_func = predicate;
            }
    
            Func<T, bool> m_func;
    
            public override bool Call(params object[] args)
            {
                return m_func((T)args[0]);
            }
        }
    
        public class Condition<T1, T2> : Condition
        {
            public Condition(Func<T1, T2, bool> predicate)
                : base(predicate)
            {
                m_func = predicate;
            }
    
            Func<T1, T2, bool> m_func;
    
            public override bool Call(params object[] args)
            {
                return m_func((T1)args[0], (T2)args[1]);
            }
        }
    
        public class Condition<T1, T2, T3> : Condition
        {
            public Condition(Func<T1, T2, T3, bool> predicate)
                : base(predicate)
            {
                m_func = predicate;
            }
    
            Func<T1, T2, T3, bool> m_func;
    
            public override bool Call(params object[] args)
            {
                return m_func((T1)args[0], (T2)args[1], (T3)args[2]);
            }
        }
    
        public class Condition<T1, T2, T3, T4> : Condition
        {
            public Condition(Func<T1, T2, T3, T4, bool> predicate)
                : base(predicate)
            {
                m_func = predicate;
            }
    
            Func<T1, T2, T3, T4, bool> m_func;
    
            public override bool Call(params object[] args)
            {
                return m_func((T1)args[0], (T2)args[1], (T3)args[2], (T4) args[3]);
            }
        }
    
        public class Condition<T1, T2, T3, T4, T5> : Condition
        {
            public Condition(Func<T1, T2, T3, T4, T5, bool> predicate)
                : base(predicate)
            {
                m_func = predicate;
            }
    
            Func<T1, T2, T3, T4, T5, bool> m_func;
    
            public override bool Call(params object[] args)
            {
                return m_func((T1)args[0], (T2)args[1], (T3)args[2], (T4)args[3], (T5)args[4]);
            }
        }
    
        public class Condition<T1, T2, T3, T4, T5, T6> : Condition
        {
            public Condition(Func<T1, T2, T3, T4, T5, T6, bool> predicate)
                : base(predicate)
            {
                m_func = predicate;
            }
    
            Func<T1, T2, T3, T4, T5, T6, bool> m_func;
    
            public override bool Call(params object[] args)
            {
                return m_func((T1)args[0], (T2)args[1], (T3)args[2], (T4)args[3], (T5)args[4], (T6)args[5]);
            }
        }
    
        public class Condition<T1, T2, T3, T4, T5, T6, T7> : Condition
        {
            public Condition(Func<T1, T2, T3, T4, T5, T6, T7, bool> predicate)
                : base(predicate)
            {
                m_func = predicate;
            }
    
            Func<T1, T2, T3, T4, T5, T6, T7, bool> m_func;
    
            public override bool Call(params object[] args)
            {
                return m_func((T1)args[0], (T2)args[1], (T3)args[2], (T4)args[3], (T5)args[4], (T6)args[5], (T7)args[6]);
            }
        }
    
        public class Condition<T1, T2, T3, T4, T5, T6, T7, T8> : Condition
        {
            public Condition(Func<T1, T2, T3, T4, T5, T6, T7, T8, bool> predicate)
                : base(predicate)
            {
                m_func = predicate;
            }
            
            Func<T1, T2, T3, T4, T5, T6, T7, T8, bool> m_func;
    
            public override bool Call(params object[] args)
            {
                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]);
            }
        }
    }

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Collections;
    using System.Threading.Tasks;
    using System.Linq.Expressions;
    
    namespace NonDeterministicEngineCS
    {
        public class NonDeterministicEngine
        {
            private List<Param> m_paramDict = new List<Param>();
            private List<Condition> m_predicateDict = new List<Condition>();
    
            public void AddParam(string name, IEnumerable values)
            {
                m_paramDict.Add(new Param { Name = name, Values = values.GetEnumerator() });
            }
    
            #region Add Require
            public void AddRequire<T>(Func<T, bool> predicate)
            {
                m_predicateDict.Add(new Condition<T>(predicate));
            }
    
            public void AddRequire<T1, T2>(Func<T1, T2, bool> predicate)
            {
                m_predicateDict.Add(new Condition<T1, T2>(predicate));
            }
    
            public void AddRequire<T1, T2, T3>(Func<T1, T2, T3, bool> predicate)
            {
                m_predicateDict.Add(new Condition<T1, T2, T3>(predicate));
            }
    
            public void AddRequire<T1, T2, T3, T4>(Func<T1, T2, T3, T4, bool> predicate)
            {
                m_predicateDict.Add(new Condition<T1, T2, T3, T4>(predicate));
            }
    
            public void AddRequire<T1, T2, T3, T4, T5>(Func<T1, T2, T3, T4, T5, bool> predicate)
            {
                m_predicateDict.Add(new Condition<T1, T2, T3, T4, T5>(predicate));
            }
    
            public void AddRequire<T1, T2, T3, T4, T5, T6>(Func<T1, T2, T3, T4, T5, T6, bool> predicate)
            {
                m_predicateDict.Add(new Condition<T1, T2, T3, T4, T5, T6>(predicate));
            }
    
            public void AddRequire<T1, T2, T3, T4, T5, T6, T7>(Func<T1, T2, T3, T4, T5, T6, T7, bool> predicate)
            {
                m_predicateDict.Add(new Condition<T1, T2, T3, T4, T5, T6, T7>(predicate));
            }
    
            public void AddRequire<T1, T2, T3, T4, T5, T6, T7, T8>(Func<T1, T2, T3, T4, T5, T6, T7, T8, bool> predicate)
            {
                m_predicateDict.Add(new Condition<T1, T2, T3, T4, T5, T6, T7, T8>(predicate));
            } 
            #endregion
    
            public IEnumerable<Dictionary<string, object>> GetResults()
            {
                var em = new CombinationEnumerable(this);
    
                foreach (var item in em)
                {
                    if (Satisfy(item))
                        yield return item;
                }
            }
    
            public void EachResult(Action<Dictionary<string, object>> action)
            {
                var em = new CombinationEnumerable(this);
    
                Parallel.ForEach(
                    em,
                    result =>
                    {
                        if (Satisfy(result))
                        {
                            action(result);
                        }
                    }
                );
            }
            
            bool Satisfy(Dictionary<string, object> result)
            {
                foreach (Condition item in m_predicateDict)
                {
                    var args = item.ParamNames.Select(
                        name => result[name]
                            ).ToArray();
    
                    if (item.Call(args))
                        continue;
    
                    return false;
                }
                return true;
            }
            
            private class CombinationEnumerable : IEnumerable<Dictionary<string, object>>
            {
                NonDeterministicEngine m_engine;
    
                public CombinationEnumerable(NonDeterministicEngine engine)
                {
                    m_engine = engine;
                }
    
                public IEnumerator<Dictionary<string, object>> GetEnumerator()
                {
                    return new CombinationEnumerator(m_engine);
                }
    
                IEnumerator IEnumerable.GetEnumerator()
                {
                    return new CombinationEnumerator(m_engine);
                }
            }
    
            /// <summary>
            /// 组合多个 iterator 为一个复合的 iterator.
            /// MoveNext 实现为：移动到下一个所有变量值可能的组合。
            /// </summary>
            private class CombinationEnumerator : IEnumerator<Dictionary<string, object>>
            {
                private bool m_firstTime = true;
                private NonDeterministicEngine m_target;
    
                public CombinationEnumerator(NonDeterministicEngine engine)
                {
                    m_target = engine;
                }
    
                public void Dispose()
                {
                }
    
                public Dictionary<string, object> GetCurrent()
                {
                    if (IterationOver)
                        return null;
    
                    return m_target.m_paramDict.ToDictionary
                        (param => param.Name, param => param.Values.Current);
                }
    
                public bool MoveNext()
                {
                    if (IterationOver)
                        return false;
    
                    if (m_firstTime)
                    {
                        // 首次执行时，需要将所有变量的 enumerator 都前进到起始位置
                        foreach (Param item in m_target.m_paramDict)
                        {
                            item.Values.MoveNext();
                        }
                        m_firstTime = false;
                        return true;
                    }
    
                    // 首先尝试最后一个变量的 iterator，看能否 MoveNext() （是否还有没有尝试过的值）。
                    int iterIndex = m_target.m_paramDict.Count - 1;
                    bool canMoveNext = m_target.m_paramDict[iterIndex].Values.MoveNext();
                    if (canMoveNext)
                        return true;
    
                    // 否则依次回溯到前一个变量，看该变量的 iterator 能否 MoveNext()
                    while (!canMoveNext)
                    {
                        iterIndex--;
    
                        // 表明已尝试了所有变量的所有可能值，退无可退，则终止枚举过程。
                        if (iterIndex == -1)
                        {
                            IterationOver = true;
                            return false;
                        }
    
                        canMoveNext = m_target.m_paramDict[iterIndex].Values.MoveNext();
                        // 如果往前退到某个可以前进的位置
                        if (canMoveNext)
                        {
                            // 则需要将这个位置之后的所有其他变量的 iterator 复位，并前进到第一种可能性。
                            for (int i = iterIndex + 1; i < m_target.m_paramDict.Count; i++)
                            {
                                var iter = m_target.m_paramDict[i].Values;
                                iter.Reset();
                                iter.MoveNext();
                            }
                            return true;
                        }
                    }
                    return false;
                }
                
                public void Reset()
                {
                    IterationOver = false;
                    m_firstTime = true;
    
                    foreach (var param in m_target.m_paramDict)
                    {
                        param.Values.Reset();
                    }
                }
    
                public Dictionary<string, object> Current
                {
                    get
                    {
                        return GetCurrent();
                    }
                }
                
                /// <summary>
                /// 标记枚举是否已经结束
                /// </summary>
                public bool IterationOver
                {
                    get;
                    set;
                }
    
                object IEnumerator.Current
                {
                    get
                    {
                        return GetCurrent();
                    }
                }
            }
        }
    }

[Link 1]: http://www.cnblogs.com/RChen/archive/2010/06/27/1766009.html