Python-сообщество

Alex2ndr · Янв. 21, 2010 21:26:23

Всем доброго времени суток!

Написал вот такую функцию:

def ipgen(oct1,oct2,oct3,oct4):
    for o1 in xrange(oct1[0],oct1[1]+1):
        for o2 in xrange(oct2[0],oct2[1]+1):
            for o3 in xrange(oct3[0],oct3[1]+1):
                for o4 in xrange(oct4[0],oct4[1]+1):
                    yield '%s.%s.%s.%s' % (o1,o2,o3,o4)

for i in ipgen((192,192),(168,168),(0,1),(0,5)):
    print i

Думаю всем кто знаком с сетями сразу станет ясно для чего она нужна. Посмотрел на этот код и решил что он на китайский код похож(это хорошо что в ip всего 4 октета, а если бы я что-нить такое же, но с 40 счетчиками описывал). Решил сделать поизящнее (заметьте - не проще и понятнее - изящнее) - интереса ради. Т к мыслить рекурсиями я умею плохо то мучился долго - через час пришел вот к такому:

def ipgen2(oc,a=0,o=[0,0,0,0]):
    if a == 4:
            print '.'.join( str(i) for i in o)
    else:
        for octt in xrange(oc[a][0],oc[a][1]+1):
            o[a] = octt
            ipgen2(oc,a+1,o)

ipgen2([(192,192),(168,168),(0,1),(0,5)])

следующим шагом решил сделать из него генератор - сеть с 16 (а тем более с 8-й) маской держать в списке как-то не комильфо. Но тут меня поджидала проблема - простая замена print на yield не прошла (естественно с обходом ipgen2 в цикле) - не делается ни одной итерации. Кто мне может сказать почему так получается и где я ошибаюсь (наверняка чего-то очевидное - но создав рекурсивный алгоритм я наверно перенапрягся и теперь этого очевидного не вижу). Итоговый код такой -

def ipgen2(oc,a=0,o=[0,0,0,0]):
    if a == 4:
            yield '.'.join( str(i) for i in o)
    else:
        for octt in xrange(oc[a][0],oc[a][1]+1):
            o[a] = octt
            ipgen2(oc,a+1,o)

for i in ipgen2([(192,192),(168,168),(0,1),(0,5)]):
    print i

Спасибо за внимание.

PS Кто нить может посоветовать хорошие материалы по рекурсии - не обязательно для питона, а просто с алгоритмической точки зрения. Есть 3 тома Кнута - но рекурсия только в 4-м - а он как я понял еще не издан (по крайней мере на русском).

Ed · Янв. 21, 2010 23:02:02

Вот так нужно:

def ipgen2(oc,a=0,o=[0,0,0,0]):
    if a == 4:
            yield '.'.join( str(i) for i in o)
    else:
        for octt in xrange(oc[a][0],oc[a][1]+1):
            o[a] = octt
            for i in ipgen2(oc,a+1,o):
                yield i

Но вообще-то вы изобретаете велосипед. Читайте здесь: http://en.wikipedia.org/wiki/Cartesian_product
И смотрите itertools.product.
Вот немного подредактированая версия оттуда:

def product(*iterables):
    result = [[]]
    for pool in iterables:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield '.'.join(map(str, prod))
for i in product((192,), (168,), (0,1), (0,1,2,3,4,5)):
    print i

В отличие от вашей сгенерит ip адрес состоящий хоть из ста октетов :)
И не требует выкрутасов типа (192,192).

Alex2ndr · Янв. 23, 2010 10:05:59

Спасибо большое. В своем изучении питона до itertools я еще не добрался - обязательно посмотрю и потестирую.

Alex2ndr · Янв. 24, 2010 14:25:06

Решил интереса ради погонять все 3 варианта. Написал такой вот скрипт -

#!/usr/bin/env python
# -*-coding: utf-8 -*-
# vim: sw=4 ts=4 expandtab ai

import time

def ipgen(oct1,oct2,oct3,oct4):
    for o1 in xrange(oct1[0],oct1[1]+1):
        for o2 in xrange(oct2[0],oct2[1]+1):
            for o3 in xrange(oct3[0],oct3[1]+1):
                for o4 in xrange(oct4[0],oct4[1]+1):
                    yield '%s.%s.%s.%s' % (o1,o2,o3,o4)

def ipgen2(oc,a=0,o=[0,0,0,0]):
    if a == 4:
        yield '.'.join( str(i) for i in o)
    else:
        for octt in xrange(oc[a][0],oc[a][1]+1):
            o[a] = octt
            for i in ipgen2(oc,a+1,o):
                yield i

def product(*iterables):
    result = [[]]
    for pool in iterables:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield '.'.join(map(str, prod))

starttime = time.time()
for i in ipgen((192,192),(160,168),(0,255),(0,255)):
    pass
print 'ipgen time = ',(time.time()-starttime)

starttime = time.time()
for i in ipgen2([(192,192),(160,168),(0,255),(0,255)]):
    pass
print 'ipgen2 time = ',(time.time()-starttime)

starttime = time.time()
for i in product((192,), xrange(160,169), xrange(0,256), xrange(0,256)):
    pass
print 'product time = ',(time.time()-starttime)

Решил погонять на сети с 13 маской (примерно). Вот такие результаты -

master alex@deb-home:~/development/asfs/python$ python -m cProfile ./pinger.py
ipgen time =  3.74306893349
ipgen2 time =  28.3054819107
product time =  10.6935710907
         9439511 function calls (6488077 primitive calls) in 42.745 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000   42.745   42.745 <string>:1(<module>)
3541259/589825   12.850    0.000   27.209    0.000 pinger.py:14(ipgen2)
  2949120    6.680    0.000    6.680    0.000 pinger.py:16(<genexpr>)
   589825    4.806    0.000    9.214    0.000 pinger.py:23(product)
        1    3.950    3.950   42.743   42.743 pinger.py:5(<module>)
   589825    2.369    0.000    2.369    0.000 pinger.py:7(ipgen)
        1    0.002    0.002   42.745   42.745 {execfile}
   589824    3.066    0.000    3.066    0.000 {map}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
  1179648    9.021    0.000   15.701    0.000 {method 'join' of 'str' objects}
        6    0.000    0.000    0.000    0.000 {time.time}

на сети с 8-й маской в принципе похожий результат

master alex@deb-home:~/development/asfs/python$ python -m cProfile ./pinger.py
ipgen time =  64.787596941
ipgen2 time =  613.484504223
product time =  306.106604099
         177252791 function calls (121831437 primitive calls) in 984.381 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000  984.381  984.381 <string>:1(<module>)
66496939/11075585  281.981    0.000  589.888    0.000 pinger.py:14(ipgen2)
 55377920  140.105    0.000  140.105    0.000 pinger.py:16(<genexpr>)
 11075585  202.787    0.000  280.651    0.000 pinger.py:23(product)
        1   72.437   72.437  984.379  984.379 pinger.py:5(<module>)
 11075585   41.402    0.000   41.402    0.000 pinger.py:7(ipgen)
        1    0.002    0.002  984.381  984.381 {execfile}
 11075584   53.411    0.000   53.411    0.000 {map}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
 22151168  192.255    0.000  332.361    0.000 {method 'join' of 'str' objects}
        6    0.000    0.000    0.000    0.000 {time.time}

Решил поставить функции в одинаковые условия - заменил выражения генераторы на форматирование строки - вот так -

...

def ipgen2(oc,a=0,o=[0,0,0,0]):
    if a == 4:
        yield '%s.%s.%s.%s' % (o[0],o[1],o[2],o[3])
    else:
        for octt in xrange(oc[a][0],oc[a][1]+1):
            o[a] = octt
            for i in ipgen2(oc,a+1,o):
                yield i

def product(*iterables):
    result = [[]]
    for pool in iterables:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield '%s.%s.%s.%s' % (prod[0],prod[1],prod[2],prod[3])
...

Результат стал интереснее (на 13 маске):

master alex@deb-home:~/development/asfs/python$ python -m cProfile ./pinger.py
ipgen time =  3.17732310295
ipgen2 time =  14.0130200386
product time =  4.38480210304
         4720919 function calls (1769485 primitive calls) in 21.578 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000   21.578   21.578 <string>:1(<module>)
3541259/589825   12.926    0.000   12.926    0.000 pinger.py:14(ipgen2)
   589825    3.146    0.000    3.146    0.000 pinger.py:24(product)
        1    3.451    3.451   21.576   21.576 pinger.py:5(<module>)
   589825    2.053    0.000    2.053    0.000 pinger.py:7(ipgen)
        1    0.003    0.003   21.578   21.578 {execfile}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        6    0.000    0.000    0.000    0.000 {time.time}

Таким образом приходим к мысли что китайский код быстрее всех остальных (особенно рекурсии) :)
Имхо он же и самый читабельный (лично для меня). Серьезно задумался не оставить ли его в своем проекте…

Отредактировано (Янв. 24, 2010 14:27:02)

Андрей Светлов · Янв. 24, 2010 16:27:23

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

Отредактировано (Янв. 24, 2010 21:10:14)

Python-сообщество

Уведомления

#1 Янв. 21, 2010 21:26:23

Проблема с превращение рекурсивной функции в генератор

#2 Янв. 21, 2010 23:02:02

Проблема с превращение рекурсивной функции в генератор

#3 Янв. 23, 2010 10:05:59

Проблема с превращение рекурсивной функции в генератор

#4 Янв. 24, 2010 14:25:06

Проблема с превращение рекурсивной функции в генератор

#5 Янв. 24, 2010 16:27:23

Проблема с превращение рекурсивной функции в генератор

Board footer