Найти - Пользователи
Полная версия: Оптимизация генерации рандомной строки
Начало » Python для экспертов » Оптимизация генерации рандомной строки
1
jon34
При генерации строки длинной 100 000 000 скрипт работает 1 мин 22 сек, подскажите как можно оптимизировать или переписать более оптимально существующий код?
 import math
import random
import multiprocessing as mp
  
from multiprocessing.managers import ListProxy
 
from config import ConfigParser
 
 
def get_symbol(alphabet: dict):
    """
    Генератор создающий последовательность из полученных символов с заданной
    веростяность и при каждом запросе возвращает случайный
    :param alphabet словарь символов из которых будет генерится строка с
    заданной вероятностью для каждого из символов
    """
    seq = sum([[key] * alphabet[key] for key in alphabet], [])
    while True:
        yield random.choice(seq)
 
 
def generate_str(symbols, str_len: int):
    """
    Генерирует строку из заданных символов с указанной вероятностью
    :param alphabet словарь символов из которых будет генерится строка с
    заданной вероятностью для каждого из символов
    :param str_len длинна генерируемой строки
    """
    return ''.join([next(symbols) for _ in range(str_len)])
 
 
def calc_entropy(alphabet: dict):
    return sum([-p / 100 * math.log(p / 100, 2) for p in alphabet.values()])
 
 
def calc_parts(str_len: int):
    """
    Считает какой длинны генерировать строку каждому из процессов
    :param str_len: общая длинна строки
    """
    parts = [str_len // mp.cpu_count()] * mp.cpu_count()
    diff = str_len - sum(parts)
    if diff != 0:
        parts[-1] += diff
    return parts
 
 
def wrapper_generate_str(symbols, str_len: int, out: ListProxy):
    out.append(generate_str(symbols, str_len))
 
 
conf = ConfigParser()
 
symbols = get_symbol(conf.alphabet)
all_process = []
manager = mp.Manager()
out = manager.list()
 
for length in calc_parts(conf.length):
    process = mp.Process(
        target=wrapper_generate_str, args=(symbols, length, out)
    )
    process.start()
    all_process.append(process)
 
for i in all_process:
    i.join()
 
text = ''.join(out)
# print(text)
print('Энтропия равна: {}'.format(calc_entropy(conf.alphabet)))
scidam
Для вашей задачи можно попробовать пакет NumPy (он написан на C и работает быстрее), там уже есть функция для выбора элементов с заданной вероятностью.
Привожу пример со случайно назначаемыми вероятностями для строки из символов (your_symbols), которые выбираются случайно:

 python -m timeit -s "import numpy as np; your_symbols='abcdefgh'; probs = np.random.rand(len(your_symbols)); probs=probs/sum(probs);" "np.random.choice(list(your_symbols), p=probs, size=100000000)"
10 loops, best of 3: 4.84 sec per loop

Таким образом, время генерации заняло около 5 сек.
Компьютер,на котором тестировалось: 4x3.2GHz AMD, 4MB RAM, Linux 3.16.7-21; Numpy v. 1.11.1, python2.7
jon34
scidam
Да, numpy отличная вещь, но как мне на нем реализовать именно ту функциональность, что была до этого? На сколько я понял сейчас происходит генерация просто рандомной строки, а мне надо строку в которой символы встречаются с заданной вероятнотью.
scidam
Приведенный пример как раз для случая генерации символов с заданной вероятностью, только вероятности там выбирались случайно. np.random.choice(a, p=p, size=size) осуществляет выбор символов из списка a, где в p заданы вероятности встречаемости, size - размер генерируемой выборки:
 import numpy as np
symbols = ['a', 'b', 'c']
np.random.choice(symbols, p=[0.2, 0.5, 0.3], size=100)
# Это сгенерирует массив из 100 символов a,b,c, с вероятностями их выпадения 0.2, 0.5 и 0.3 соответственно.
jon34
scidam
Огромное спасибо)

Ещё вопрос назрел, как с помощью numpy превратить сгенерированный массив символов в строку. То есть как там сделать вот такую вещь
''.join(['1', '2', '3'])
scidam
Полагаю, что самый быстрый способ объединить все символы в строку это:
numpy_array.view('Sxx'), где xx – количество объединяемых символов

Пример:
 x = np.array(['a','b','c'] + ['d']*1000)
# len(x) = 1003
concatenated = x.view('S'+str(len(x)))[0]
# concatenated - видимо то, что нужно
jon34
scidam
Что-то этот код генерит даже не похожее на то, что надо.
scidam
Последний код это просто пример объединения символов в строку:
 >>> x = np.array(['a','b','c'] + ['d']*10)
>>> x
array(['a', 'b', 'c', 'd', 'd', 'd', 'd', 'd', 'd', 'd', 'd', 'd', 'd'], 
      dtype='|S1')
>>> x.view('S'+str(len(x)))[0]
'abcdddddddddd'

np.random.choice из примеров выше выдает массив символов с заданными вероятностями, а этот код позволяет получить из этого массива строку.

  import numpy as np
symbols = ['a', 'b', 'c']
x = np.random.choice(symbols, p=[0.2, 0.5, 0.3], size=100)
result_string = x.view('S'+str(len(x)))[0]

Вот результат запуска последнего варианта:
 >>> result_string
'bcbbcbbcbcbbaabbbbbcabbccbaccbcbcbacbbbbbacaaccbabbcbabaabbbcbbbbcbbcbcaabbaccbbbbbccbcbaabccbccabac'
>>> result_string.count('b')
51
>>> result_string.count('c')
30
>>> result_string.count('a')
19
>>>



jon34
Огромное спасибо за все пояснения и ответы.
This is a "lo-fi" version of our main content. To view the full version with more information, formatting and images, please click here.
Powered by DjangoBB