Why vector is slower than set? (C++)


  • 1
    T

    When I was working on this problem, I thought about using set or 2D bool vector to record the body of snake. I tested both but the performance of set (beat 55%) is better than vector (beat 15%), which is not what I expected. Maybe the initialization of the 2D vector is too expensive? Could anyone shed some light on this?

    Use set, 312 ms

    class SnakeGame {
        deque<pair<int, int>> snake;
        set<pair<int, int>> body;
        vector<pair<int, int>> food;
        int m, n, fn;
        
    public:
        SnakeGame(int width, int height, vector<pair<int, int>> food) {
            m = height, n = width, fn = 0;
            this->food = food;
            snake.emplace_back(0, 0);
        }
        
        int move(string direction) {
            int x = snake.front().first, y = snake.front().second;
            if (direction == "U") x --;
    	else if (direction == "D") x ++;
    	else if (direction == "L") y --;
    	else if (direction == "R") y ++;
    	auto xy = make_pair(x, y);
            if (fn < food.size() and xy == food[fn])
                fn ++;
            else {
                body.erase(snake.back());
                snake.pop_back(); 
            }
            if (x < 0 or x >= m or y < 0 or y >= n or body.count(xy))
                return -1;
            snake.push_front(xy);
            body.insert(xy);
            return fn;
        }
    };
    
    

    Use 2D vector, 380 ms

    class SnakeGame {
        deque<pair<int, int>> snake;
        vector<vector<bool>> bd;
        vector<pair<int, int>> food;
        int m, n, fn;
        
    public:
        SnakeGame(int width, int height, vector<pair<int, int>> food) {
            m = height, n = width, fn = 0;
            this->food = food;
            bd = vector<vector<bool>>(m, vector<bool>(n, false));
            bd[0][0] = true;
            snake.emplace_back(0, 0);
        }
        
        int move(string direction) {
            int x = snake.front().first, y = snake.front().second;
            if (direction == "U") x --;
    	else if (direction == "D") x ++;
    	else if (direction == "L") y --;
    	else if (direction == "R") y ++;
    	auto xy = make_pair(x, y);
            if (fn < food.size() and xy == food[fn])
                fn ++;
            else {
                bd[snake.back().first][snake.back().second] = false;
                snake.pop_back(); 
            }
            if (x < 0 or x >= m or y < 0 or y >= n or bd[x][y])
                return -1;
            snake.push_front(xy);
            bd[x][y] = true;
            return fn;
        }
    };

  • 0

    @topcoder007 Show us the code, please. Thank you!


  • 1
    T

    @LHearen Code attached


  • 0

    I think it might be sufficient to simply use queue instead of deque for snake. And there might be no need to define "body" since your snake queue already defined the position of the entire snake.


  • 0

    @zzg_zzm The set of body is for the check of collision. If you only have the queue of snake, it takes O(n) time to check collision, with set, it is O(1).


  • 0

    @Dragon.PW I see. But wouldn't set::count be of O(log N) complexity (still better than queue, you are right)? The unordered_set::count is of O(1) complexity, but probably needs to define a hasher and equal operator.


  • 0

    @zzg_zzm yes, unordered_set is enough, no need to use set. Also, we can just use the equivalent 1D index, instead of pair.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.