jzhe727's blog

By jzhe727, history, 14 months ago, In English

Python 3 has unlimited size integers, which can function as dynamic size bitsets when doing bitwise operations. Python is still about 3x slower than C++ bitsets with no pragmas and 10x slower than C++ with avx2+O3 pragmas. However, the Python integers have dynamic size, so there some potential of making a problem that requires dynamic bitsets purely to mess with people who use C++ standard library bitsets.

Anyways, here's some simple code I wrote in Python for https://ecna22.kattis.com/problems/amusicalquestion. It is AC in 0.16s.

Code
  • Vote: I like it
  • +18
  • Vote: I do not like it

| Write comment?
»
14 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

AFAIK, there is std::tr2::dynamic_bitset in (and I believe, only in) GCC (reference link here). I think it is to replace std::vector<bool> in a near future, but it is not yet in the standards. It is at least in a "usable" state if I remember correctly.

»
14 months ago, # |
  Vote: I like it +29 Vote: I do not like it

There's a simple way to use static bitsets (with minimal overhead) when dynamic bitsets are needed.

template <uint32_t N> // size_t might give stack frame related warnings
void helper(int n) {
    if (n <= N) {
        bitset<N> b;
        std::cout << "N = " << b.size() << '\n'; // implementation goes here
    } else {
        helper<2 * N>(n);
    }
}

void solve(int n) {
    helper<1>(n);
}

And if you want to limit $$$N$$$ to a certain limit, you can do it using std::enable_if (now you can even use size_t without warnings):

static constexpr size_t MAX_BITSET_SIZE = 10000;

template <size_t N>
std::enable_if<(N <= MAX_BITSET_SIZE)>::type helper(int n) {
    if (n <= N) {
        std::bitset<N> b;
        std::cout << "N = " << b.size() << '\n'; // implementation goes here
    } else {
        if constexpr (2 * N <= MAX_BITSET_SIZE) {
            helper<2 * N>(n);
        }
    }
}

void solve(int n) {
  helper<2>(n);
}

And if you want to be more space efficient about it, consider replacing 2 * N by static_cast<uint32_t>(1.5 * N + 1) or something similar everywhere, though the smaller the increase, the more functions and if checks there will be. In the worst case, if the increase is linear, you'll either have a bloated binary (with potential instruction cache misses) or the compiler will fail to compile the code due to out of memory errors, not to mention the linear search time in this recursive definition.

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Is this a certified way to do bitset in python?

I found python 1 << k can hold 1000 number of bits. Not sure how to do count, any, iterating all 1's in constant time as C++ ? https://leetcode.com/problems/all-paths-from-source-lead-to-destination/submissions/1458994019/?envType=problem-list-v2&envId=topological-sort

    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        N = n + 1
        deg = [0] * N
        g = [[] for _ in range(N)]
        rch = [1 << i for i in range(N)]
        for a, b in edges:
            g[b].append(a)
            deg[a]+= 1
        q = deque()
        for i in range(n): 
            if not deg[i]:
                q.append(i)
        while q:
            x = q.popleft()
            for v in g[x]:
                deg[v]-= 1
                rch[v]|= rch[x]
                if not deg[v]:
                    q.append(v)
        ans = [[] for _ in range(n)]
        for i in range(n):
            for k in range(n):
                if rch[i] & (1<< k) and i != k:
                    ans[k].append(i)
        return ans
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    for count(), you can do like __builtin_popcount() in c++ in $$$\mathcal O(\frac{N}{w})$$$:

    int popcount(unsigned u) {
        u = (u & 0x55555555) + ((u >> 1) & 0x55555555);
        u = (u & 0x33333333) + ((u >> 2) & 0x33333333);
        u = (u & 0x0F0F0F0F) + ((u >> 4) & 0x0F0F0F0F);
        u = (u & 0x00FF00FF) + ((u >> 8) & 0x00FF00FF);
        u = (u & 0x0000FFFF) + ((u >> 16) & 0x0000FFFF);
        return u;
    }
    

    for any() just see if it's 0.

    for iterating all 1s you can use lowbit (count()) times:

    unsigned int lb(unsigned x) {
        return x & (x ^ (x - 1));
    }
    
    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      any is lowbit, I see. Let me study __builtin_popcount

      How to understand 0x0F0F0F0F, 0x5555555 lmao??