生成带有较低拉丁字母的大随机字符串的最快方法

Question

我正在尝试从Timus在线法官那里解决这个问题。要解决此问题，您需要生成1
000 000个小写拉丁字母的序列，并在1秒内将其写入stdin。

使用C ++或Java很容易解决此问题。我在这里有python解决方案：

import os
from random import randint

s = ''.join(chr(97 + randint(0, 25)) for i in range(1000000))
os.write(1, bytes(s, 'utf8'))

需要1.7秒：

$ time python3.3 1219.py > /dev/null

real    0m1.756s
user    0m1.744s
sys     0m0.008s

结果是“超出时间限制”。因此，问题是“如何更快地做到这一点？”

UPD1 ：使用randint(97, 122)减少了16ms的时间。现在是1.740秒

UPD2： @Martijn Pieters的解决方案需要0.979s，但也未通过测试。

UPD3 Martijn Pieters提出了一个很好的解决方案，但是仍然很慢：

from sys import stdin
from random import choice
from string import ascii_lowercase

s = ''.join([choice(ascii_lowercase) for _ in range(1000000)])
stdout.write(s)

耗时 0.924秒

from sys import stdout
from random import choice
from string import ascii_lowercase

for _ in range(1000000):
    stdout.write(choice(ascii_lowercase))

耗时 1.173秒

from sys import stdout
from random import choice
from string import ascii_lowercase
bal = [c.encode('ascii') for c in ascii_lowercase]
out = stdout.buffer

for _ in range(1000000):
    out.write(choice(bal))

需要 1.155秒

from sys import stdout
from random import choice
from string import ascii_lowercase

bal = [c.encode('ascii') for c in ascii_lowercase]
stdout.buffer.write(b''.join([choice(bal) for _ in range(1000000)]))

耗时 0.901秒

UPD4

有人解决了Timus上的问题。我希望他会分享他的解决方案:)

UPD5 感谢Ashwini Chaudhary与我们分享他的Python 2.x解决方案：

from random import choice
from string import ascii_lowercase
lis=list(ascii_lowercase)
print ''.join(choice(lis) for _ in xrange(1000000))

在我的计算机上花费 0.527秒 ，并且通过了 Timus的 测试。但是Python3.x的问题仍然存在。

UPD6 感谢 MarkkuK。此代码：

import os
from random import random
from string import ascii_lowercase

bal = [c.encode('ascii') for c in ascii_lowercase]
os.write(1, b''.join([bal[int(random() * 26)] for _ in range(1000000)]))

耗时 0.445秒 ，但仍未通过测试

Answer 1

这是Python
3代码，可在0.28几秒钟内生成1000000个“随机”小写字母（另请参阅0.11-seconds解决方案；问题中的@Ashwini
Chaudhary的代码0.55在我的计算机上需要几秒钟，@ Markku K.的代码- 0.53）：

#!/usr/bin/env python3
import os
import sys

def write_random_lowercase(n):
    min_lc = ord(b'a')
    len_lc = 26
    ba = bytearray(os.urandom(n))
    for i, b in enumerate(ba):
        ba[i] = min_lc + b % len_lc # convert 0..255 to 97..122
    sys.stdout.buffer.write(ba)

write_random_lowercase(1000000)

% len_lc 尽管它仍然满足条件（ascii，小写字母，1、2、3个字母序列的频率），但使分布偏斜（请参阅最后的解决方法）：

$ python3 generate-random.py | python3 check-seq.py

在哪里check-seq.py：

#!/usr/bin/env python3
import sys
from collections import Counter
from string import ascii_lowercase

def main():
    limits = [40000, 2000, 100]

    s = sys.stdin.buffer.readline() # a single line
    assert 1000000 <= len(s) <= 1000002 # check length +/- newline
    s.decode('ascii','strict') # check ascii
    assert set(s) == set(ascii_lowercase.encode('ascii')) # check lowercase

    for n, lim in enumerate(limits, start=1):
        freq = Counter(tuple(s[i:i+n]) for i in range(len(s)))
        assert max(freq.values()) <= lim, freq

main()

注意：在acm.timus.ru上generate-random.py给出“超出输出限制”。

为了提高性能，您可以使用bytes.translate()方法（0.11秒）：

#!/usr/bin/env python3
import os
import sys

# make translation table from 0..255 to 97..122
tbl = bytes.maketrans(bytearray(range(256)),
                      bytearray([ord(b'a') + b % 26 for b in range(256)]))
# generate random bytes and translate them to lowercase ascii
sys.stdout.buffer.write(os.urandom(1000000).translate(tbl))

如何解决% len_lc偏斜

256（字节数）不能被26（低拉丁字母数）均分，因此该公式min_lc + b % len_lc使某些值出现的频率比其他值少，例如：

#!/usr/bin/env python3
"""Find out skew: x = 97 + y % 26 where y is uniform from [0, 256) range."""
from collections import Counter, defaultdict

def find_skew(random_bytes):
    char2freq = Counter(chr(ord(b'a') + b % 26) for b in random_bytes)
    freq2char = defaultdict(set)
    for char, freq in char2freq.items():
        freq2char[freq].add(char)
    return {f: ''.join(sorted(c)) for f, c in freq2char.items()}

print(find_skew(range(256)))
# -> {9: 'wxyz', 10: 'abcdefghijklmnopqrstuv'}

这里，输入range(256)是均匀分布的（每个字节正好一次出现），但'wxyz'在输出信往往小于其余部分9与10发生。要解决此问题，可以丢弃未对齐的字节：

print(find_skew(range(256 - (256 % 26))))
# -> {9: 'abcdefghijklmnopqrstuvwxyz'}

在此，输入是均匀分布的字节，[0, 234)输出范围是均匀分布的ascii小写字母。

bytes.translate() 接受第二个参数来指定要删除的字节：

#!/usr/bin/env python3
import os
import sys

nbytes = 256
nletters = 26
naligned = nbytes - (nbytes % nletters)
tbl = bytes.maketrans(bytearray(range(naligned)),
                      bytearray([ord(b'a') + b % nletters
                                 for b in range(naligned)]))
bytes2delete = bytearray(range(naligned, nbytes))
R = lambda n: os.urandom(n).translate(tbl, bytes2delete)

def write_random_ascii_lowercase_letters(write, n):
    """*write* *n* random ascii lowercase letters."""    
    while n > 0:
        # R(n) expected to drop `(nbytes - nletters) / nbytes` bytes
        # to compensate, increase the initial size        
        n -= write(memoryview(R(n * nbytes // naligned + 1))[:n])

write = sys.stdout.buffer.write
write_random_ascii_lowercase_letters(write, 1000000)

如果随机生成器（os.urandom此处）产生的长字节序列超出了对齐范围（>=234），则while循环可能执行多次。

如果random.getrandbits(8*n).to_bytes(n, 'big')使用代替，则时间html" target="_blank">性能可以提高另一个数量级os.urandom(n)。前者使用Mersenne
Twister作为核心生成器，它可能比os.urandom()使用操作系统提供的源更快。如果将随机字符串用于机密，则后者更为安全。