我刚刚解决了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/

10-11 23:14
查看更多