PiStroke's blog

Storing boolean array-like object of size 1e9 in Python3
By PiStroke, history, 3 years ago, In English

Recently, I came across this blog which explains bitwise operations in vector <bool> (c++).

Problem: You are given 10**7 integers in the range [0,10**9], find the number of distinct integers.

In python making a boolean list/array wouldn't help, an integer will occupy at least 24 bits and a bool will occupy 8 bits, the issue is it would lead to MLE, which isn't desirable!

Are there any python alternatives for vector <bool>?

I looked up numPy (even though it's not allowed in online Judge) but it doesn't seem to have one. Bitarray might be of some help, but I believe it's not allowed in Online Judge either.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can make a bootleg std::bitset in python, make an array(let's call it just arr) of 10**9/32 integers, and do arr[x // 32] |= 1 << (x % 32) for every x in input array. Then afterwards you find number of 1 bits in all elements of arr.

Btw I am not sure about the complexity of doing so, in C++ you can count 1 bits in O(1). If that's not the case in Python, then you probably can't do the problem in python without getting TLE, a better try would be to put input array through a set and find its length.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually thinking about it, you can find the number of set bits implicitly.

    Code would be something like this:

    import sys
input = sys.stdin.readline
a = [int(x) for x in input().split()]
arr = [0] * (10**9 // 32)
ans = 0
for x in a:
    i = x // 32
    j = x % 32
    ans -= (arr[i] >> j) & 1
    arr[i] |= 1 << j
    ans += 1
print(ans)
    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There is an array module contains arrays as same as c arrays and contains bool array. 

from array import array
vis=array('b',[0]*10)   # 'b' mean bool variable

You can see more about this arrays in my previous blog

→ Reply