Как ускорить код на python - перечисление всех вариантов?

Question

import string
out=[]
s=string.ascii_letters
x=0
y=0
z=0
t=0
r=0
f=0
for i in range(len(s)**6):
    out.append(s[x]+s[y]+s[z]+s[t]+s[r]+s[f])
    if x+1==len(s):
        x=-1
        y+=1
    if y==len(s):
        z+=1
    if z==len(s):
        t+=1
    if t==len(s):
        r+=1

    f=f+1 if r==len(s) else f
    r=0 if r==len(s) else r
    t=0 if t==len(s) else t
    z=0 if z==len(s) else z
    y=0 if y==len(s) else y
    x+=1
    
print(len(out))

Как можно его ускорить?

Answer 1

Можно применить itertools и метод itertools.product(). Будете на выходе получать через итератор комбинации. Тогда не придется держать список в памяти.

В примере ниже имеем генератор, который через product() в нужном количестве символов строит все варианты сочетаний, потом через lenght_max_for_fill проверяем нужно ли нам добирать количество символов до максимальной длины, и, если да, то через переменную fill делаем донаполнение строки.

import string
import itertools

s = string.ascii_letters


# вариант с итерацией символов до строки нужной длины
def brute(s, count):
    for s in itertools.product(s, repeat=count):
        yield ''.join(s)

a = brute(s, 6)
for _ in range(10):
    print(next(a))

# вариант с добавлением символов из переменной `fill` до нужной длины строки.
def brute(s, count, lenght_max_for_fill = 6, fill = 'a'):
    for s in itertools.product(s, repeat=count):
        yield '{}{}'.format(''.join(s), (lenght_max_for_fill - count) * fill if count < lenght_max_for_fill else '')

a = brute(s, 6, 6, 'a')
for _ in range(10):
    print(next(a))

Делать же список длиной в 20 миллиардов элементов память не потянет и времени много уйдет. Даже без дополнительных операций. А Вы еще дополнительно в каждом цикле 9 раз берете длину строки s

Answer 2

Несколько раз реализовывал этот алгоритм, но не на питоне а на VB где не было никаких итераторов, генераторов.

Понимаю, что ответ уже дан, но возможно кому-то понравится и этот подход, по сути создается система счисления и инкрементация переключает разряды, как по мне - логично и удобно для понимания алгоритма перебора, и условие только одно - на выход из цикла. Можно конечно еще внутренний цикл сделать для краткости, но в данном случае счел лишним, так будет проще для понимания.

Но на скорость не тестировал, скорее всего будет уступать встроенным функциям так как думаю они под это оптимизированы на низком уровне.

import string
import time
out=[]
s=string.ascii_letters

def brute_1(count = 10000): 
  n = [0,0,0,0,0,0]
  last = len(n)-1
  m = len(s)
  for i in range(count):
    k = m
    n[5]=i % k  
    n[4]=(i // k) % m
    k *= m
    n[3]=(i // k) % m
    k *= m
    n[2]=(i // k) % m
    k *= m
    n[1]=(i // k) % m
    k *= m
    n[0]=(i // k) % m
    yield(''.join([s[n[0]], s[n[1]],s[n[2]],s[n[3]],s[n[4]],s[n[5]]]))    

# оптимизация на ~42%
def brute_2(count = 10000): 
  m = len(s)
  ka = m
  kb = ka * m
  kc = kb * m
  kd = kc * m
  ke = kd * m
  kf = ke * m
  out = 0
  for i in range(count):
    a=i % m
    b=(i // kb) % m
    c=(i // kc) % m
    d=(i // kd) % m
    e=(i // ke) % m
    f=(i // kf) % m
    yield(f'{s[f]}{s[e]}{s[d]}{s[c]}{s[b]}{s[a]}')  

start = time.time()
a = brute_1(7311616)
for _ in range(7311616):
  next(a) 
print((time.time() - start)*1000.0)  # 14443.275

start = time.time()
a = brute_2(7311616)
for _ in range(7311616):
  next(a) 
print((time.time() - start)*1000.0)  # 8506.388

БЛОГ НА HUSL

Как ускорить код на python - перечисление всех вариантов?

Ответы (2 шт):