Уведомления

Группа в Telegram: @pythonsu

#1 Окт. 6, 2016 23:43:46

jon34
Зарегистрирован: 2016-02-14
Сообщения: 47
Репутация: +  0  -
Профиль   Отправить e-mail  

Оптимизация генерации рандомной строки

При генерации строки длинной 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)

Офлайн

#2 Окт. 7, 2016 03:46:51

scidam
Зарегистрирован: 2016-06-15
Сообщения: 288
Репутация: +  35  -
Профиль   Отправить e-mail  

Оптимизация генерации рандомной строки

Для вашей задачи можно попробовать пакет 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

Отредактировано scidam (Окт. 7, 2016 03:54:15)

Офлайн

#3 Окт. 7, 2016 10:40:54

jon34
Зарегистрирован: 2016-02-14
Сообщения: 47
Репутация: +  0  -
Профиль   Отправить e-mail  

Оптимизация генерации рандомной строки

scidam
Да, numpy отличная вещь, но как мне на нем реализовать именно ту функциональность, что была до этого? На сколько я понял сейчас происходит генерация просто рандомной строки, а мне надо строку в которой символы встречаются с заданной вероятнотью.

Офлайн

#4 Окт. 7, 2016 13:36:04

scidam
Зарегистрирован: 2016-06-15
Сообщения: 288
Репутация: +  35  -
Профиль   Отправить e-mail  

Оптимизация генерации рандомной строки

Приведенный пример как раз для случая генерации символов с заданной вероятностью, только вероятности там выбирались случайно. 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)

Офлайн

#5 Окт. 7, 2016 14:33:53

jon34
Зарегистрирован: 2016-02-14
Сообщения: 47
Репутация: +  0  -
Профиль   Отправить e-mail  

Оптимизация генерации рандомной строки

scidam
Огромное спасибо)

Ещё вопрос назрел, как с помощью numpy превратить сгенерированный массив символов в строку. То есть как там сделать вот такую вещь

''.join(['1', '2', '3'])

Офлайн

#6 Окт. 7, 2016 14:42:54

scidam
Зарегистрирован: 2016-06-15
Сообщения: 288
Репутация: +  35  -
Профиль   Отправить e-mail  

Оптимизация генерации рандомной строки

Полагаю, что самый быстрый способ объединить все символы в строку это:
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 - видимо то, что нужно

Офлайн

#7 Окт. 7, 2016 15:57:49

jon34
Зарегистрирован: 2016-02-14
Сообщения: 47
Репутация: +  0  -
Профиль   Отправить e-mail  

Оптимизация генерации рандомной строки

scidam
Что-то этот код генерит даже не похожее на то, что надо.

Офлайн

#8 Окт. 8, 2016 03:32:06

scidam
Зарегистрирован: 2016-06-15
Сообщения: 288
Репутация: +  35  -
Профиль   Отправить e-mail  

Оптимизация генерации рандомной строки

Последний код это просто пример объединения символов в строку:

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



Офлайн

#9 Окт. 12, 2016 03:38:22

jon34
Зарегистрирован: 2016-02-14
Сообщения: 47
Репутация: +  0  -
Профиль   Отправить e-mail  

Оптимизация генерации рандомной строки

Огромное спасибо за все пояснения и ответы.

Офлайн

Board footer

Модераторировать

Powered by DjangoBB

Lo-Fi Version