Курс лекций по Python. Курс лекций по Python (ru). 1. Лекция Введение в программирование на языке Python
 Скачать 0.77 Mb.
|
|
14. Лекция: Устройство интерпретатора языка Python. В этой лекции сделана попытка пролить свет на внутреннее устройство интерпретатора Python. Для иллюстрации работы интерпретатора рассматриваются отладчик, профайлер и «дизассемблер». Лексический анализ Лексический анализатор языка программирования разбивает исходный текст программы (состоящий из одиночных символов) на лексемы — неделимые «слова» языка. Основные категории лексем Python: идентификаторы и ключевые слова (NAME), литералы (STRING, NUMBER и т.п.), операции (OP), разделители, специальные лексемы для обозначения (изменения) отступов (INDENT, DEDENT) и концов строк (NEWLINE), а также комментарии (COMMENT). Лексический анализатор доступен через модуль tokenize, а определения кодов лексем содержатся в модуле token стандартной библиотеки Python. Следующий пример показывает лексический анализатор в действии: Листинг import StringIO, token, tokenize prog_example = """ for i in range(100): # comment if i % 1 == 0: \ print ":", t**2 «"".strip() rl = StringIO.StringIO(prog_example).readline for t_type, t_str, (br,bc), (er,ec), logl in tokenize.generate_tokens(rl): print "%3i %10s : %20r» % (t_type, token.tok_name[t_type], t_str) А вот что выведет эта программа, разбив на лексемы исходный код примера: Листинг Фактически получен поток лексем, который может использоваться для различных целей. Например, для синтаксического «окрашивания» кода на языке Python. Словарь token.tok_name позволяет получить мнемонические имена для типа лексемы по номеру. Синтаксический анализ Вторая стадия преобразования исходного текста программы в байт–код интерпретатора состоит в синтаксическом анализе исходного текста. Модуль parser содержит функции suite() и expr() для построения деревьев синтаксического разбора соответственно для кода программ и выражений Python. Модуль symbol содержит номера символов грамматики Python, словарь для получения названия символа из грамматики Python. Следующая программа анализирует достаточно простой код Python (prg) и порождает дерево синтаксического разбора (AST–объект), который тут же можно превращать в кортеж и красиво выводить функцией pprint.pprint(). Далее определяется функция для превращения номеров символов в их мнемонические обозначения (имена) в грамматике: Листинг import pprint, token, parser, symbol prg = ""«print 2*2»"" pprint.pprint(parser.suite(prg).totuple()) def pprint_ast(ast, level=0): if type(ast) == type(()): for a in ast: pprint_ast(a, level+1) elif type(ast) == type(""): print repr(ast) else: print " "*level, try: print symbol.sym_name[ast] except: print «token.»+token.tok_name[ast], print pprint_ast(parser.suite(prg).totuple()) Эта программа выведет следующее (структура дерева отражена отступами): Листинг (257, (264, (265, (266, (269, (1, 'print'), (292, (293, (294, (295, (297, (298, (299, (300, (301, (302, (303, (304, (305, (2, '2')))), (16, '*'), (303, (304, (305, (2, '2')))))))))))))))), (4, ''))), (0, '')) file_input stmt simple_stmt small_stmt print_stmt token.NAME 'print' test and_test not_test comparison expr xor_expr and_expr shift_expr arith_expr term factor power atom token.NUMBER '2' token.STAR '*' factor power atom token.NUMBER '2' token.NEWLINE '' token.ENDMARKER '' Получение байт–кода После того как получено дерево синтаксического разбора, компилятор должен превратить его в байт–код, подходящий для исполнения интерпретатором. В следующей программе проводятся отдельно синтаксический анализ, компиляция и выполнение (вычисление) кода (и выражения) в языке Python: Листинг import parser prg = ""«print 2*2»"" ast = parser.suite(prg) code = ast.compile('filename.py') exec code prg = ""«2*2»"" ast = parser.expr(prg) code = ast.compile('filename1.py') print eval(code) Функция parser.suite() (или parser.expr()) возвращает AST–объект (дерево синтаксического анализа), которое методом compile() компилируется в Python байт–код и сохраняется в кодовом объекте code. Теперь этот код можно выполнить (или, в случае выражения — вычислить) с помощью оператора exec (или функции eval()). Здесь необходимо заметить, что недавно в Python появился пакет compiler, который объединяет модули для работы анализа исходного кода на Python и генерации кода. В данной лекции он не рассматривается, но те, кто хочет глубже изучить эти процессы, может обратиться к документации по Python. Изучение байт–кода Для изучения байт–кода Python–программы можно использовать модуль dis (сокращение от «дизассемблер»), который содержит функции, позволяющие увидеть байт–код в мнемоническом виде. Следующий пример иллюстрирует эту возможность: Листинг >>> def f(): … print 2*2 … >>> dis.dis(f) 2 0 LOAD_CONST 1 (2) 3 LOAD_CONST 1 (2) 6 BINARY_MULTIPLY 7 PRINT_ITEM 8 PRINT_NEWLINE 9 LOAD_CONST 0 (None) 12 RETURN_VALUE Определяется функция f(), которая должна вычислить и напечатать значение выражения 2*2. Функция dis() модуля dis выводит код функции f() в виде некого «ассемблера», в котором байт–код Python представлен мнемоническими именами. Следует заметить, что при интерпретации используется стек, поэтому LOAD_CONST кладет значение на вершину стека, а BINARY_MULTIPLY берет со стека два значения и помещает на стек результат их перемножения. Функция без оператора return возвращает значение None. Как и в случае с кодами для микропроцессора, некоторые байт–коды принимают параметры. Мнемонические имена можно увидеть в списке dis.opname (ниже печатаются только задействованные имена): Листинг >>> import dis >>> [n for n in dis.opname if n[0] != "<"] ['STOP_CODE', 'POP_TOP', 'ROT_TWO', 'ROT_THREE', 'DUP_TOP', 'ROT_FOUR', 'NOP', 'UNARY_POSITIVE', 'UNARY_NEGATIVE', 'UNARY_NOT', 'UNARY_CONVERT', 'UNARY_INVERT', 'LIST_APPEND', 'BINARY_POWER', 'BINARY_MULTIPLY', 'BINARY_DIVIDE', 'BINARY_MODULO', 'BINARY_ADD', 'BINARY_SUBTRACT', 'BINARY_SUBSCR', 'BINARY_FLOOR_DIVIDE', 'BINARY_TRUE_DIVIDE', 'INPLACE_FLOOR_DIVIDE', 'INPLACE_TRUE_DIVIDE', 'SLICE+0', 'SLICE+1', 'SLICE+2', 'SLICE+3', 'STORE_SLICE+0', 'STORE_SLICE+1', 'STORE_SLICE+2', 'STORE_SLICE+3', 'DELETE_SLICE+0', 'DELETE_SLICE+1', 'DELETE_SLICE+2', 'DELETE_SLICE+3', 'INPLACE_ADD', 'INPLACE_SUBTRACT', 'INPLACE_MULTIPLY', 'INPLACE_DIVIDE', 'INPLACE_MODULO', 'STORE_SUBSCR', 'DELETE_SUBSCR', 'BINARY_LSHIFT', 'BINARY_RSHIFT', 'BINARY_AND', 'BINARY_XOR', 'BINARY_OR', 'INPLACE_POWER', 'GET_ITER', 'PRINT_EXPR', 'PRINT_ITEM', 'PRINT_NEWLINE', 'PRINT_ITEM_TO', 'PRINT_NEWLINE_TO', 'INPLACE_LSHIFT', 'INPLACE_RSHIFT', 'INPLACE_AND', 'INPLACE_XOR', 'INPLACE_OR', 'BREAK_LOOP', 'LOAD_LOCALS', 'RETURN_VALUE', 'IMPORT_STAR', 'EXEC_STMT', 'YIELD_VALUE', 'POP_BLOCK', 'END_FINALLY', 'BUILD_CLASS', 'STORE_NAME', 'DELETE_NAME', 'UNPACK_SEQUENCE', 'FOR_ITER', 'STORE_ATTR', 'DELETE_ATTR', 'STORE_GLOBAL', 'DELETE_GLOBAL', 'DUP_TOPX', 'LOAD_CONST', 'LOAD_NAME', 'BUILD_TUPLE', 'BUILD_LIST', 'BUILD_MAP', 'LOAD_ATTR', 'COMPARE_OP', 'IMPORT_NAME', 'IMPORT_FROM', 'JUMP_FORWARD', 'JUMP_IF_FALSE', 'JUMP_IF_TRUE', 'JUMP_ABSOLUTE', 'LOAD_GLOBAL', 'CONTINUE_LOOP', 'SETUP_LOOP', 'SETUP_EXCEPT', 'SETUP_FINALLY', 'LOAD_FAST', 'STORE_FAST', 'DELETE_FAST', 'RAISE_VARARGS', 'CALL_FUNCTION', 'MAKE_FUNCTION', 'BUILD_SLICE', 'MAKE_CLOSURE', 'LOAD_CLOSURE', 'LOAD_DEREF', 'STORE_DEREF', 'CALL_FUNCTION_VAR', 'CALL_FUNCTION_KW', 'CALL_FUNCTION_VAR_KW', 'EXTENDED_ARG'] Легко догадаться, что LOAD означает загрузку значения в стек, STORE — выгрузку, PRINT — печать, BINARY — бинарную операцию и т.п. Отладка В интерпретаторе языка Python заложены возможности отладки программ, а в стандартной поставке имеется простейший отладчик — pdb. Следующий пример показывает программу, которая подвергается отладке, и типичную сессию отладки: Листинг # File myfun.py def fun(s): lst = [] for i in s: lst.append(ord(i)) return lst Так может выглядеть типичный процесс отладки: Листинг >>> import pdb, myfun >>> pdb.runcall(myfun.fun, «ABCDE») > /examples/myfun.py(4)fun() — > lst = [] (Pdb) n > /examples/myfun.py(5)fun() — > for i in s: (Pdb) n > /examples/myfun.py(6)fun() — > lst.append(ord(i)) (Pdb) l 1 #!/usr/bin/python 2 # File myfun.py 3 def fun(s): 4 lst = [] 5 for i in s: 6 -> lst.append(ord(i)) 7 return lst [EOF] (Pdb) p lst [] (Pdb) p vars() {'i': 'A', 's': 'ABCDE', 'lst': []} (Pdb) n > /examples/myfun.py(5)fun() — > for i in s: (Pdb) p vars() {'i': 'A', 's': 'ABCDE', 'lst': [65]} (Pdb) n > /examples/myfun.py(6)fun() — > lst.append(ord(i)) (Pdb) n > /examples/myfun.py(5)fun() — > for i in s: (Pdb) p vars() {'i': 'B', 's': 'ABCDE', 'lst': [65, 66]} (Pdb) r — Return - > /examples/myfun.py(7)fun() — >[65, 66, 67, 68, 69] — > return lst (Pdb) n [65, 66, 67, 68, 69] >>> Интерактивный отладчик вызывается функцией pdb.runcall() и на его приглашение (Pdb) следует вводить команды. В данном примере сессии отладки были использованы некоторые из следующих команд: l (печать фрагмент трассируемого кода), n (выполнить все до следующей строки), s (сделать следующий шаг, возможно, углубившись в вызов метода или функции), p (печать значения), r (выполнить все до возврата из текущей функции). Разумеется, некоторые интерактивные оболочки разработчика для Python предоставляют функции отладчика. Кроме того, отладку достаточно легко организовать, поставив в ключевых местах программы, операторы print для вывода интересующих параметров. Обычно этого достаточно, чтобы локализовать проблему. В CGI–сценариях можно использовать модуль cgitb, о котором говорилось в одной из предыдущих лекций. Профайлер Для определения мест в программе, на выполнение которых уходит значительная часть времени, обычно применяется профайлер. Модуль profile Этот модуль позволяет проанализировать работу функции и выдать статистику использования процессорного времени на выполнение той или иной части алгоритма. В качестве примера можно рассмотреть профилирование функции для поиска строк из списка, наиболее похожих на данную. Для того чтобы качественно профилировать функцию difflib.get_close_matches(), нужен большой объем данных. В файле russian.txt собрано 160 тысяч слов русского языка. Следующая программа поможет профилировать функцию difflib.get_close_matches(): Листинг import difflib, profile def print_close_matches(word): print "\n».join(difflib.get_close_matches(word + "\n», open(«russian.txt»))) profile.run(r'print_close_matches(«профайлер»)') При запуске этой программы будет выдано примерно следующее: Листинг провайдер трайлер бройлер 899769 function calls (877642 primitive calls) in 23.620 CPU seconds Ordered by: standard name ncalls tottime percall cumtime percall filename:lineno(function) 1 0.000 0.000 23.610 23.610 1 0.000 0.000 23.610 23.610 T.py:6(print_close_matches) 1 0.000 0.000 0.000 0.000 difflib.py:147(__init__) 1 0.000 0.000 0.000 0.000 difflib.py:210(set_seqs) 159443 1.420 0.000 1.420 0.000 difflib.py:222(set_seq1) 2 0.000 0.000 0.000 0.000 difflib.py:248(set_seq2) 2 0.000 0.000 0.000 0.000 difflib.py:293(__chain_b) 324261 2.240 0.000 2.240 0.000 difflib.py:32(_calculate_ratio) 28317 1.590 0.000 1.590 0.000 difflib.py:344(find_longest_match) 6474 0.100 0.000 2.690 0.000 difflib.py:454(get_matching_blocks) 28317/6190 1.000 0.000 2.590 0.000 difflib.py:480(__helper) 6474 0.450 0.000 3.480 0.001 difflib.py:595(ratio) 28686 0.240 0.000 0.240 0.000 difflib.py:617( 158345 8.690 0.000 9.760 0.000 difflib.py:621(quick_ratio) 159442 2.950 0.000 4.020 0.000 difflib.py:650(real_quick_ratio) 1 4.930 4.930 23.610 23.610 difflib.py:662(get_close_matches) 1 0.010 0.010 23.620 23.620 profile:0(print_close_matches(«профайлер»)) 0 0.000 0.000 profile:0(profiler) Здесь колонки таблицы показывают следующие значения: ncalls — количество вызовов (функции), tottime — время выполнения кода функции (не включая времени выполнения вызываемых из нее функций), percall — то же время, в пересчете на один вызов, cumtime — суммарное время выполнения функции (и всех вызываемых из нее функций), filename — имя файла, lineno — номер строки в файле, function — имя функции (если эти параметры известны). Из приведенной статистики следует, что наибольшие усилия по оптимизации кода необходимо приложить в функциях quick_ratio() (на нее потрачено 8,69 секунд), get_close_matches() (4,93 секунд), затем можно заняться real_quick_ratio() (2,95 секунд) и _calculate_ratio() (секунд). Это лишь самый простой вариант использования профайлера: модуль profile (и связанный с ним pstats) позволяет получать и обрабатывать статистику: их применение описано в документации. Модуль timeit Предположим, что проводится оптимизация небольшого участка кода. Необходимо определить, какой из вариантов кода является наиболее быстрым. Это можно сделать с помощью модуля timeit. В следующей программе используется метод timeit() для измерения времени, необходимого для вычисления небольшого фрагмента кода. Измерения проводятся для трех вариантов кода, делающих одно и то же: конкатенирующих десять тысяч строк в одну строку. В первом случае используется наиболее естественный, «лобовой» прием инкрементной конкатенации, во втором — накопление строк в списке с последующим объединением в одну строку, в третьем применяется списковое включение, а затем объединение элементов списка в одну строку: Листинг from timeit import Timer t = Timer(""" res = "" for k in range(1000000,1010000): res += str(k) «"") print t.timeit(200) t = Timer(""" res = [] for k in range(1000000,1010000): res.append(str(k)) res = ",".join(res) «"") print t.timeit(200) t = Timer(""" res = ",".join([str(k) for k in range(1000000,1010000)]) «"") print t.timeit(200) Разные версии Python дадут различные результаты прогонов: Листинг # Python 2.3 77.6665899754 10.1372740269 9.07727599144 # Python 2.4 9.26631307602 9.8416929245 7.36629199982 В старых версиях Python рекомендуемым способом конкатенации большого количества строк являлось накопление их в списке с последующим применением функции join() (кстати, инкрементная конкатенация почти в восемь раз медленнее этого приема). Начиная с версии 2.4, инкрементная конкатенация была оптимизирована и теперь имеет даже лучший результат, чем версия со списками (которая вдобавок требует больше памяти). Но чемпионом все–таки является работа со списковым включением, поэтому свертывание циклов в списковое включение позволяет повысить эффективность кода. Если требуются более точные результаты, рекомендуется использовать метод repeat(n, k) - он позволяет вызывать timeit(k) n раз, возвращая список из n значений. Необходимо отметить, что на результаты может влиять загруженность компьютера, на котором проводятся испытания. Оптимизация Основная реализация языка Python пока что не имеет оптимизирующего компилятора, поэтому разговор об оптимизации касается только оптимизации кода самим программистом. В любом языке программирования имеются свои характерные приемы оптимизации кода. Оптимизация (улучшение) кода может происходить в двух (зачастую конкурирующих) направлениях: скорость и занимаемая память. В условиях достатка оперативной памяти приложения обычно оптимизируют по скорости. При оптимизации по времени программы для одноразового вычисления следует иметь в виду, что в общее время решения задачи входит не только выполнение программы, но и время ее написания. Не стоит тратить усилия на оптимизацию программы, если она будет использоваться очень редко. Следует учитывать, что программа, реализующая некоторый алгоритм, не может быть оптимизирована до бесконечно малого времени вычисления: используемый алгоритм имеет определенную временную сложность и программу, основанную на слишком сложном алгоритме, существенно оптимизировать не удастся. Можно попытаться сменить алгоритм (хотя многие задачи этого сделать не позволяют) или ослабить требования к решениям. Иногда помогает упрощение алгоритма. К сожалению, оптимизация кода, как и программирование — задача неформальная, поэтому умение оптимизировать код приходит с опытом. Если скорость работы программы при большой длине данных не устраивает, следует поискать более эффективный алгоритм. Если же более эффективный алгоритм практически нецелесообразен, можно попытаться провести оптимизацию кода. Собственно, в данном примере для модуля timeit уже показан практический способ нахождения оптимального кода. Стоит также отметить, что с помощью профайлера нужно определить места кода, отнимающие наибольшую часть времени. Обычно это действия, выполняемые в самом вложенном цикле. Можно попытаться вынести из цикла все, что можно вычислить в более внешнем цикле или вообще вне цикла. В языке Python вызов функции является относительно дорогостоящей операцией, поэтому на критичных по скорости участках кода следует избегать вызова большого числа функций. В некоторых случаях работу программы на Python можно ускорить в несколько раз с помощью специального оптимизатора (он не входит в стандартную поставку Python, но свободно распространяется): psyco. Для ускорения программы достаточно добавить следующие строки в начале главного модуля программы: Листинг import psyco psyco.full() Правда, некоторые функции не поддаются «компиляции» с помощью psyco. В этих случаях будут выданы предупреждения. Посмотрите документацию по psyco с тем, чтобы узнать ограничения в его использовании и способы их преодоления. Еще одним вариантом ускорения работы приложения является переписывание критических участков алгоритма на языках более низкого уровня (С/С++) и использование модулей расширения из Python. Однако эта крайняя мера обычно не требуется или модули для задач, требующих большей эффективности, уже написаны. Например, для работы с растровыми изображениями имеется прекрасная библиотека модулей PIL (Python Imaging |