Generate Sequence of Booleans Quickly in Python

Question

I have a for loop that looks like this, and am looking to make it faster.

mylist = range(100)

def normalrandom():
    for a in range(100):
        b = random.getrandbits(1)
        if b==1: #do something with mylist[a]

My list has ~100 elements, and I know calls to random are expensive. Is there a faster way to make just one call to random, and get 100 random booleans?

Edit: Here is the best solution so far.

def fastrandom(): 
    s = list(range(100))
    res = [i for i in s if random.random() >= .5]
    for item in res:
        #do something with mylist[item]

normalrandom: 0:00:00.591000
fastrandom: 0:00:00.293000

Have you benchmarked this code and found that it is the bottleneck of your application? — Blender
– Blender, Commented Aug 1, 2013 at 5:26
I'm running a monte carlo simulation, so this is the application :) — user1935929
– user1935929, Commented Aug 1, 2013 at 6:21

Jonathon Reinhart · Accepted Answer · 2013-08-01 06:03:00Z

2

This seems to work pretty nicely. It returns a generator object, so the only memory usage is the n-bit integer r.

Edit: Don't use this!

import random

def rand_bools(n):
    r = random.getrandbits(n)
    return ( bool((r>>i)&1) for i in xrange(n) )

Usage:

>>> for b in rand_bools(4): print b
...
False
True
False
True

It works by successively shifting r, masking off the low bit, and converting it to a bool every iteration.

EDIT: The moral of the story is to benchmark your code! After taking the hint from Blender, I wrote the following test:

import random
import time

def test_one(N):
    a = 0
    t0 = time.time()
    for i in xrange(N):
        if random.getrandbits(1):  a += 1
    return time.time() - t0

def rand_bools_int_func(n):
    r = random.getrandbits(n)
    return ( bool((r>>i)&1) for i in xrange(n) ) 

def test_generator(gen):
    a = 0
    t0 = time.time()
    for b in gen:
        if b:  a += 1
    return time.time() - t0  

def test(N):
    print 'For N={0}'.format(N)
    print '  getrandbits(1) in for loop              {0} sec'.format(test_one(N))

    gen = ( not random.getrandbits(1) for i in xrange(N) )
    print '  getrandbits(1) generator using not      {0} sec'.format(test_generator(gen))

    gen = ( bool(random.getrandbits(1)) for i in xrange(N))
    print '  getrandbits(1) generator using bool()   {0} sec'.format(test_generator(gen))

    if (N < 10**6):     # Way too slow!
        gen = rand_bools_int_func(N)
        print '  getrandbits(n) with shift/mask          {0} sec'.format(test_generator(gen))

def main():
    for i in xrange(3,8):
       test(10**i)

if __name__ == '__main__':
   main()

The results:

C:\Users\Jonathon\temp>python randbool.py
For N=1000
  getrandbits(1) in for loop              0.0 sec
  getrandbits(1) generator using not      0.0 sec
  getrandbits(1) generator using bool()   0.0 sec
  getrandbits(n) with shift/mask          0.0 sec
For N=10000
  getrandbits(1) in for loop              0.00200009346008 sec
  getrandbits(1) generator using not      0.00300002098083 sec
  getrandbits(1) generator using bool()   0.00399994850159 sec
  getrandbits(n) with shift/mask          0.0169999599457 sec
For N=100000
  getrandbits(1) in for loop              0.0230000019073 sec
  getrandbits(1) generator using not      0.029000043869 sec
  getrandbits(1) generator using bool()   0.0380001068115 sec
  getrandbits(n) with shift/mask          1.20000004768 sec
For N=1000000
  getrandbits(1) in for loop              0.233999967575 sec
  getrandbits(1) generator using not      0.289999961853 sec
  getrandbits(1) generator using bool()   0.37700009346 sec
For N=10000000
  getrandbits(1) in for loop              2.34899997711 sec
  getrandbits(1) generator using not      2.89400005341 sec
  getrandbits(1) generator using bool()   3.76900005341 sec

In conclusion, my answer was a "fun* solution, but don't use it! It is much faster to simply use random.getrandbits(1).

edited Aug 1, 2013 at 6:03

answered Aug 1, 2013 at 5:27

Jonathon Reinhart

138k38 gold badges266 silver badges347 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Blender Over a year ago

This becomes slower than getrandbits(1) for large (~1000 items) lists.

Blender Over a year ago

Also, not is faster than bool.

Jonathon Reinhart Over a year ago

@Blender Wow, you aren't kidding. Just added benchmark results.

Jonathon Reinhart Over a year ago

@Blender I'm really interested in why not would be faster than bool.

mata · Accepted Answer · 2013-08-01 06:05:01Z

Here are some timings for different methods:

code:

from random import getrandbits, randint, random, sample

s = list(range(100))

def loop_bits():
    res = []
    b = getrandbits(len(s))
    for i in s:
        if b % 2 == 0:
            res.append(i)
        b >>= 1

def comp_bits():
    res = [i for i in s if getrandbits(1)]

def comp_randint():
    res = [i for i in s if randint(0, 1)]

def comp_random():
    res = [i for i in s if random() >= .5]

And the results for different interperters:

$ python2.7 -m timeit -s 'import randtest' 'randtest.loop_bits()'
10000 loops, best of 3: 97.7 usec per loop
$ python2.7 -m timeit -s 'import randtest' 'randtest.comp_bits()'
10000 loops, best of 3: 55.6 usec per loop
$ python2.7 -m timeit -s 'import randtest' 'randtest.comp_randint()'
1000 loops, best of 3: 306 usec per loop
$ python2.7 -m timeit -s 'import randtest' 'randtest.comp_random()'
10000 loops, best of 3: 25.5 usec per loop
$ 
$ pypy -m timeit -s 'import randtest' 'randtest.loop_bits()'
10000 loops, best of 3: 44 usec per loop
$ pypy -m timeit -s 'import randtest' 'randtest.comp_bits()'
10000 loops, best of 3: 41 usec per loop
$ pypy -m timeit -s 'import randtest' 'randtest.comp_randint()'
100000 loops, best of 3: 14.4 usec per loop
$ pypy -m timeit -s 'import randtest' 'randtest.comp_random()'
100000 loops, best of 3: 12.7 usec per loop
$ 
$ python3 -m timeit -s 'import randtest' 'randtest.loop_bits()'
10000 loops, best of 3: 53.7 usec per loop
$ python3 -m timeit -s 'import randtest' 'randtest.comp_bits()'
10000 loops, best of 3: 48.9 usec per loop
$ python3 -m timeit -s 'import randtest' 'randtest.comp_randint()'
1000 loops, best of 3: 436 usec per loop
$ python3 -m timeit -s 'import randtest' 'randtest.comp_random()'
10000 loops, best of 3: 22.2 usec per loop

So, in all cases the last (a comprehension using random.random() was by far the fastest.

eri · Accepted Answer · 2013-08-01 06:16:02Z

0

Try this:

mylist = range(100)
todolist= filter(lambda x: random.getrandbits(1),mylist)
todolist
[0, 4, 7, 8, 11, 13, 15, 16, 20, 21, 22, 23, 24, 25, 29, 33, 34, 35, 36, 37, 38, 40, 41, 42, 43, 52, 53, 54, 56, 59, 64, 67, 68, 70, 71, 80, 81, 82, 85, 89, 90, 93, 95, 96, 97, 99]
len(todolist)
46
for item in todolist : do_work(item)

answered Aug 1, 2013 at 6:16

eri

3,6142 gold badges30 silver badges46 bronze badges

Comments

bossi · Accepted Answer · 2013-08-01 06:36:09Z

0

How about generating a random binary string

import random

rand_sequence = [random.randint(0, 1) for x in range(100)]

and then accessing the string array through an index

for i in range(len(rand_sequence)):
    if bool(rand_sequence [i]):
        # do something here

Alternatively, you could generate a string of random ints from set (0, 1) as well through

rand_sequence = str(bin(random.getrandbits(100)))[2:].zfill(100)

edited Aug 1, 2013 at 6:36

answered Aug 1, 2013 at 5:31

bossi

1,74413 silver badges19 bronze badges

6 Comments

Blender Over a year ago

rand_bin_str doesn't have a constant length.

user1935929 Over a year ago

edit suggested to fix rand_bin_str length: add on .zfill(100)

bossi Over a year ago

@Blender: You're exactly right, thanks for pointing it out, I have fixed the code to return a list of random integers from set (0, 1).

bossi Over a year ago

@user1935929: Thanks for the idea; even though padding with a static value would be something to avoid in a situation where randomness is the objective, I have put it back in include your suggestion.

user1935929 Over a year ago

@bossi The leading positions still are random. Any leading 0s are generated randomly, chopped off using bin, and added back on using zfill... so the net effect of bin chopping & zfill adding is that any leading 0s are removed & replaced, ie there is no net change to the bitstring; so the leading 0s are still random.

|

br3nt · Accepted Answer · 2021-07-15 11:32:17Z

0

Just putting this here for me to find in the future...

import random

def random_array(i):
  return [bool(random.getrandbits(1)) for i in range(i)]

Usage:

>>> random_array(10)
[False, False, True, True, True, True, True, True, True, False]

>>> random_array(10)
[False, True, True, False, False, True, True, True, False, True]

>>> random_array(10)
[False, True, False, False, True, True, True, True, False, True]

answered Jul 15, 2021 at 11:32

br3nt

9,7543 gold badges47 silver badges67 bronze badges

Collectives™ on Stack Overflow

Generate Sequence of Booleans Quickly in Python

5 Answers 5

4 Comments

Comments

Comments

6 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

4 Comments

Comments

Comments

6 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related