我刚刚解决了一个关于 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;
}
当n = 1000, table all square = 0时,STL栈大于2s,array栈小于1s。 所以我认为堆栈的STL实现比按数组实现堆栈慢。队列,双端队列也可以用数组来实现。
为什么 STL 实现速度较慢,我应该通过数组实现它们以提高性能吗?
最佳答案
像往常一样,您应该始终在简单情况下使用直接内存访问(如数组),或者为复杂情况实现您自己的数据结构以获得更好的性能。 Std 容器具有检查、间接和抛出异常的功能,这些都会降低内存访问性能。此外,在“堆栈”版本的算法中,您使用方法来增加/减少堆栈大小,这可能(但不是必须)导致大量内存分配/释放,这也会导致性能问题。
关于C++:我应该通过数组实现堆栈/队列/双端队列以提高性能吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27539605/