我正在尝试从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秒
randint(97, 122)
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秒 ,但仍未通过测试
这是Python 3代码,可在0.28几秒钟内生成1000000个“随机”小写字母(另请参阅0.11-seconds解决方案;问题中的@Ashwini Chaudhary的代码0.55在我的计算机上需要几秒钟,@ Markku K.的代码- 0.53):
0.28
0.11
0.55
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个字母序列的频率),但使分布偏斜(请参阅最后的解决方法):
% len_lc
$ python3 generate-random.py | python3 check-seq.py
在哪里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给出“超出输出限制”。
generate-random.py
为了提高性能,您可以使用bytes.translate()方法(0.11秒):
bytes.translate()
#!/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))
256(字节数)不能被26(低拉丁字母数)均分,因此该公式min_lc + b % 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发生。要解决此问题,可以丢弃未对齐的字节:
range(256)
'wxyz'
9
10
print(find_skew(range(256 - (256 % 26)))) # -> {9: 'abcdefghijklmnopqrstuvwxyz'}
在此,输入是均匀分布的字节,[0, 234)输出范围是均匀分布的ascii小写字母。
[0, 234)
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循环可能执行多次。
os.urandom
>=234
while
如果random.getrandbits(8*n).to_bytes(n, 'big')使用代替,则时间性能可以提高另一个数量级os.urandom(n)。前者使用Mersenne Twister作为核心生成器,它可能比os.urandom()使用操作系统提供的源更快。如果将随机字符串用于机密,则后者更为安全。
random.getrandbits(8*n).to_bytes(n, 'big')
os.urandom(n)
os.urandom()