Efficient list building in Python

Question

Being a long-time Matlab user, I am accustomed to getting a caution whenever I build a list/array/anything with multiple elements in a loop such that it changes size every time, because that slows things down.

As I teach myself Python 2.7, I'm wondering if such a rule applies here to strings. I know exactly how long I want my string to be, and I have a specific list of the characters I want to build it from, but otherwise I want it to be random. My favorite code I've written so far is:

def BernSeq(length,freq):
"""Create a Bernoulli sequence - a random bitstring - of the given length 
and with the given frequency of 1s"""
    seq = '0'*length
    for ii in range(length):
        num = np.random.rand(1)
        if num < freq:
            cha = '1'
            seq = seq[:ii] + cha + seq[ii+1:]

I call this as BernSeq(20,.25) and I get the output '10001000000001011101'.

I already tried seq[ii] = '1', but, to put it in IPython's words, TypeError: 'str' object does not support item assignment.

So, am I doing this the most Pythonic way, or is there some sleight of hand that I haven't seen yet - maybe a random string or list generator to which I can directly give a list of characters I want it to randomly choose between, the probability I want each possibility to have, and how long I want this string or list to be?

(I've seen other questions about random strings, but while they do address how to make it the right length, they are generally trying to generate passwords, with all ASCII characters being equally likely. That's not what I want.)

Answer 1

There are several ways of doing it.

First, you can create the correct elements from the start:

seq = "".join("1" if np.random.rand(1) < freq else "0" for _ in range(length))

But the very first question to ask is: what do you want as an output? Do you require it to be a string? Maybe you are ok with a list of booleans?

Then

seq = [np.random.rand(1) < freq for _ in range(length)]

would be enough as well.

Answer 2

You could define a function that produces a random letter, as per your distributional preferences, then perform it the number of times you like.

import random
def my_letter():
   a = random.randint(1,10)
   if a > 5:
   return "a"
   else:
   return "b"

Then for your length preferences:

my_str = ""
for x in range(length):
   my_str += my_letter()

Answer 3

Strings in python are immutable

In [1]: a = '1' * 5

In [2]: a
Out[2]: '11111'

In [3]: type(a)
Out[3]: str

In [4]: a[2] = 'c'
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-4-69ed835eb212> in <module>()
----> 1 a[2] = 'c'

TypeError: 'str' object does not support item assignment

In [5]: b = [1] * 5

In [6]: b
Out[6]: [1, 1, 1, 1, 1]

Adjusting your code to use a int list instead. (minimal fixes, not fixing style or optimizing other things)

def BernSeq(length,freq):
"""Create a Bernoulli sequence - a random bitstring - of the given length 
and with the given frequency of 1s"""
    seq = [0] * length
    for ii in range(length):
        num = np.random.rand(1)
        if num < freq:
            cha = 1
            seq.append(cha)

Answer 4

There is a Binomial distribution in NumPy, np.random.binomial. Sampling from it with your desired frequency and then joining together string representations will be faster than reinventing it yourself.

def bernouilli_str(N, one_freq):
    return ''.join(np.random.binomial(1, one_freq, N).astype('U1'))

Benchmark

In [112]: %timeit ''.join(np.random.binomial(1, 0.75, 10**6).astype('U1'))
637 ms ± 5.75 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [113]: %timeit "".join("1" if np.random.rand(1) < 0.75 else "0" for _ in range(10**6))
1.69 s ± 11 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)