Fastest / most efficient random bit indexing in Python
What exactly do you want to do with your array of booleans? If you used numpy, you could instantiate your boolean array as an array of uint8 one eighth the size of the boolean array, e.g.

In [38]: a = np.random.randint(256, size=(1000000//8,)).astype(np.uint8)


To extract items, you could do something like:

In [39]: def get_bools(a, i):
   ....:     b = i // 8
   ....:     o = i % 8
   ....:     mask = 1 &lt;&lt; o
   ....:     return (a[b] &amp; mask) != 0
   ....:


If you run this to extract a single item, the speed is appalling:

In [40]: idx = 500000

In [41]: %timeit get_bools(a, idx)
100000 loops, best of 3: 4.53 us per loop


But if you do it for 1000 items at once, things look (much) better:

In [42]: idx = np.random.randint(1000000, size=(1000,))

In [43]: %timeit get_bools(a, idx)
10000 loops, best of 3: 31.1 us per loop


Note that the last timing means ~30 ns per item retrieved, right where you wanted to be.

If you need to extract the boolean values one at a time, you are going to have to deal with the painful Python overhead. Notice that simply getting a single item from an array is terribly slow:

In [44]: %timeit a[62500]
10000000 loops, best of 3: 135 ns per loop


But if you can vectorize your code with numpy, or use a C array directly from cython, then you should have no problem in achieving your speed goal.