Самый быстрый способ генерации большой случайной строки с более низкими латинскими буквами

Ответ 1

Здесь код Python 3, который генерирует 1000000 "случайных" строчных букв в 0.28 секунды (см. также 0.11 -секундное решение в конце, код @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() method (0.11 seconds):

#!/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 skew

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 vs. 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') "отн =" NOFOLLOW" > os.urandom(n). Первый использует Mersenne Twister в качестве основного генератора, который может быть быстрее, чем os.urandom(), который использует источники, предоставленные операционной системой. Последнее более безопасно, если вы используете случайную строку для секретов.

Ответ 2

Используйте string.ascii_lowercase вместо chr для генерации строчных символов:

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 миллион элементов, присоединяем их к большой байтовой строке, а затем пишем, что в одном идет в двоичный буфер stdout.

Присоединение байтов как "медленное" как строка версии:

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

но мы кодируем 26 символов, а не 1 миллион, чтобы сцена записи была быстрее.

Ответ 3

Мое решение, которое только что принято (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 здесь, так как большинство онлайн-судей нас что-то вроде этого проверит на вашем script:

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

Таким образом, вы можете использовать print вместо stdout и raw_input() вместо stdin, хотя для огромных входов stdin.readline выполняется быстрее, чем raw_input().

Обновление 1:

Использование @Markku tip времени выполнения сократилось до 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)] )

Ответ 4

Я получаю огромное улучшение скорости, изменяя от randint (0,25) до int (random() * 25) в вашем исходном решении. На моей машине время составляло от 2 секунд до примерно 0,6 секунды. Если вы посмотрите на код random.py, вы увидите, что randint полон чеков, которые вам не нужны или вам нужны.

update:. Вам нужно int (random() * 26). Спасибо Ashwini

Ответ 5

Попробуйте превратить часть его в С++ или другой скомпилированный язык. Это почти гарантировано сделает его быстрее. К сожалению, Python не слишком быстро, особенно когда дело касается таких вещей. Попробуйте С++, C или Pascal.

EDIT: Также см. Советы по производительности Python

Ответ 6

Сгенерируйте и напишите в кусках, размер которых больше 2.

Может быть, используйте строку или массив из 26 строчных букв и произвольно выберите тогда вместо генерации символов.

Ответ 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