Оптимизация Python

Question

f = open('wl4.txt', 'w')
hh = 0
######################################
for n in range(1,5):
    for l in range(33,127):
        if n==1:
            b = chr(l) + '\n'
            f.write(b)
            hh += 1 
        elif n==2:           
            for s0 in range(33, 127):
                b = chr(l) + chr(s0) + '\n'
                f.write(b)
                hh += 1
        elif n==3:          
            for s0 in range(33, 127):
                for s1 in range(33, 127):
                    b = chr(l) + chr(s0) + chr(s1) + '\n'
                    f.write(b)
                    hh += 1 
        elif n==4:    
            for s0 in range(33, 127):
                for s1 in range(33, 127):
                    for s2 in range(33,127):
            b = chr(l) + chr(s0) + chr(s1) + chr(s2) + '\n'
            f.write(b)
            hh += 1 
######################################
print "We Made %d Words." %(hh)
######################################
f.close()

Итак, есть ли способ сделать это быстрее?

Answer 1

Возможны дальнейшие существенные улучшения.

Следующий файл скрипта демонстрирует это, используя (для краткости) только цикл размера 4 (который занимает более 90% времени).

метод 0: исходный код ОП

метод 1: решение Джона Куглемана

метод 2: (1) и убрать некоторую конкатенацию строк из внутренних циклов

метод 3: (2) и поместите код в функцию - доступ к локальным переменным НАМНОГО быстрее, чем к глобальным переменным. Любой сценарий может сделать это. Многие сценарии должны это делать.

метод 4: (3) и накапливать строки в списке, затем присоединять их и записывать их. Обратите внимание, что это использует память, как вы можете не верить. Мой код не пытается сделать это для всего файла, потому что (127 - 33) ** 4 - 78M строк. В 32-битном боксе это 78 * 4 = 312 МБ только для списка (игнорируя неиспользуемую память в конце списка), плюс 78 * 28 = 2184 МБ для объектов str (sys.getsizeof ("1234") создает 28) плюс 78 * 5 = 390 Мб за результат объединения. Вы просто взорвали свое адресное пространство пользователя или ваш ulimit или что-то еще, что можно было бы сдуть. Или, если у вас есть 1 ГБ реальной памяти, 128 МБ которой было зарезервировано видеодрайвером, но достаточно места подкачки, у вас есть время на обед (если вы работаете с определенной ОС, то и с ужином).

метод 5: (4) и не спрашивать список о местонахождении его атрибута добавления 78 миллионов раз: -)

Вот файл сценария:

import time, sys
time_function = time.clock # Windows; time.time may be better on *x
ubound, which = map(int, sys.argv[1:3])
t0 = time_function()
if which == 0:
    ### original ###
    f = open('wl4.txt', 'w')
    hh = 0
    n = 4
    for l in range(33, ubound):
        if n == 1:
            pass
        elif n == 2:
            pass
        elif n == 3:
            pass
        elif n == 4:
            for s0 in range(33, ubound):
                for s1 in range(33, ubound):
                    for s2 in range(33,ubound):
                        b = chr(l) + chr(s0) + chr(s1) + chr(s2) + '\n'
                        f.write(b)
                        hh += 1
    f.close()
elif which == 1:
    ### John Kugleman ###
    f = open('wl4.txt', 'w')
    chars = [chr(c) for c in range(33, ubound)]
    hh = 0
    for l in chars:
        for s0 in chars:
            for s1 in chars:
                for s2 in chars:
                    b = l + s0 + s1 + s2 + '\n'
                    f.write(b)
                    hh += 1
    f.close()
elif which == 2:
    ### JohnK, saving + ###
    f = open('wl4.txt', 'w')
    chars = [chr(c) for c in range(33, ubound)]
    hh = 0
    for L in chars: # "L" as in "Legible" ;-)
        for s0 in chars:
            b0 = L + s0
            for s1 in chars:
                b1 = b0 + s1
                for s2 in chars:
                    b = b1 + s2 + '\n'
                    f.write(b)
                    hh += 1
    f.close()
elif which == 3:
    ### JohnK,  saving +, function ###
    def which3func():
        f = open('wl4.txt', 'w')
        chars = [chr(c) for c in range(33, ubound)]
        nwords = 0
        for L in chars:
            for s0 in chars:
                b0 = L + s0
                for s1 in chars:
                    b1 = b0 + s1
                    for s2 in chars:
                        b = b1 + s2 + '\n'
                        f.write(b)
                        nwords += 1
        f.close()
        return nwords
    hh = which3func()
elif which == 4:
    ### JohnK, saving +, function, linesep.join() ###
    def which4func():
        f = open('wl4.txt', 'w')
        chars = [chr(c) for c in range(33, ubound)]
        nwords = 0
        for L in chars:
            accum = []
            for s0 in chars:
                b0 = L + s0
                for s1 in chars:
                    b1 = b0 + s1
                    for s2 in chars:
                        accum.append(b1 + s2)
            nwords += len(accum)
            accum.append("") # so that we get a final newline
            f.write('\n'.join(accum))
        f.close()
        return nwords
    hh = which4func()
elif which == 5:
    ### JohnK, saving +, function, linesep.join(), avoid method lookup in loop ###
    def which5func():
        f = open('wl4.txt', 'w')
        chars = [chr(c) for c in range(33, ubound)]
        nwords = 0
        for L in chars:
            accum = []; accum_append = accum.append
            for s0 in chars:
                b0 = L + s0
                for s1 in chars:
                    b1 = b0 + s1
                    for s2 in chars:
                        accum_append(b1 + s2)
            nwords += len(accum)
            accum_append("") # so that we get a final newline
            f.write('\n'.join(accum))
        f.close()
        return nwords
    hh = which5func()
else:
    print "Bzzzzzzt!!!"
t1 = time_function()
print "Method %d made %d words in %.1f seconds" % (which, hh, t1 - t0)

Вот некоторые результаты:

C:\junk\so>for %w in (0 1 2 3 4 5) do \python26\python wl4.py 127 %w

C:\junk\so>\python26\python wl4.py 127 0
Method 0 made 78074896 words in 352.3 seconds

C:\junk\so>\python26\python wl4.py 127 1
Method 1 made 78074896 words in 183.9 seconds

C:\junk\so>\python26\python wl4.py 127 2
Method 2 made 78074896 words in 157.9 seconds

C:\junk\so>\python26\python wl4.py 127 3
Method 3 made 78074896 words in 126.0 seconds

C:\junk\so>\python26\python wl4.py 127 4
Method 4 made 78074896 words in 68.3 seconds

C:\junk\so>\python26\python wl4.py 127 5
Method 5 made 78074896 words in 60.5 seconds

Обновление в ответ на вопросы ОП

"" "Когда я пытаюсь добавить циклы, у меня возникает ошибка памяти для fas_append .. в чем проблема ??" ""

Я не знаю, в чем проблема; Я не могу прочитать твой код на таком расстоянии. Угадайте: если вы пытаетесь сделать длину == 5, вы, вероятно, получили биты инициализации и записи accum в неправильном месте, а accum пытается вырасти за пределы объема памяти вашей системы (как я и надеялся, объяснил ранее).

"" "Теперь метод 5 самый быстрый, но он заставляет слово сказать длину 4 ... как я могу сделать, сколько я хочу ?? :)" ""

У вас есть два варианта: (1) вы продолжаете использовать вложенные циклы for (2) вы смотрите на ответы, которые не используют вложенные циклы for, с длиной, определяемой динамически.

Методы 4 и 5 получили ускорение при использовании accum, но способ их выполнения был приспособлен к точному знанию того, сколько памяти будет использовано.

Ниже приведены еще 3 метода. 101 - это метод tgray без использования дополнительной памяти. 201 - это метод Пола Ханкина (плюс некоторый код записи в файл), аналогично без использования дополнительной памяти. Эти два метода имеют примерно одинаковую скорость и находятся в поле зрения метода 3 по скорости. Они оба позволяют динамически задавать желаемую длину.

Метод 102 - это метод tgray с фиксированным буфером в 1 МБ - он пытается сэкономить время, уменьшая количество вызовов функции f.write () ... вы можете поэкспериментировать с размером буфера. Вы можете создать ортогональный метод 202, если хотите. Обратите внимание, что метод tgray использует itertools.product, для чего вам потребуется Python 2.6, тогда как метод Пола Ханкина использует выражения-генераторы, которые существовали уже некоторое время.

elif which == 101:
    ### tgray, memory-lite version
    def which101func():
        f = open('wl4.txt', 'w')
        f_write = f.write
        nwords = 0
        chars = map(chr, xrange(33, ubound))  # create a list of characters
        length = 4 #### length is a variable
        for x in product(chars, repeat=length):
            f_write(''.join(x) + '\n')
            nwords += 1
        f.close()
        return nwords
    hh = which101func()
elif which == 102:
    ### tgray, memory-lite version, buffered
    def which102func():
        f = open('wl4.txt', 'w')
        f_write = f.write
        nwords = 0
        chars = map(chr, xrange(33, ubound))  # create a list of characters
        length = 4 #### length is a variable
        buffer_size_bytes = 1024 * 1024
        buffer_size_words = buffer_size_bytes // (length + 1)
        words_in_buffer = 0
        buffer = []; buffer_append = buffer.append
        for x in product(chars, repeat=length):
            words_in_buffer += 1
            buffer_append(''.join(x) + '\n')
            if words_in_buffer >= buffer_size_words:
                f_write(''.join(buffer))
                nwords += words_in_buffer
                words_in_buffer = 0
                del buffer[:]
        if buffer:
            f_write(''.join(buffer))
            nwords += words_in_buffer
        f.close()
        return nwords
    hh = which102func()
elif which == 201:
    ### Paul Hankin (needed output-to-file code added)
    def AllWords(n, CHARS=[chr(i) for i in xrange(33, ubound)]):
        #### n is the required word length
        if n == 1: return CHARS
        return (w + c for w in AllWords(n - 1) for c in CHARS)
    def which201func():
        f = open('wl4.txt', 'w')
        f_write = f.write
        nwords = 0
        for w in AllWords(4):
            f_write(w + '\n')
            nwords += 1
        f.close()
        return nwords
    hh = which201func()

Answer 2

Вы можете создать range(33, 127) один раз и сохранить его. Отсутствие необходимости его многократно сокращает время выполнения на моей машине вдвое.

chars = [chr(c) for c in range(33, 127)]

...

for s0 in chars:
    for s1 in chars:
        for s2 in chars:
            b = l + s0 + s1 + s2 + '\n'
            f.write(b)
            hh += 1

Answer 3

При выполнении операций, которые включают многократное повторение, хорошее место для начала - пакет itertools.

В этом случае, похоже, вам нужна функция product . Что дает вам:

декартово произведение, эквивалентное вложенный цикл for

Итак, чтобы получить список «слов», которые вы создаете:

from itertools import product

chars = map(chr, xrange(33,127))  # create a list of characters
words = []                        # this will be the list of words

for length in xrange(1, 5):       # length is the length of the words created
    words.extend([''.join(x) for x in product(chars, repeat=length)])

# instead of keeping a separate counter, hh, we can use the len function
print "We Made %d Words." % (len(words))  

f = open('wl4.txt', 'w')
f.write('\n'.join(words))         # write one word per line
f.close()

В результате мы получаем результат, который нам дает ваш скрипт. И поскольку itertools реализован в c, он также быстрее.

Edit:

Согласно очень проницательному комментарию Джона Мачина об использовании памяти, здесь приведен обновленный код, который не выдает ошибку памяти при запуске во всем диапазоне (33, 127).

from itertools import product

chars = map(chr, xrange(33,127))  # create a list of characters
f_words = open('wl4.txt', 'w')

num_words = 0                     # a counter (was hh in OPs code)
for length in xrange(1, 5):       # length is the length of the words created
    for char_tup in product(chars, repeat=length):
        f_words.write(''.join(char_tup) + '\n')
        num_words += 1

f.close()
print "We Made %d Words." % (num_words)  

На моем компьютере это займет около 4 минут (240 секунд).

Answer 4

Внешний цикл кажется довольно бессмысленным. Почему бы просто:

for l in range(33,127)
   .. your code for the n==1 case

for l in range(33,127)
   .. your code for the n==2 case

for l in range(33,127)
   .. your code for the n==3 case

for l in range(33,127)
   .. your code for the n==4 case

Это будет и быстрее, и легче для чтения.

Answer 5

Как это работает с произвольными длинами слов: (Генератор паролей?)

f = open('wl4.txt', 'w')
hh=0
chars = map(chr,xrange(33, 127))

def func(n, result):
    if (n == 0):
        f.write(result + "\n")
        hh +=1
    else:
        for c in chars:
            func(n-1, result+c)

for n in range(1, 5):
    func(n,"")
######################################   
print "We Made %d Words." %(hh)   
######################################   
f.close()

Answer 6

Вот короткое рекурсивное решение.

def AllWords(n, CHARS=[chr(i) for i in xrange(33, 127)]):
    if n == 1: return CHARS
    return (w + c for w in AllWords(n - 1) for c in CHARS)

for i in xrange(1, 5):
    for w in AllWords(i):
        print w

PS: это ошибка, что символ 127 исключен?

Answer 7

Нужны ли вам все слова, отсортированные по длине? Если вы можете смешать длины вместе, вы можете немного улучшить ответ Джона Кугельмана следующим образом:

f = open("wl4.txt", "w")

chars = [chr(c) for c in range(33, 127)]
c = len(chars)
count = c + c*c + c**3 + c**4

for c0 in chars:
    print >>f, c0
    for c1 in chars:
        s1 = c0 + c1
        print >>f, s1
        for c2 in chars:
            s2 = s1 + c2
            print >>f, s2
            for c3 in chars:
                print >>f, s2 + c3

print "We Made %d Words." % count

Прямой расчет чч вместо всех приращений также является большим выигрышем (около 15% на этом ноутбуке). Есть также улучшение от использования печати поверх f.write, хотя я не знаю, почему это так. Эта версия работает для меня примерно за 39 секунд.