Ускорение функции, которая выводит продукты с повторениями в Python - PullRequest
Новая
       8

Ускорение функции, которая выводит продукты с повторениями в Python

0 голосов
/ 23 июня 2018

Я написал функцию, которая возвращает список всех возможных «продуктов» строки с повторениями (для программы проверки орфографии): 

def productRepeats(string):
    comboList = []

    for item in [p for p in product(string, repeat = len(list(string)))]:
        if item not in comboList:
            comboList.append("".join(item))

    return list(set(comboList))

Поэтому, когда вводится print(productRepeats("PIP")),он выводит (мне все равно, в каком порядке): 

['PII', 'IIP', 'PPI', 'IPI', 'IPP', 'PPP', 'PIP', 'III']

Однако, если я пытаюсь получить что-то больше 5 цифр (PIIIIP), вывод занимает около 30 секунд, даже если естьтолько 64 способа

Можно ли как-нибудь ускорить это, так как получение списка для строки 'GERAWUHGP', например, занимает более получаса?

Ответы [ 2 ]

0 голосов
/ 23 июня 2018

Есть несколько приемов, которые вы можете использовать:

  1. Используйте понимание списка или map для выполнения итерации.
  2. Как объясняет @ jwodder , используйте set(string), чтобы избежать проверки на дубликаты на более позднем этапе.

Вот демонстрация. Я вижу улучшение в ~ 900 раз для слова "привет": 

from itertools import product

def productRepeats(string):
    comboList = []

    for item in [p for p in product(string, repeat = len(list(string)))]:
        if item not in comboList:
            comboList.append("".join(item))

    return list(set(comboList))

def productRepeats2(string):
    return list(map(''.join, product(set(string), repeat=len(string))))

assert set(productRepeats2('hello')) == set(productRepeats('hello'))

%timeit productRepeats('hello')   # 127 ms
%timeit productRepeats2('hello')  # 143 µs
0 голосов
/ 23 июня 2018

Устранить дубликаты до вызова product()

product(seq, repeat=len(seq)) выдаст дубликаты результатов, если & только если seq содержит дубликаты элементов; например, product('ABC', repeat=3) не будет иметь дубликатов, но product('ABA', repeat=3) будет иметь некоторые дубликаты, потому что A будет выбран более одного раза (и это будет усугубляться тем фактом, что 'ABA' используется в качестве аргумента три раза) , Сначала отфильтруйте все дубликаты из string, а затем передайте результат в product, и вы сможете полностью отбросить проверку после product дублирования, так что вы можете просто вернуть результат product напрямую: 

def productRepeats(string):
    return product(set(string), repeat=len(string))
...