Форум сайта python.su
При генерации строки длинной 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)))
Отредактировано jon34 (Окт. 6, 2016 23:44:29)
Офлайн
Для вашей задачи можно попробовать пакет 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
Отредактировано scidam (Окт. 7, 2016 03:54:15)
Офлайн
scidam
Да, numpy отличная вещь, но как мне на нем реализовать именно ту функциональность, что была до этого? На сколько я понял сейчас происходит генерация просто рандомной строки, а мне надо строку в которой символы встречаются с заданной вероятнотью.
Офлайн
Приведенный пример как раз для случая генерации символов с заданной вероятностью, только вероятности там выбирались случайно. 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 соответственно.
Отредактировано scidam (Окт. 7, 2016 13:44:42)
Офлайн
scidam
Огромное спасибо)
Ещё вопрос назрел, как с помощью numpy превратить сгенерированный массив символов в строку. То есть как там сделать вот такую вещь
''.join(['1', '2', '3'])
Офлайн
Полагаю, что самый быстрый способ объединить все символы в строку это:
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 - видимо то, что нужно
Офлайн
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'
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 >>>
Офлайн
Огромное спасибо за все пояснения и ответы.
Офлайн