一千萬個為什麽

搜索

c ++ std對vs矢量加速

I wrote a maze program using a vector of lots of coordinates. Testing a 100x100 grid, when I used vector the program took 383 seconds, but when I used pair it took only 13 seconds. Where did this dramatic speedup come from?

這是代碼:(還有待改進)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

const int HEIGHT = 100, WIDTH = 100;

bool in_bounds(int x, int y)
{
   //Cells (0,0) to (WIDTH-1, HEIGHT -1)
    return (x >= 0 && x < WIDTH && y >= 0 && y < HEIGHT);
}

bool in_vector(int x, int y, vector > v)
{
    return find(v.begin(), v.end(), pair(x,y)) != v.end();
}

vector get_dir(int x, int y, vector > v)
{
    vector open_dir;//Open neighbor cells
    if (in_bounds(x+1,y) && !in_vector(x+1,y,v))
        open_dir.push_back("e");
    if (in_bounds(x-1,y) && !in_vector(x-1,y,v))
        open_dir.push_back("w");
    if (in_bounds(x,y+1) && !in_vector(x,y+1,v))
        open_dir.push_back("n");
    if (in_bounds(x,y-1) && !in_vector(x,y-1,v))
        open_dir.push_back("s");
    return open_dir;
}

int main()
{
    vector > in_maze_cells {make_pair(0, 0)}, path {make_pair(0, 0)};
    vector > hor_walls (WIDTH, vector(HEIGHT, "--")),
                            vert_walls (WIDTH, vector(HEIGHT, "|"));

    srand(time(0));

    while (in_maze_cells.size() != HEIGHT * WIDTH)
    {
        pair  current_cell = path.back();
        int x = current_cell.first;
        int y = current_cell.second;

        vector open_dir = get_dir(x, y, in_maze_cells);

         if (open_dir.size())
         {
            //Randomly pick an open cell and move to it
            string dir = open_dir[rand() % open_dir.size()];
            pair new_cell;
           //Left and bottom wall coordinates match cell coordinates
            if (dir == "e"){
                new_cell = make_pair(x+1,y);
                vert_walls[x+1][y] = " ";
            }
            if (dir == "w"){
                new_cell = make_pair(x-1,y);
                vert_walls[x][y] = " ";
            }
            if (dir == "n"){
                new_cell = make_pair(x,y+1);
                hor_walls[x][y+1] = "  ";
            }
            if (dir == "s"){
                new_cell = make_pair(x,y-1);
                hor_walls[x][y] = "  ";
            }
            in_maze_cells.push_back(new_cell);
            path.push_back(new_cell);
         }
         else
            path.pop_back();//Backtracking
    }
   //Top row
    for(int i=0; i<< "+--";
    cout << "+" << endl;

    for(int i=HEIGHT-1; i>=0; i--)
    {
        for(int j=0; j<< vert_walls[j][i] << "  ";
        cout << "|" << endl;

        for(int j=0; j<< "+" << hor_walls[j][i];
        cout << "+" << endl;
    }
    return 0;
}

最佳答案

載體的載體可能更重,因為載體比一對更復雜。

另外,在你的函數中,你通過值傳遞了這個向量:

bool in_vector(int x, int y, vector v)
{
    return find(v.begin(), v.end(), cell(x,y)) != v.end();
}

這使得它更加昂貴。將其更改為

bool in_vector(int x, int y, vector const& v)

如果您有興趣,我可以提供更多優化提示

轉載註明原文: c ++ std對vs矢量加速