一个C#和C++执行效率对比的简单实例
生活随笔
收集整理的這篇文章主要介紹了
一个C#和C++执行效率对比的简单实例
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
這里用一個(gè)算法題進(jìn)行比較。
原題是見http://acm.hdu.edu.cn/showproblem.php?pid=4090，登載在http://blog.csdn.net/woshi250hua/article/details/7997550
作者提供了一個(gè)比較快的答案。
我之前也嘗試做了一個(gè)，沒有用遞歸，但也沒有用作者使用的格局保存的剪枝方案，比較慢，隨后看了作者的方案后再整合進(jìn)了一個(gè)基本等效的格局保存邏輯。
以下是作者的C++程序的基本等價(jià)的C#程序，
1 using System.Collections.Generic; 2 3 namespace HDU4090 4 { 5 internal class SolveGemAndPrince2 6 { 7 private const int Max = 10; 8 9 private struct Node 10 { 11 public int X; 12 public int Y; 13 } 14 15 private readonly Node[] _qu = new Node[Max*Max]; 16 private readonly Dictionary<string, int> _hash = new Dictionary<string, int>(); 17 18 private readonly int[,] _dir = new[,] 19 { 20 {1, 0}, {1, 1}, {1, -1}, {-1, 0}, {-1, -1}, {-1, 1}, {0, 1}, {0, -1} 21 }; 22 23 private static void Change(int[,] mmap, ref int n, ref int m) 24 { 25 int i, j, tn = 0, tm = 0; 26 var k = new int[10]; 27 for (j = 0; j < m; ++j) 28 { 29 30 k[j] = 0; 31 for (i = 0; i < n; ++i) 32 if (mmap[i, j] != 0) mmap[k[j]++, j] = mmap[i, j]; 33 } 34 for (j = 0; j < m; ++j) 35 if (k[j] != 0) 36 { 37 38 for (i = 0; i < k[j]; ++i) 39 mmap[i, tm] = mmap[i, j]; 40 for (i = k[j]; i < n; ++i) 41 mmap[i, tm] = 0; 42 tm++; 43 if (k[j] > tn) tn = k[j]; 44 } 45 n = tn; 46 m = tm; 47 } 48 49 private int Ok(int[,] temp, int[,] vis, int i, int j, int n, int m) 50 { 51 var cnt = 0; 52 int head = 0, tail = 0; 53 Node cur; 54 55 cur.X = i; 56 cur.Y = j; 57 _qu[head++] = cur; 58 vis[cur.X,cur.Y] = 1; 59 60 while (tail < head) 61 { 62 cur = _qu[tail++]; 63 cnt++; 64 int k; 65 for (k = 0; k < 8; ++k) 66 { 67 Node next; 68 next.X = cur.X + _dir[k,0]; 69 next.Y = cur.Y + _dir[k,1]; 70 if (next.X >= 0 && next.X < n 71 && next.Y >= 0 && next.Y < m 72 && vis[next.X,next.Y] == 0 73 && temp[next.X,next.Y] == temp[i,j]) 74 { 75 76 _qu[head++] = next; 77 vis[next.X,next.Y] = 1; 78 temp[next.X,next.Y] = 0; 79 } 80 } 81 } 82 temp[i,j] = 0; 83 return cnt >= 3 ? cnt : 0; 84 } 85 86 static string GetHash(int[,] temp,int n,int m) 87 { 88 var s = ""; 89 for (var i = 0; i < n; ++i) 90 for (var j = 0; j < m; ++j) 91 s += temp[i,j] + '0'; 92 return s; 93 } 94 95 static void Mem(int[,] temp, int[,] mmap, int n, int m) 96 { 97 for (var i = 0; i < Max; i++ ) 98 for (var j = 0; j < Max; j++) 99 temp[i, j] = 0; 100 for (var i = 0; i < n; ++i) 101 for (var j = 0; j < m; ++j) 102 temp[i,j] = mmap[i,j]; 103 } 104 105 int Dfs(int[,] mmap,int n,int m) 106 { 107 108 if (n*m < 3) return 0; 109 var temp = new int[Max,Max]; 110 int i, j; 111 var vis = new int[Max,Max]; 112 var cnt = 0; 113 114 for (i = 0; i < n; ++i) 115 for (j = 0; j < m; ++j) 116 if (vis[i,j]==0 && mmap[i,j]!=0) 117 { 118 Mem(temp, mmap, n, m); 119 var ans = Ok(temp, vis, i, j, n, m); 120 if (ans >= 3) 121 { 122 ans = ans*ans; 123 int tn = n, tm = m; 124 Change(temp, ref tn, ref tm); 125 var s = GetHash(temp, tn, tm); 126 #if true 127 if (!_hash.ContainsKey(s)) 128 ans += Dfs(temp, tn, tm); 129 else ans += _hash[s]; 130 #else 131 ans += Dfs(temp, tn, tm); 132 #endif 133 if (ans > cnt) cnt = ans; 134 } 135 } 136 137 _hash[GetHash(mmap, n, m)] = cnt; 138 return cnt; 139 } 140 141 public int Solve(int n, int m, int k, int[,] gems) 142 { 143 _hash.Clear(); 144 return Dfs(gems, n, m); 145 } 146 } 147 }再接下來(lái)是我的方案（純粹湊熱鬧，沒有參與這里的對(duì)比），
測(cè)試程序和樣本：
?
1 using System; 2 3 namespace HDU4090 4 { 5 class Program 6 { 7 struct Sample 8 { 9 public int N, M, K; 10 public int[,] Data; 11 } 12 13 private static Sample[] Samples = new Sample[] 14 { 15 new Sample 16 { 17 N = 5, 18 M = 5, 19 K = 5, 20 Data = 21 new[,] 22 { 23 {1, 2, 3, 4, 5}, 24 {1, 2, 2, 2, 1}, 25 {1, 2, 1, 2, 1}, 26 {1, 2, 2, 2, 2}, 27 {1, 2, 3, 3, 5} 28 } 29 }, 30 new Sample 31 { 32 N = 3, 33 M = 3, 34 K = 3, 35 Data = 36 new[,] 37 { 38 {1, 1, 1}, 39 {1, 1, 1}, 40 {2, 3, 3} 41 } 42 }, 43 new Sample 44 { 45 N = 4, 46 M = 4, 47 K = 3, 48 Data = 49 new[,] 50 { 51 {1, 1, 1, 3}, 52 {2, 1, 2, 3}, 53 {1, 2, 1, 3}, 54 {3, 3, 3, 3} 55 } 56 }, 57 new Sample 58 { 59 N = 4, 60 M = 4, 61 K = 2, 62 Data = 63 new[,] 64 { 65 {1, 2, 1, 2}, 66 {2, 1, 2, 1}, 67 {1, 2, 1, 2}, 68 {2, 1, 2, 1} 69 } 70 }, 71 new Sample 72 { 73 N = 8, 74 M = 8, 75 K = 6, 76 Data = 77 new[,] 78 { 79 {1, 1, 1, 1, 1, 1, 1, 1}, 80 {2, 2, 2, 2, 2, 2, 2, 2}, 81 {3, 3, 3, 3, 3, 3, 3, 3}, 82 {4, 4, 4, 4, 4, 4, 4, 4}, 83 {5, 5, 5, 5, 5, 5, 5, 5}, 84 {6, 6, 6, 6, 6, 6, 6, 6}, 85 {6, 6, 6, 6, 6, 6, 6, 6}, 86 {6, 6, 6, 6, 6, 6, 6, 6} 87 } 88 }, 89 new Sample 90 { 91 N = 8, 92 M = 8, 93 K = 6, 94 Data = 95 new[,] 96 { 97 {6, 6, 6, 6, 6, 6, 6, 6}, 98 {6, 6, 6, 6, 6, 6, 6, 6}, 99 {6, 6, 6, 6, 6, 6, 6, 6}, 100 {6, 6, 6, 6, 6, 6, 6, 6}, 101 {6, 6, 6, 6, 6, 6, 6, 6}, 102 {6, 6, 6, 6, 6, 6, 6, 6}, 103 {6, 6, 6, 6, 6, 6, 6, 6}, 104 {6, 6, 6, 6, 6, 6, 6, 6} 105 } 106 }, 107 }; 108 109 110 private static int[] _key = {166,36,94,128,896,4096}; 111 112 static void Main(string[] args) 113 { 114 var solve = new SolveGemAndPrince(); 115 var solve2 = new SolveGemAndPrince2(); 116 var time1 = DateTime.Now; 117 for (var i = 0; i < 10000; i++ ) 118 { 119 int t = 0; 120 foreach (var sample in Samples) 121 { 122 var result = solve.Solve(sample.N, sample.M, sample.K, sample.Data); 123 //var result = solve2.Solve(sample.N, sample.M, sample.K, sample.Data); 124 //Console.WriteLine("Highest score achievable = {0}", result); 125 if (result != _key[t++]) 126 { 127 Console.WriteLine("error!"); 128 return; 129 } 130 } 131 } 132 var time2 = DateTime.Now; 133 var span = time2 - time1; 134 Console.WriteLine("Done {0}", span.TotalSeconds); 135 } 136 } 137 }將工程編譯都調(diào)整到速度最大優(yōu)化，編譯環(huán)境為Visual Studio 2012，C++編譯為32位，C#為Any CPU，運(yùn)行于CORE i7。結(jié)果是運(yùn)行10000次循環(huán)，算法相同的C++程序的速度大約是C#的6倍。當(dāng)然這個(gè)倍率有點(diǎn)高于我的預(yù)料，可能程序中還有需要對(duì)針對(duì)C#進(jìn)行改進(jìn)和優(yōu)化的地方（例如減少堆分配等），但同樣C++也有提升空間（當(dāng)然原作者已經(jīng)做的很好了）。這個(gè)程序包含棧/遞歸和字典數(shù)據(jù)結(jié)構(gòu)和一些邏輯和計(jì)算操作?？偟膩?lái)說(shuō)在最大速度優(yōu)先編譯情況下，C++相對(duì)C#的執(zhí)行效率優(yōu)勢(shì)還是比較明顯。等過一陣子有空針對(duì)這個(gè)實(shí)例再做一次review和各自優(yōu)化再評(píng)估一下結(jié)果。
?
關(guān)于效率這個(gè)問題，stackoverflow上有一些討論可以參考：
http://stackoverflow.com/questions/145110/c-performance-vs-java-c
http://stackoverflow.com/questions/3961426/c-sharp-vs-c-performance-comparison
?
附，對(duì)應(yīng)的C++程序（由原作者所作，略作修改并用于執(zhí)行效率對(duì)比）
?
?
// HDU4090cpp.cpp : Defines the entry point for the console application. //#include "stdafx.h"#include <stdlib.h> #include <stdio.h> #include <map> #include <string> #include <string.h> #include <time.h>using namespace std; #define MAX 10struct node {int x,y; }qu[MAX*MAX];map<string,int> _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<testnum; t++){_hash.clear();int res = Dfs(gmmap[t],n,m);if (res != key[t]){printf("error\n");return 0;}t++;}}time_t t2;time(&t2);double diff=difftime(t2,t1);printf("done %f\n", diff);fclose(fp); }轉(zhuǎn)載于:https://www.cnblogs.com/quanben/archive/2012/09/22/3128850.html
總結(jié)
以上是生活随笔為你收集整理的一个C#和C++执行效率对比的简单实例的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： EntityModelStudio系列教
- 下一篇： 农忙……