我刚刚解决了SPOJ上的一个问题,我执行了DFS,并使用STL堆栈而不是递归的方法,但我得到了TLE。然后我使用数组堆栈而不是STL堆栈并被接受。
问题是:给一个n * n表,每个正方形都有一个数字。首先,您可以从任何正方形开始,选择一个数字K,然后可以转到与您所站立的正方形具有共同边的正方形,然后abs(那个正方形上的数字-您站立的正方形上的数字)== K.您可以去的最大区域是什么?
这是我的解决方案:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <cmath>
#include <cstring>
#include <stack>
using namespace std;
#define maxn 1010
int n, a[maxn][maxn],visited[maxn][maxn], direction[5][3],cnt,anscnt,dd[1000010],dc[1000010],k[1000010];
bool Free[maxn][maxn][5];
/*void visit(int d,int c,int dif) {
stack<int> dd,dc,k;
dd.push(d);
dc.push(c);
k.push(1);
visited[d][c]=dif;
cnt = 0;
while (!dd.empty()) {
int ud = dd.top(), uc = dc.top() , i = k.top();
k.pop();
for (;i<=4;i++)
if (Free[ud][uc][i]) {
int vd = ud+direction[i][1], vc = uc + direction[i][2];
if ((vd==0) or (vc==0) or (vd>n) or (vc>n)) continue;
if ((visited[vd][vc]==dif) or (abs(a[vd][vc]-a[ud][uc])!=dif)) continue;
if (Free[vd][vc][5-i]==false) continue;
visited[vd][vc]=dif;
Free[vd][vc][5-i]=false;
Free[ud][uc][i]=false;
k.push(i+1);
dd.push(vd);
dc.push(vc);
k.push(1);
break;
}
if (i==5) {
cnt++;
cout << ud << ' ' << uc << ' ' << dd.top() << ' ' << dc.top() << ' ' << dd.size() << '\n';
dd.pop(); dc.pop();
}
}
if (cnt > anscnt) {anscnt = cnt;}
} */
void visit(int d,int c,int dif) {
int topdd=0, topdc=0, topk=0;
dd[++topdd]=d;
dc[++topdc]=c;
k[++topk]=1;
visited[d][c]=dif;
cnt = 0;
while (topdd>0) {
int ud = dd[topdd], uc = dc[topdc] , i = k[topk];
topk--;
for (;i<=4;i++)
if (Free[ud][uc][i]) {
int vd = ud+direction[i][1], vc = uc + direction[i][2];
if ((vd==0) or (vc==0) or (vd>n) or (vc>n)) continue;
if ((visited[vd][vc]==dif) or (abs(a[vd][vc]-a[ud][uc])!=dif)) continue;
if (Free[vd][vc][5-i]==false) continue;
visited[vd][vc]=dif;
Free[vd][vc][5-i]=false;
Free[ud][uc][i]=false;
k[++topk]=(i+1);
dd[++topdd]=(vd);
dc[++topdc]=(vc);
k[++topk]=(1);
break;
}
if (i==5) {
cnt++;
topdd--; topdc--;
}
}
if (cnt > anscnt) {anscnt = cnt;}
}
int main()
{
std::ios_base::sync_with_stdio(false);
anscnt = 1;
direction[1][1] = -1; direction[1][2] = 0;
direction[2][1] = 0; direction[2][2] = 1;
direction[3][1] = 0; direction[3][2] = -1;
direction[4][1] = 1; direction[4][2] = 0;
cin >> n;
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++) cin >> a[i][j];
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++) visited[i][j]=-1;
memset(Free,true,sizeof(Free));
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++) {
if (i>1) visit(i,j,abs(a[i][j]-a[i-1][j]));
if (j<n) visit(i,j,abs(a[i][j]-a[i][j+1]));
if (j>1) visit(i,j,abs(a[i][j]-a[i][j-1]));
if (i<n) visit(i,j,abs(a[i][j]-a[i+1][j]));
}
cout << anscnt;
}
http://ideone.com/Hn6Dl4
当n = 1000,并且表中的所有正方形= 0时,STL堆栈大于2s,而数组堆栈小于1s。
因此,我认为堆栈的STL实现比按阵列实现堆栈要慢。队列,双端队列也可以通过数组来实现。
为什么STL的执行速度较慢,我应该按数组实施以提高性能吗?
最佳答案
通常,在简单情况下,应始终使用直接内存访问(如数组),在复杂情况下,应实现自己的数据结构,以获得更好的性能。 Std容器具有检查,指示和抛出异常,这些异常会降低内存访问性能。此外,在“堆栈”版本的算法中,您使用增加/减小堆栈大小的方法,这可能(但不是必须)导致大量的内存分配/取消分配,这也导致性能问题。
关于c++ - C++:是否应该通过数组实现堆栈/队列/双端队列以提高性能?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/27539605/