一个C#和C++执行效率对比的简单实例

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

原题是见http://acm.hdu.edu.cn/showproblem.php?pid=4090，登载在http://blog.csdn.net/woshi250hua/article/details/7997550

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

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

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

// 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);}