Why vector<bool> so slow? Isn't it optimized?


  • 0
    G

    Following is one 12ms answer @aileenbai, original post: 12ms-c-solution

    class Solution {
    public:
      int countPrimes(int n) {
        if(--n < 2) return 0;
        int m = (n + 1)/2, count = m, k, u = (sqrt(n) - 1)/2;
        bool notPrime[m] = {0};   // <---------   this line
    
        for(int i = 1; i <= u;i++) {
          if(!notPrime[i]) {
            for(k = (i+ 1)*2*i; k < m;k += i*2 + 1)
              if (!notPrime[k]) {
                notPrime[k] = true;
                count--;
              }
          }
        }
        return count;
      }
    };
    

    If you change "this line" from bool notPrime[m] = {0} to vector<bool> notPrime(m, 0), running time increases from 12ms to 100+ms.....


  • 2
    S

    Read this, vector<bool> is a specialized version of vector, which is used for elements of type bool and optimizes for space. In any case, it is not possible to instantiate the unspecialized template of vector for bool directly. Workarounds to avoid this range from using a different type (char, unsigned char) or container (like deque) to use wrapper types or further specialize for specific allocator types. You should use vector<char> notPrime(m, 0);, instead of vector<bool> notPrime(m, 0); to fix the performance issue.


  • 0
    G

    Thanks for the link. I think the essence of the problem is that vector<bool> "favors memory optimization over processing".


Log in to reply
 

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