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

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

7
  • 1
    Есть исходный текст задания?
    – Alpensin
    29 июл 2021 в 17:01
  • Это я для себя делаю.
    – halwa
    29 июл 2021 в 17:02
  • А что хотели то для себя? 29 июл 2021 в 17:04
  • 1
    Вы все 20 миллиардов комбинаций собрались в список запихать? Вы уверены, что у вас есть несколько сотен гигабайт памяти?
    – GrAnd
    29 июл 2021 в 17:25
  • 1
    А вообще, похоже вы пытались реализовать вот это: import itertools ; for a in itertools.product(string.ascii_letters, repeat=6): print(''.join(a[::-1])). Если обратный порядок не важен, то можно выкинуть [::-1].
    – GrAnd
    29 июл 2021 в 17:26

2 ответа 2

3

Можно применить 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

2
  • можно ли чтобы без создания списка, а сразу перебирать в реальном времени?
    – halwa
    29 июл 2021 в 17:49
  • Так оно так и сделано здесь. Переменной a присваивается функция-генератор , потом через next(a) она каждый раз выдает следующее значение. Вы можете это увидеть на последних трех строчках моего кода. Почитайте wiki.python.org/moin/Generators или realpython.com/introduction-to-python-generators Цикл выдает 10 раз следующее значение. 29 июл 2021 в 17:53
1

Несколько раз реализовывал этот алгоритм, но не на питоне а на 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
10
  • Разница с моим вариантом примерно в два раза по времени, но реализация хорошая, когда ничего кроме нет. 29 июл 2021 в 20:00
  • @AndyPavlov спасибо за результаты тестирования, ну а так да это как раз тот случай когда нет возможности реализовать иначе. 29 июл 2021 в 20:09
  • Кстати замерил для трех элементов оба варианта без вывода, по времени практически тоже самое плюс, минус, немного странно. 29 июл 2021 в 21:34
  • @AndyPavlov хотел проверить на 4 элемента, Ваш код сломался в чем может быть дело? Я просто подставил 7311616 в цикл, нужны ли еще какие-то настройки? 29 июл 2021 в 21:42
  • Я обернул Ваш код в виде функции-итератора и прогнал по своей тест системе, а также на обычном timeit. Можете кинуть свой код куда-то? Я варианты от 1 до 6 символов прогонял для оценки времени, все работало 29 июл 2021 в 21:48

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.