Generating a large random string

[Andreas Lobinger]

Aloha,
i wanted to ask another problem, but as i started to build an example...

How to generate (memory and time)-efficient a string containing
random characters? I have never worked with generators, so my solution
at the moment is:

import string
import random
random.seed(14)
d = [random.choice(string.letters) for x in xrange(3000)]
s = "".join(d)
print s

which is feasible for the 3000, but i need lengths in the range
10.000 to 1.000.000.

Hoping for an answer and wishing a happy day
LOBI

 

[Chris]

How are you planning on using this large random string? If you are just
planning on printing, you can write:

for i in xrange(100000):
sys.stdout.write(random.choice(string.letters))

and it will dump lots of garbage to the screen pretty quickly. If you're
looking to do something else with the data, be specific about what you're
trying to do.

Chris

 

[Sean Ross]

[snip]

How to generate (memory and time)-efficient a string containing
random characters? I have never worked with generators, so my solution
at the moment is:

import string
import random
random.seed(14)
d = [random.choice(string.letters) for x in xrange(3000)]
s = "".join(d)
print s

which is feasible for the 3000, but i need lengths in the range
10.000 to 1.000.000.

[snip]

There are several things to try, but here's one attempt that's
relatively fast but whose time (and size) still grow linearly
with the size of n:


from string import letters
from random import choice, sample, seed

# Note: should probably use timeit.py but this will do ...
from time import clock as now

n = 1000000

# your approach
seed(14)
start = now()
s = ''.join([choice(letters) for i in xrange(n)])
took = now() - start
print "old way n: %d took: %2.2fs"%(n, took)

# different approach
seed(14)
# add 1 so population > sample size (n)
factor = n/len(letters) + 1
start = now()
s = ''.join(sample(letters*factor, n))
took = now() - start
print "new way n: %d took: %2.2fs"%(n, took)


# Output: tested on Windows 98 500+mhz 128MB
old way n: 1000000 took: 23.94s
new way n: 1000000 took: 8.90s

There's a start ...

Sean

 

[Sean Ross]

[snip]

# different approach
seed(14)
# add 1 so population > sample size (n)
factor = n/len(letters) + 1
start = now()
s = ''.join(sample(letters*factor, n))
took = now() - start
print "new way n: %d took: %2.2fs"%(n, took)

[snip]

There's a problem with this method as it appears
random.sample is done without replacement, e.g.

from random import sample
sample(range(10), 10) [9, 5, 3, 2, 0, 8, 4, 1, 6, 7]

Sorry about that,
Sean

 

[Sean Ross]

Here's a sample with replacement, where k can be greater than
len(population):

from random import random, seed
from string import letters
from time import clock as now

# derived from random.sample code ... scarcely tested
def sample(population, k):
"""Chooses k random elements from a population sequence. """
n = len(population)
result = [None] * k
for i in xrange(k):
j = int(random() * n)
result = population[j]
return result

n = 1000000
seed(14)
start = now()
s = ''.join(sample(letters, n))
took = now() - start
print "sample with replacement n: %d took: %2.2fs"%(n, took)

# Output
Even faster than before, and more correct to boot, heh.

 

[Jeff Epler]

I'm pretty sure that the two methods you mention don't give results with
the same distribution.

Instead of letters, let's choose from "01", and choose a string of
length 2.

def f1():
return ''.join([choice("01") for i in xrange(2)])

def f2():
return ''.join(sample("01" * 2, 2))

def test():
for f in (p1, p2):
p = {}
for i in range(1000):
o = f()
p[o] = p.get(o, 0) + 1
print p

[jepler@parrot src]$ ./python /tmp/ross.py
{'11': 25212, '10': 24904, '00': 24996, '01': 24888}
{'11': 16800, '10': 33289, '00': 16705, '01': 33206}

As you can see p1 picks evenly from the 4 alternatives, while p2 favors
the outcomes that have different contents (01 and 10) over the ones that
are a repetition of the same symbol (00 and 11).


Jeff

 

[Paul Rubin]

How to generate (memory and time)-efficient a string containing
random characters? I have never worked with generators, so my solution
at the moment is:

What do you want to do with the random characters, and what OS are you
running on?

import string
import random

If you're using the random characters for some security-related purpose,
you shouldn't use the random module.

If you're running Linux or *BSD, the simplest way to get good quality
random characters is something like

s = open("/dev/urandom").read(3000)

or however many characters you want. For Windows, it's harder.

random.seed(14)
d = [random.choice(string.letters) for x in xrange(3000)]
s = "".join(d)
print s

which is feasible for the 3000, but i need lengths in the range
10.000 to 1.000.000.

Try something like:

import array
from random import randint
d = array.array('B')
for i in xrange(1000000):
d.append(randint(0,255))
s = d.tostring()

 

[Sean Ross]

I'm pretty sure that the two methods you mention don't give results with
the same distribution.

[snip]

Yep. I made an error choosing random.sample() as its sampling is
done without replacement. See my subsequent post with a sample
function that uses replacement and allows for sampling beyond the
population size. That version has a better distribution:

{'11': 266, '10': 251, '00': 245, '01': 238}

 

[Sean Ross]

[snip]

import array
from random import randint
d = array.array('B')
for i in xrange(1000000):
d.append(randint(0,255))
s = d.tostring()

Hi.

Actually, that is pretty slow: 42.79s (on my machine)

The OP's solution took 23.94s
My sampling with replacement took 7.68s

No doubt someone else will come up with something faster.

I'd be interested to see how

s = open("/dev/urandom").read(3000)

compares, and, if better, whether something similar can
be done on Windows.

 

[Paul Rubin]

I'd be interested to see how

s = open("/dev/urandom").read(3000)

compares, and, if better, whether something similar can
be done on Windows.

On Linux, this is almost instantaneous. Reading 1 megabyte takes
under a second on my 700 mhz P3.

 

[Roy Smith]

How to generate (memory and time)-efficient a string containing
random characters?

Find a perl file on your system and read it?

 

[Sean Ross]

On Linux, this is almost instantaneous. Reading 1 megabyte takes
under a second on my 700 mhz P3.

And when you've done

s = open("/dev/urandom").read(1000000)

is s a string containing one million letters [a-zA-Z] and no other
types of characters, as the OP is looking for?

I've never used /dev/urandom, so I don't know what kind of stuff
is being read from there - but I suspect further processing would
be needed to meet the OP's requirements. I'll check it out.

Thanks
Sean

 

[Roger Binns]

How to generate (memory and time)-efficient a string containing
It depends how random you need it to be.

The approach I take in my test harness (which generates a CSV file
with random contents) is to create a 30,000 character string the
old fashioned way:

"".join([random.choice(item) for i in range(30000)])

item is a string of which characters to choose from (some fields
are phone numbers, some are names, some are email addresses etc).

To generate a random string I then take random slices of that
30,000 character object. If I need longer strings, I glue
the random slices together (in a cStringIO).

Roger

 

[Paul Rubin]

s = open("/dev/urandom").read(1000000)

is s a string containing one million letters [a-zA-Z] and no other
types of characters, as the OP is looking for?

Oh oops, I didn't catch that part. It's a million random bytes.
Sorry.

 

[Paul Rubin]

And when you've done

s = open("/dev/urandom").read(1000000)

is s a string containing one million letters [a-zA-Z] and no other
types of characters, as the OP is looking for?

Oops, per other post, it gives strings of bytes and needs filtering.
The following runs in about 1.2 seconds on my machine, but has an
small (infinitesimal) chance of failure:

import string,array,time
t=time.time()
ttab = string.letters*4 + '\0'*48
a = array.array('B', open("/dev/urandom").read(1500000).translate(ttab))
a = array.array('B', filter(abs,a)).tostring()[:1000000]
print time.time()-t

 

[Andreas Lobinger]

Aloha,

How to generate (memory and time)-efficient a string containing
random characters?

d = [random.choice(string.letters) for x in xrange(3000)]
s = "".join(d)

1) Sorry for starting a new thread, but there were calls for more spec.
2) Thanks for all replies so far.

To be more specific about
- OS/availability of /dev/random
Im looking for an elegant solution for all types. At the moment i'm
developing in parallel on a slow (250MHz) i86/Win95 notebook, a typical
i86/linux box and a couple of SUNs (up to 16GB main-mem...).

- using random / crypto-safe-strings
The use of random is intended, because it generates a known sequence.
I can store the seed an re-generate the sequence any time, and afaik
the sequence is OS/machinetype independent.

As i wrote in the original post, the random string is only a prerequisite
for another question.

- What to do with the string
I use the sting as a testpattern for a tokenizer/parser. So the usage
of string.letters is only used as an example here.

The main question was:
How to concat a string without contantly reallocating it.

Wishing a happy day
LOBI

 

[Peter Otten]

Oops, per other post, it gives strings of bytes and needs filtering.
The following runs in about 1.2 seconds on my machine, but has an
small (infinitesimal) chance of failure:

import string,array,time
t=time.time()
ttab = string.letters*4 + '\0'*48
a = array.array('B', open("/dev/urandom").read(1500000).translate(ttab))
a = array.array('B', filter(abs,a)).tostring()[:1000000]
print time.time()-t

from __future__ import division
import array, random, string, sys

identity = string.maketrans("", "")
ld = 256//len(string.letters)
rest = 256 % len(string.letters)
ttab = string.letters*ld + '\0'*rest
dtab = identity[-rest:]

# a fully functional variant of your approach
def randstrUnix(length, extra=1.25):
a = open("/dev/urandom").read(int(length*extra)).translate(ttab, dtab)
while len(a) < length:
a += randstrUnix(length-len(a), 1.3)
return a[:length]

twoletters = [c+d for c in string.letters for d in string.letters]

# the fastest pure-python version I was able to produce
def randstrPure(length):
r = random.random
n = len(twoletters)
l2 = length//2
lst = [None] * l2
for i in xrange(l2):
lst = twoletters[int(r() * n)]
if length & 1:
lst.append(random.choice(string.letters))
return "".join(lst)

The timings:

$ timeit.py -s"import randchoice as r" "r.randstrUnix(1000000)"
10 loops, best of 3: 2.29e+05 usec per loop
$ timeit.py -s"import randchoice as r" "r.randstrPure(1000000)"
10 loops, best of 3: 6.51e+05 usec per loop

A factor of 3 would hardly justify the OS-dependency in most cases.
Note that using twoletters[int(r() * n)] as seen in Sean Ross' version
instead of random.choice(twoletters) doubled the speed.

Peter

 

[Chris]

If you're looking to have a string that you can write to in a stream, like a
file, you might try StringIO
s.write(random.choice(string.letters))
1000000

This works fine for strings up to 10 MB, after that you might want to
consider stashing your data to disk and reading/writing in chunks.

Chris

Aloha,

How to generate (memory and time)-efficient a string containing
random characters?

d = [random.choice(string.letters) for x in xrange(3000)]
s = "".join(d)

1) Sorry for starting a new thread, but there were calls for more spec.
2) Thanks for all replies so far.

To be more specific about
- OS/availability of /dev/random
Im looking for an elegant solution for all types. At the moment i'm
developing in parallel on a slow (250MHz) i86/Win95 notebook, a typical
i86/linux box and a couple of SUNs (up to 16GB main-mem...).

- using random / crypto-safe-strings
The use of random is intended, because it generates a known sequence.
I can store the seed an re-generate the sequence any time, and afaik
the sequence is OS/machinetype independent.

As i wrote in the original post, the random string is only a prerequisite
for another question.

- What to do with the string
I use the sting as a testpattern for a tokenizer/parser. So the usage
of string.letters is only used as an example here.

The main question was:
How to concat a string without contantly reallocating it.

Wishing a happy day
LOBI

 

[Josiah Carlson]

This works fine for strings up to 10 MB, after that you might want to

consider stashing your data to disk and reading/writing in chunks.

Or he could use mmap. It handles all of that for you, is mutable, and
can be used as a replacement for strings in most places.

- Josiah

 

[Chris]

I suppose this would be cheating?
"Hey Rocky, watch me pull a random string out of my hat!"
def __init__(self, item):
self.__item = item

def __getitem__(self, key):
if type(key) is int:
return random.choice(self.__item)
elif type(key) is slice:
return ''.join([random.choice(self.__item)
for i in xrange(*key.indices(sys.maxint))])
else:
raise TypeError('Time to get a new hat!')

ReallyRandomString('spam')[1000:1060]

'mapsmpspapaaamppmapammaasapmaspmspmpppmpmamsmpsaspamaamssspm'

Chris

It depends how random you need it to be.

The approach I take in my test harness (which generates a CSV file
with random contents) is to create a 30,000 character string the
old fashioned way:

"".join([random.choice(item) for i in range(30000)])

item is a string of which characters to choose from (some fields
are phone numbers, some are names, some are email addresses etc).

To generate a random string I then take random slices of that
30,000 character object. If I need longer strings, I glue
the random slices together (in a cStringIO).

Roger