最快的方法来生成具有较低的拉丁字母大的随机字符串(Fastest method to generat

我试图解决这个从Timus在线法官的问题。 为了解决这个问题，你需要生成的1 000 000小写拉丁字母顺序，并把它写在1秒标准输入。

这是很容易用C ++或Java来解决这个问题。 我有蟒蛇这里的解决方案：

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.7S：

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

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

而我得到了结果：“时间限制超标”。 所以，问题是“如何做快？”

UPD1：使用randint(97, 122)在16毫秒降低时间。 现在是1.740s

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.924s

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

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

需要1.173s

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.155s

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.901s

UPD4

有些家伙只是解决了上Timus问题。 我希望他会分享他的解决方案:)

UPD5感谢阿什维尼·乔杜里与我们分享他的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.527s我的电脑上，它在Timus通过测试。 但随着Python3.x问题仍然存在。

UPD6由于马尔K.这样的代码：

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.445s，但仍然没有通过测试

Answer 1:

下面是Python 3的代码，在生成1000000“随机”的小写字母0.28秒（另见0.11末-seconds解决方案;从问题@Ashwini乔杜里的代码需要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')是用来代替os.urandom(n) 。 前者采用Mersenne扭曲为核心发电机可能比更快os.urandom()它使用由操作系统提供的源。 如果你使用的秘密随机字符串，后者是更安全的。

Answer 2:

使用string.ascii_lowercase代替chr产生小写charaters：

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)

也写入stdout直接出现要快，在Python编码自己是不是不是它全部的C代码处理速度更快。

我也用一个列表理解; str.join()需要通过输入序列来扫描两次，一次以确定输出的长度，一旦实际拷贝输入元件，以输出字符串。 列表解析，然后击败了速度较慢的发电机，以列表的代码。

只是使用choice(ascii_lowercase)在你从一个整数生成的每个字符的方法是在快两倍：

>>> timeit.timeit('f()', 'from __main__ import yours as f', number=3)
11.299837955011753
>>> timeit.timeit('f()', 'from __main__ import mine as f', number=3)
5.330044150992762

你可以尝试，避免了''.join()通过直接写入单个字符开销stdout ：

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

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

下一步是尝试写原始字节：

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))

但这些都是在没有改善''.join()在我的测试。

接下来，我们移动到一次编码ASCII字符字节，然后使用bytes.join()

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)]))

bal是编码为字节小写ASCII字符，从中随机单击1万件商品，在将其加入到一个大的字节串，然后写一气呵成二进制标准输出缓冲区列表。

该字节的加入是一样“慢”的字符串形式：

>>> timeit.timeit('f()', 'from __main__ import bytes as f', number=3)
5.41390264898655

但我们编码26个字符，而不是百万所以写阶段更快。

Answer 3:

我在原来的解决方案，从randint（0,25）改变为int（随机（）* 25）获得巨大的速度提升。 在我的机器，时间从2秒左右去，到约0.6秒。 如果你看看在random.py代码，你会看到，randint已满，你不想要或需要的检查。

更新：哎呀，关闭一个。 你需要INT（随机（）* 26）。 由于阿什维尼

Answer 4:

我的解决方案，它刚刚被（Python 2.7版，执行时间：0.984）：

from random import choice
from string import ascii_lowercase

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

访问列表的元素是快比字符串。

In [13]: from random import choice

In [14]: from string import ascii_lowercase

In [15]: lis = list(ascii_lowercase)

In [16]: %timeit ''.join(choice(lis) for _ in xrange(10**5))
1 loops, best of 3: 128 ms per loop

In [17]: %timeit ''.join(choice(ascii_lowercase) for _ in xrange(10**5))
1 loops, best of 3: 134 ms per loop

而你并不需要stdout或stdin这里大多数在线审判我们这样的事情来测试你的脚本：

$python script.py <in.txt >out.txt

所以，你可以使用print ，而不是stdout和raw_input()而不是stdin ，但巨额投入stdin.readline比更快raw_input()

更新1：

使用@马尔的提示执行时间减少到0.64在py2.7：

from random import random
from string import ascii_lowercase

lis = list(ascii_lowercase)
print "".join( [lis[int(random() * 26)] for _ in xrange(1000000)] )

Answer 5:

请尝试将它的某些部分为C ++或其他编译语言。 这将几乎可以保证让它更快。 Python中，不幸的是，是不是太快了，特别是当它涉及到这样的事情。 试试C ++，C或帕斯卡 。

编辑：另请参阅Python的性能提示

Answer 6:

生成并在是2在尺寸更大的功率块写。

也许使用26小写字母的字符串或阵列和随机挑选然后代替产生字符的。

Answer 7:

使用random.choices ？

有一个Python 3.6：

import random
import string

%timeit ''.join(random.choices(string.ascii_lowercase, k=10**6))
1 loop, best of 3: 235 ms per loop

文章来源: Fastest method to generate big random string with lower Latin letters