博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
一个C#和C++执行效率对比的简单实例
阅读量：3976 次
发布时间：2019-05-24

本文共 19498 字，大约阅读时间需要 64 分钟。

这里用一个算法题进行比较。

原题是见，登载在

作者提供了一个比较快的答案。

我之前也尝试做了一个，没有用递归，但也没有用作者使用的格局保存的剪枝方案，比较慢，随后看了作者的方案后再整合进了一个基本等效的格局保存逻辑。

以下是作者的C++程序的基本等价的C#程序，

using System.Collections.Generic;namespace HDU4090{    internal class SolveGemAndPrince2    {        private const int Max = 10;        private struct Node        {            public int X;            public int Y;        }        private readonly Node[] _qu = new Node[Max*Max];        private readonly Dictionary
   
     _hash = new Dictionary
    
     ();        private readonly int[,] _dir = new[,]            {                {1, 0}, {1, 1}, {1, -1}, {-1, 0}, {-1, -1}, {-1, 1}, {0, 1}, {0, -1}            };        private static void Change(int[,] mmap, ref int n, ref int m)        {            int i, j, tn = 0, tm = 0;            var k = new int[10];            for (j = 0; j < m; ++j)            {                k[j] = 0;                for (i = 0; i < n; ++i)                    if (mmap[i, j] != 0) mmap[k[j]++, j] = mmap[i, j];            }            for (j = 0; j < m; ++j)                if (k[j] != 0)                {                    for (i = 0; i < k[j]; ++i)                        mmap[i, tm] = mmap[i, j];                    for (i = k[j]; i < n; ++i)                        mmap[i, tm] = 0;                    tm++;                    if (k[j] > tn) tn = k[j];                }            n = tn;            m = tm;        }        private int Ok(int[,] temp, int[,] vis, int i, int j, int n, int m)        {            var cnt = 0;            int head = 0, tail = 0;            Node cur;            cur.X = i;            cur.Y = j;            _qu[head++] = cur;            vis[cur.X,cur.Y] = 1;            while (tail < head)            {                cur = _qu[tail++];                cnt++;                int k;                for (k = 0; k < 8; ++k)                {                    Node next;                    next.X = cur.X + _dir[k,0];                    next.Y = cur.Y + _dir[k,1];                    if (next.X >= 0 && next.X < n                        && next.Y >= 0 && next.Y < m                        && vis[next.X,next.Y] == 0                        && temp[next.X,next.Y] == temp[i,j])                    {                        _qu[head++] = next;                        vis[next.X,next.Y] = 1;                        temp[next.X,next.Y] = 0;                    }                }            }            temp[i,j] = 0;            return cnt >= 3 ? cnt : 0;        }        static string GetHash(int[,] temp,int n,int m)        {            var s = "";            for (var i = 0; i < n; ++i)                for (var j = 0; j < m; ++j)                    s += temp[i,j] + '0';            return s;        }        static void Mem(int[,] temp, int[,] mmap, int n, int m)        {            for (var i = 0; i < Max; i++ )                for (var j = 0; j < Max; j++)                    temp[i, j] = 0;            for (var i = 0; i < n; ++i)                for (var j = 0; j < m; ++j)                    temp[i,j] = mmap[i,j];        }        int Dfs(int[,] mmap,int n,int m)        {            if (n*m < 3) return 0;            var temp = new int[Max,Max];            int i, j;            var vis = new int[Max,Max];            var cnt = 0;            for (i = 0; i < n; ++i)                for (j = 0; j < m; ++j)                    if (vis[i,j]==0 && mmap[i,j]!=0)                    {                        Mem(temp, mmap, n, m);                        var ans = Ok(temp, vis, i, j, n, m);                        if (ans >= 3)                        {                            ans = ans*ans;                            int tn = n, tm = m;                            Change(temp, ref tn, ref tm);                            var s = GetHash(temp, tn, tm);#if true                            if (!_hash.ContainsKey(s))                                ans += Dfs(temp, tn, tm);                            else ans += _hash[s];#else                            ans += Dfs(temp, tn, tm);#endif                            if (ans > cnt) cnt = ans;                        }                    }            _hash[GetHash(mmap, n, m)] = cnt;            return cnt;        }        public int Solve(int n, int m, int k, int[,] gems)        {            _hash.Clear();            return Dfs(gems, n, m);        }    }}
再接下来是我的方案（纯粹凑热闹，没有参与这里的对比）， 

using System;using System.Collections.Generic;namespace HDU4090{    public class SolveGemAndPrince    {        #region Nested types        class Node        {            #region Nested types            public class Gem            {                public int Row { get; set; }                public int Col { get; set; }            }            public class Connective            {                public readonly List
   
     Connected = new List
    
     ();            }            #endregion            #region Properties            private int[,] Gems { get; set; }            public List
     
       Connectives { get; private set; }            public int Try { get; set; }            public int Score { get; private set; }            #endregion            #region Constructors            public Node(int rows, int cols, int[,] gems, int iniScore)            {                _rows = rows;                _cols = cols;                Score = iniScore;                Connectives = new List
      
       ();                Gems = gems;                Segment();            }            #endregion            #region Methods            public string GetHash()            {                var hash = "";                foreach (var gem in Gems)                {                    hash += gem.ToString() + '0';                }                return hash;            }            void AddToConnective(Connective connective, bool[,] visited, int r, int c)            {                visited[r, c] = true;                connective.Connected.Add(new Gem { Row = r, Col = c });                var imin = Math.Max(0, r - 1);                var imax = Math.Min(_rows - 1, r + 1);                var jmin = Math.Max(0, c - 1);                var jmax = Math.Min(_cols - 1, c + 1);                var cur = Gems[r, c];                for (var i = imin; i <= imax; i++)                {                    for (var j = jmin; j <= jmax; j++)                    {                        if (visited[i, j]) continue;                        var val = Gems[i, j];                        if (val == cur)                        {   // TODO recursive, improve it                            AddToConnective(connective, visited, i, j);                        }                    }                }            }            void Segment()            {                var visited = new bool[_rows, _cols];                for (var i = 0; i < _rows; i++)                {                    for (var j = 0; j < _cols; j++)                    {                        if (visited[i, j] || Gems[i, j] == 0) continue;                        var connective = new Connective();                        AddToConnective(connective, visited, i, j);                        if (connective.Connected.Count < 3) continue;                        Connectives.Add(connective);                    }                }            }            public Node Action(int path)            {                var connective = Connectives[path];                var gems = Copy();                var firstNonZeroRow = _rows;                var firstNonZeroCol = 0;                foreach (var gem in connective.Connected)                {                    gems[gem.Row, gem.Col] = 0;                }                // processes falling                var newcols = 0;                for (var i = 0; i < _cols; i++)                {                    var k = _rows - 1;                    for (var j = _rows - 1; j >= 0; j--)                    {                        if (gems[j, i] > 0)                        {                            gems[k--, i] = gems[j, i];                        }                    }                    for (var t = 0; t <= k; t++)                    {                        gems[t, i] = 0;                    }                    if (k + 1 < firstNonZeroRow) firstNonZeroRow = k + 1;                    if (k + 1 < _rows)                    {   // non-empty                        newcols++;                    }                    else if (i == firstNonZeroCol)                    {                        firstNonZeroCol = i;                    }                }                // processes shifting                var newrows = _rows - firstNonZeroRow;                var newgems = new int[newrows, newcols];                var tcol = 0;                for (var j = firstNonZeroCol; j < _cols; j++)                {                    if (gems[_rows - 1, j] == 0) continue;  // empty column                    for (var i = firstNonZeroRow; i < _rows; i++)                    {                        newgems[i - firstNonZeroRow, tcol] = gems[i, j];                    }                    tcol++;                }                var count = connective.Connected.Count;                var scoreInc = count*count;                return new Node(newrows, newcols, newgems, Score + scoreInc);            }            int[,] Copy()            {                var gems = new int[_rows,_cols];                for (var i = 0; i < _rows; i++)                {                    for (var j =0; j < _cols; j++)                    {                        gems[i, j] = Gems[i, j];                    }                }                return gems;            }            #endregion            #region Fields            private readonly int _rows;            private readonly int _cols;            #endregion        }        #endregion        #region Methods        /// 
               ///  Solves the gem-and-prince problem presented in HDU-4090        ///  http://acm.hdu.edu.cn/showproblem.php?pid=4090        ///  found from the post at        ///  http://blog.csdn.net/woshi250hua/article/details/7997550        ///         /// 
       The number of rows the gem grid contains; might well be ignored in C#        /// 
       The number of columns the gem grid contains; might well be ignored in C#        /// 
       The inclusive upper bound of gem values of which the minimum is always 0 which means there is no gem        /// 
       The initial grid of gems        /// 
       
        The highest score that can be achieved by the solution
               public int Solve(int n, int m, int k, int[,] gems)        {            _records.Clear();            var root = new Node(n, m, gems, 0);            var stack = new Stack
       
        ();            var highest = 0;            stack.Push(root);            while (stack.Count > 0)            {                var node = stack.Pop();                if (node.Try >= node.Connectives.Count) continue;                var newNode = node.Action(node.Try);                node.Try++;                stack.Push(node);#if true    // optimisation                var hash = newNode.GetHash();                if (_records.ContainsKey(hash))                {                    var oldScore = _records[hash];                    if (newNode.Score <= oldScore)                        continue;                }                _records[hash] = newNode.Score;#endif                                if (newNode.Score > highest)                {                    highest = newNode.Score;                }                stack.Push(newNode);            }            return highest;        }        #endregion        #region Fields        readonly Dictionary
        
          _records = new Dictionary
         
          (); #endregion }}

测试程序和样本：

using System;namespace HDU4090{    class Program    {        struct Sample        {            public int N, M, K;            public int[,] Data;        }        private static Sample[] Samples = new Sample[]            {                new Sample                    {                        N = 5,                        M = 5,                        K = 5,                        Data =                            new[,]                                {                                    {1, 2, 3, 4, 5},                                    {1, 2, 2, 2, 1},                                    {1, 2, 1, 2, 1},                                    {1, 2, 2, 2, 2},                                    {1, 2, 3, 3, 5}                                }                    },                new Sample                    {                        N = 3,                        M = 3,                        K = 3,                        Data =                            new[,]                                {                                    {1, 1, 1},                                    {1, 1, 1},                                    {2, 3, 3}                                }                    },                new Sample                    {                        N = 4,                        M = 4,                        K = 3,                        Data =                            new[,]                                {                                    {1, 1, 1, 3},                                    {2, 1, 2, 3},                                    {1, 2, 1, 3},                                    {3, 3, 3, 3}                                }                    },                new Sample                    {                        N = 4,                        M = 4,                        K = 2,                        Data =                            new[,]                                {                                    {1, 2, 1, 2},                                    {2, 1, 2, 1},                                    {1, 2, 1, 2},                                    {2, 1, 2, 1}                                }                    },                new Sample                    {                        N = 8,                        M = 8,                        K = 6,                        Data =                            new[,]                                {                                    {1, 1, 1, 1, 1, 1, 1, 1},                                    {2, 2, 2, 2, 2, 2, 2, 2},                                    {3, 3, 3, 3, 3, 3, 3, 3},                                    {4, 4, 4, 4, 4, 4, 4, 4},                                    {5, 5, 5, 5, 5, 5, 5, 5},                                    {6, 6, 6, 6, 6, 6, 6, 6},                                    {6, 6, 6, 6, 6, 6, 6, 6},                                    {6, 6, 6, 6, 6, 6, 6, 6}                                }                    },                new Sample                    {                        N = 8,                        M = 8,                        K = 6,                        Data =                            new[,]                                {                                    {6, 6, 6, 6, 6, 6, 6, 6},                                    {6, 6, 6, 6, 6, 6, 6, 6},                                    {6, 6, 6, 6, 6, 6, 6, 6},                                    {6, 6, 6, 6, 6, 6, 6, 6},                                    {6, 6, 6, 6, 6, 6, 6, 6},                                    {6, 6, 6, 6, 6, 6, 6, 6},                                    {6, 6, 6, 6, 6, 6, 6, 6},                                    {6, 6, 6, 6, 6, 6, 6, 6}                                }                    },            };        private static int[] _key = {166,36,94,128,896,4096};        static void Main(string[] args)        {            var solve = new SolveGemAndPrince();            var solve2 = new SolveGemAndPrince2();            var time1 = DateTime.Now;            for (var i = 0; i < 10000; i++ )            {                int t = 0;                foreach (var sample in Samples)                {                    var result = solve.Solve(sample.N, sample.M, sample.K, sample.Data);                    //var result = solve2.Solve(sample.N, sample.M, sample.K, sample.Data);                    //Console.WriteLine("Highest score achievable = {0}", result);                    if (result != _key[t++])                    {                        Console.WriteLine("error!");                        return;                    }                }            }            var time2 = DateTime.Now;            var span = time2 - time1;            Console.WriteLine("Done {0}", span.TotalSeconds);        }    }}
将工程编译都调整到速度最大优化，编译环境为Visual Studio 2012，C++编译为32位，C#为Any CPU，运行于CORE i7。结果是运行10000次循环，算法相同的C++程序的速度大约是C#的6倍。当然这个倍率有点高于我的预料，可能程序中还有需要对针对C#进行改进和优化的地方（例如减少堆分配等），但同样C++也有提升空间（当然原作者已经做的很好了）。这个程序包含栈/递归和字典数据结构和一些逻辑和计算操作。总的来说在最大速度优先编译情况下，C++相对C#的执行效率优势还是比较明显。等过一阵子有空针对这个实例再做一次review和各自优化再评估一下结果。

关于效率这个问题，stackoverflow上有一些讨论可以参考：

附，对应的C++程序（由所作，略作修改并用于执行效率对比） 

// HDU4090cpp.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include 
   
    #include 
    
     #include 
     #include 
      
       #include 
       
        #include 
        
         using namespace std;#define MAX 10struct node { int x,y;}qu[MAX*MAX];map
         
           _hash;int gmmap[8][MAX][MAX];int (*mmap)[MAX];int ans;int n,m,K,total;int dir[8][2] = { {1,0},{1,1},{1,-1},{-1,0},{-1,-1},{-1,1},{0,1},{0,-1}};void Print(int temp[][MAX],int n,int m) { for (int i = n-1; i >= 0; --i) for (int j = 0; j < m; ++j) printf("%d%c",temp[i][j],j==m-1?'\n':' ');}void change(int mmap[][MAX],int &n,int &m){ int i,j,k[10],tn = 0,tm = 0; for (j = 0; j < m; ++j) { k[j] = 0; for (i = 0; i < n; ++i) if (mmap[i][j]) mmap[k[j]++][j] = mmap[i][j]; } for (j = 0; j < m; ++j) if (k[j]) { for (i = 0; i < k[j]; ++i) mmap[i][tm] = mmap[i][j]; for (i = k[j]; i < n; ++i) mmap[i][tm] = 0; tm++; if (k[j] > tn) tn = k[j]; } n = tn,m = tm;}int Ok(int temp[][MAX],int vis[][MAX],int i,int j,int n,int m) { int cnt = 0,k; int head = 0,tail = 0; node cur,next; cur.x = i,cur.y = j; qu[head++] = cur; vis[cur.x][cur.y] = 1; while (tail < head) { cur = qu[tail++]; cnt++; for (k = 0; k < 8; ++k) { next.x = cur.x + dir[k][0]; next.y = cur.y + dir[k][1]; if (next.x >= 0 && next.x < n && next.y >= 0 && next.y < m && vis[next.x][next.y] == 0 && temp[next.x][next.y] == temp[i][j]) { qu[head++] = next; vis[next.x][next.y] = 1; temp[next.x][next.y] = 0; } } } temp[i][j] = 0; return cnt >= 3 ? cnt : 0;}string Get_hash(int temp[][MAX],int n,int m) { string s = ""; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) s += temp[i][j] + '0'; return s;}void mem(int temp[][MAX],int mmap[][MAX],int n,int m) { memset(temp,0,sizeof(temp)); for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) temp[i][j] = mmap[i][j];}int Dfs(int mmap[][MAX],int n,int m) { if (n * m < 3) return 0; int temp[MAX][MAX],i,j; int vis[MAX][MAX],cnt = 0,ans; memset(vis,0,sizeof(vis)); for (i = 0; i < n; ++i) for (j = 0; j < m; ++j) if (!vis[i][j] && mmap[i][j]) { mem(temp,mmap,n,m); ans = Ok(temp,vis,i,j,n,m); if (ans >= 3) { ans = ans * ans; int tn = n,tm = m; change(temp,tn,tm); string s = Get_hash(temp,tn,tm); if (_hash.find(s) == _hash.end()) ans += Dfs(temp,tn,tm); else ans += _hash[s]; if (ans > cnt) cnt = ans; } } _hash[Get_hash(mmap,n,m)] = cnt; return cnt;}int _tmain(int argc, _TCHAR* argv[]){ int i,j,k; int key[] = {166,36,94,128,896,4096}; int t=0; FILE *fp = fopen("D:\\temp\\samples.txt", "r"); int testnum = 0; while (fscanf(fp, "%d%d%d",&n,&m,&K) != EOF) { for (i = n-1; i >= 0; --i) for (j = 0; j < m; ++j) fscanf(fp, "%d",&gmmap[testnum][i][j]); testnum++; } time_t t1; time(&t1); for (int C = 0; C < 10000; C++) { t = 0; for (int t=0; t
你可能感兴趣的文章
Spring - sentinel和hystrix比较
查看>>
Flutter 日期插件date_format 中文 国际化 及flutter_cupertino_date_picker
查看>>
Flutter 插件笔记 | 屏幕适配 flutter_screenutil
查看>>
Flutter UI基础 - 侧拉抽屉菜单
查看>>
Flutter UI基础 - AppBar中标题文字如何居中
查看>>
Flutter UI基础 - Drawer 抽屉视图与自定义header
查看>>
Flutter UI基础 - GridView
查看>>
Flutter UI基础 - 使用InkWell给任意Widget添加点击事件
查看>>
OC WKWebView的使用
查看>>
Flutter UI基础 - Image.asset 图片铺满布局
查看>>
Flutter UI基础 - Row、Column详解
查看>>
Flutter UI基础 - 添加背景图片
查看>>
Flutter UI基础 - 布局之Row/Column/Stack
查看>>
Flutter UI基础 - 层叠布局Stack的使用
查看>>
Go - 解决 go get 超时问题
查看>>
SQL - SQL Server 之遍历数据集合的几种方法
查看>>
SQL - SQL Server 之处理JSON数据
查看>>
SQL - SQL Server 之WHILE循环的坑
查看>>
SQL - SQL Server 性能优化之SQL语句总结
查看>>
Docker - docker-compose常用命令
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2024-09-19 03:35:38   当前IP: 18.223.213.148   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我