Использование транзакций в программах на Python

Задача
Вы хотите использовать транзакцию в сценарии DB-API.

Решение
Используйте стандартный механизм поддержки транзакций DB-API.

Обсуждение
В DB-API имеется абстракция, обеспечивающая контроль обработки транзакций за счет методов объектов соединений с базой данных. Вызовите begin() для начала транзакции и commit() или rollback() для ее завершения.

Вызовы begin() и commit() помещены в блок try, а rollback() – в соответствующий блок except для отмены транзакции в случае возникновения ошибки:

try:
conn.begin ()
cursor = conn.cursor ()
# передать деньги от одного человека другому
cursor.execute ("UPDATE money SET amt = amt - 6 WHERE name = 'Eve'")
cursor.execute ("UPDATE money SET amt = amt + 6 WHERE name = 'Ida'")
cursor.close ()
conn.commit()
except MySQLdb.Error, e:
print "Transaction failed, rolling back. Error was:"
print e.args
try: # пустой обработчик исключения, если откат не удался
conn.rollback ()
except:
pass

Добавлено: 23 Июля 2018 20:50:14 Добавил: Андрей Ковальчук

Текстовая обработка в языке Python. Подсказки для начинающих.

Как и ряд других популярных скриптовых языков, Python является великолепным инструментом для сканирования и манипуляций с текстовыми данными. Эта статья суммирует возможности текстовой обработки языка Python для тех программистов, которые являются новичками в программировании на языке Python. Эта статья объясняет некоторые основные понятия регулярных выражений и предлагает советы, когда стоит (а когда - не стоит) использовать регулярные выражения при обработке текста.

Что такое Python?
Python - это свободно доступный, интерпретируемый язык очень высокого уровня, разработанный Гвидо ван Россумом. Он объединяет ясный синтаксис с мощной (но необязательной) объектно-ориентированной семантикой. Python широко распространен и высокопортабелен.

Строки - неизменяемые последовательности
Как и в большинстве высокоуровневых языков программирования, строки переменной длины являются базовым типом в языке Python. Python выделяет область памяти для хранения строк (или других значений) "за кулисами", там, где программисту не нужно особенно задумываться об этом. Кроме того, Python имеет несколько возможностей управления строками, отсутствующих в других высокоуровневых языках.

В языке Python строки представляют собой "неизменяемые последовательности" ("immutable sequences"). Программа может обращаться к элементам или подпоследовательностям строк как к любым последовательностям, несмотря на то, что строки, как и кортежи (tuples), не могут быть изменены непосредственно "на месте". Python обращается к подпоследовательностям с помощью гибкой операции "среза", формат которой напоминает задание диапазона строк и столбцов в электронной таблице. Приведенная ниже интерактивная сессия иллюстрирует использование строк и срезов.

>>> s = "mary has a little lamb"
>>> s[0] # индекс с отсчетом от нуля
'm'
>>> s[3] = 'x' # непосредственное изменение элемента не удается
Traceback (innermost last):
File "<stdin>", line 1, in ?
TypeError: object doesn't support item assignment
>>> s[11:18] # 'вырезать' подпоследовательность
'little '
>>> s[:4] # пустое начало среза предполагает нуль
'mary'
>>> s[4] # индекс 4 не включен в срез [:4]
' '
>>> s[5:-5] # может использоваться индекс "с конца" с отрицательными числами
'had a little'
>>> s[:5]+s[5:] # соединение начала и конца среза
'mary had a little lamb'

Другая мощная строковая операция - просто ключевое слово in. Оно предлагает две интуитивные и полезные конструкции:
>>> s = "mary had a little lamb"
>>> for c in s[11:18]: print c, # печать каждого символа в срезе
...
l i t t l e
>>> if 'x' in s: print 'got x' # проверка на вхождение символа
...
>>> if 'y' in s: print 'got y' # проверка на вхождение символа
...
got y

Есть несколько способов написания строковых констант в языке Python. Вы можете использовать как одинарные, так и двойные кавычки при условии, пока символы открытия и закрытия соответствуют друг другу, и существует ряд других полезных вариантов. Если ваша строка содержит переводы строки или вложенные кавычки, тройные кавычки предоставляют удобный способ такого рода строк, как это сделано в следующем примере:
>>> s2 = """Mary had a little lamb
... its fleece was white as snow
... and everywhere that Mary went
... the lamb was sure to go"""
>>> print s2
Mary had a little lamb
its fleece was white as snow
and everywhere that Mary went
the lamb was sure to go

Как одинарные, так и тройные кавычки могут предваряться буквой "r" для обозначения того, что специальные символы регулярных выражений не должны интерпретироваться Python. Например:
>>> s3 = "this \n and \n that"
>>> print s3
this
and
that
>>> s4 = r"this \n and \n that"
>>> print s4
this \n and \n that

В "r-строках" обратный слэш, который в иных случаях может служить для задания специального символа, обрабатывается как обычный обратный слэш. Это объясняется далее при рассмотрении регулярных выражений.

Файлы и строковые переменные
Когда мы говорим "текстовая обработка", мы обычно подразумеваем обработку содержимого файла. На языке Python не составляет труда считать содержимое текстового файла в строковые переменные, где этим содержимым можно манипулировать. Файловые объекты обеспечивают три метода чтения: .read(), .readline(), and .readlines(). Каждый из этих методов может принимать аргумент для ограничения объема данных, считываемых за один раз, однако в основном они используются без аргумента. .read() считывает весь файл за один раз, и обычно используется для помещения содержимого файла в строковую переменную. Хотя .read() дает наиболее прямое строковое представление содержимого файла, он неудобен для последовательной строчно-ориентированной обработки файла, к тому же это невозможно, если размер файла превышает объем имеющейся памяти.

.readline() и .readlines() очень похожи. И та и другая используются в конструкциях наподобие следующей:
fh = open('c:\\autoexec.bat')
for line in fh.readlines():
print line

Различие между .readline() и .readlines() в том, что последняя, как и .read(), считывает весь файл за один раз. .readlines() автоматически парсит содержимое файла в список строк, который может быть обработан с помощью конструкции языка Python for ... in ....

С другой стороны, .readline() считывает только одну строку за раз, и в целом работает гораздо медленнее, чем .readlines(). .readline() следует использовать, только если памяти не хватает для считывания всего файла за один раз.

Если вы используете стандартный модуль, работающий с файлами, вы можете превратить строку в "виртуальный файл" с помощью модуля cStringIO (если требуется создание производных классов, можно использовать StringIO, но начинающим это требуется редко).

Например:
>>> import cStringIO
>>> fh = cStringIO.StringIO()
>>> fh.write("mary had a little lamb")
>>> fh.getvalue()
'mary had a little lamb'
>>> fh.seek(5)
>>> fh.write('ATE')
>>> fh.getvalue()
'mary ATE a little lamb'

Не забывайте, однако, что, в отличие от настоящего файла, "виртуальный файл", сформированный cStringIO - временный. Он исчезнет, когда программа завершится, если вы не предпримете каких-либо шагов, чтобы его сохранить (например, запишете его в реальный файл или воспользуетесь модулем shelve либо базой данных).

Стандартный модуль: string
Модуль string, возможно, в целом наиболее полезный модуль стандартных дистрибутивов языка Python 1.5.*. На самом деле похоже, что многие из возможностей модуля string будут существовать в качестве встроенных строковых методов в Python 1.6 и выше (подробности еще не были опубликованы на момент написания этой статьи). Наиболее вероятно, что любая программа, выполняющая обработку текста, должна начинаться со строки:
import string

Основное правило состоит в том, что если вы можете решить задачу с помощью модуля string, это правильный способ ее решения. В отличие от re (регулярных выражений), функции string в целом гораздо быстрее и в большинстве случаев проще для понимания и использования. Сторонние модули языка Python, включая и некоторые быстрые, написанные на С расширения, предназначены для специализированных задач, однако переносимость и простота, тем не менее, определяют привязку к string везде, где только возможно. Есть и исключения, однако не так много, как вы можете подумать, имея опыт использования других языков.

Модуль string содержит несколько типов инструментов, таких как функции, методы и классы. Он также содержит наиболее общие строковые константы. Например:
>>> import string
>>> string.whitespace
'\011\012\013\014\015 '
>>> string.uppercase
'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

Хотя вы можете написать эти константы сами, версии string более или менее гарантируют, что ваши константы будут правильны с точки зрения национального языка и платформы, на которой выполняется ваш скрипт на Python.

string также включает функции, преобразующие строки обычными способами (которые вы можете объединить для получения некоторых необычных преобразований). Например:
>>> import string
>>> s = "mary had a little lamb"
>>> string.capwords(s)
'Mary Had A Little Lamb'
>>> string.replace(s, 'little', 'fercious')
'mary had a ferocious lamb'

Существут множество других преобразований, не проиллюстрированных здесь особо; вы можете найти подробности в руководстве по языку Python. Кроме того, вы можете пользоваться функциями string для получения информации о таких атрибутах строки, как длина или позиции подстроки, например:
>>> import string
>>> s = "mary had a little lamb"
>>> string.find(s, 'had')
5
>>> string.count(s, 'a')
4

И наконец, string предоставляет очень характерную для языка Python особенность. Пара .split() и .join() обеспечивает быстрый способ преобразования строк в кортежи и наоборот, что вы найдете весьма полезным. Реализуется это просто:
>>> import string
>>> s = "mary had a little lamb"
>>> L = string.split(s)
>>> L
['mary', 'had', 'a', 'little', 'lamb'],br> >>> string.join(L, "-")
'mary-had-a-little-lamb'

Безусловно, в реальной жизни вы скорее всего будете делать со списком что-то еще, кроме немедленного объединения его вызовом .join() (возможно, что-то, включающее знакомую конструкцию for...in...).

Стандартный модуль: re
Модуль re делает устаревшими модули regex и regsub, которые использовались в старых кодах на языке Python. Хотя в использовании regex сохраняются небольшие преимущества, они незначительны и не стоят того, чтобы использовать его в в новом коде. Устаревшие модули скорее всего будут исключены из новых версий Python, и в 1.6, возможно, будет включен усовершенствованный модуль re. Так что пользуйтесь re для регулярных выражений.

Регулярные выражения сложны. Можно написать книгу на эту тему, и это на самом деле многие сделали! Эта статья постарается ухватить "гештальт" (базовую суть) регулярных выражений и позволит читателю извлечь ее.

Регулярное выражение - это краткий путь к описанию образцов (pattern), которые могут встретиться в тексте. Встречаются ли некие символы? В определенном ли порядке? Повторяются ли участки текста данное число раз? Исключено ли совпадение других участков? Концептуально это не так уж непохоже на то, как вы интуитивно описываете понятие образца на естественном языке. Хитрость состоит в кодировке этого описания в компактный синтаксис регулярных выражений.

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

Начните с самых маленьких фрагментов. На нижнем уровне любое регулярное выражение будет включать сопоставление с конкретными "символьными классами" ("character classes"). Простейший символьный класс представляет собой отдельный символ, который просто входит в образец как литерал. Вам часто может понадобиться сопоставить класс символов. Вы можете обозначить класс, заключив его в квадратные скобки; внутри скобок вы можете поместить как набор, так и диапазоны символов, которые обозначаются тире. Кроме того, вы можете использовать различные именованные символьные классы, корректные для вашей платформы и национального языка. Несколько примеров:
>>> import re
>>> s = "mary had a little lamb"
>>> if re.search("m", s): print "Match!" # char literal
...
Match!
>>> if re.search("[@A-Z]", s): print "Match!" # char class
... # match either at-sign or capital letter
...
>>> if re.search("\d", s): print "Match!" # digits class
...

Вы можете представлять символьные классы в виде "атомов" регулярных выражений и скорее всего захотите сгруппировать эти атомы в "молекулы". Это можно сделать с помощью комбинации группировки и повторения. Группировка обозначается круглыми скобками: каждое из подвыражений, содержащихся в скобках, рассматривается как атомарное для последующей группировки или повторения. Повторение отмечается одним из следующих операторов: "*" означающего "нуль или более"; "+" означающего "один или более"; "?" означающего "нуль или один". В качестве примера взгляните на выражение:
ABC([d-w]*\d\d?)+XYZ

Чтобы строка соответствовала этому выражению, она должна содержать нечто, начинающееся с "ABC" и заканчивающееся на "XYZ" -- но что должно быть в середине? Средним подвыражением является ([d-w]*\d\d?), сопровождаемое оператором "один или много". Таким образом, середина строки должна состоять из одного (или двух, или одной тысячи) фрагментов, соответствующих подвыражению в скобках. Строка "ABCXYZ" ему не соответствует, так как не содержит необходимых элементов в середине.

Что же представляет собой это внутреннее подвыражение? Оно начинается с нуля или более букв в интервале от d до w. Важно отметить, что нуль букв представляет правильное сопоставление, которое может быть контринтуитивным, если вы воспользуетесь для его описания словом "несколько". В следующей строке должна быть в точности одна цифра; затем ни одной или одна дополнительная цифра. (Первый цифровой символьный класс не имеет оператора повторения, тем самым просто встречается один раз. Второй цифровой символьный класс имеет оператор "?"). Короче говоря, все это подразумевает "одну или несколько цифр". Некоторые удовлетворяющие регулярному выражению строки выглядят так:
ABC1234567890XYZ
ABCd12e1f37g3XYZ
ABC1XYZ

А вот несколько выражений, которые не сопоставляются c этим выражением:
ABC123456789dXYZ
ABCdefghijklmnopqrstuvwXYZ
ABcd12e1f37g3XYZ
ABC12345%67890XYZ
ABCD12E1F37G3XYZ

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

Ресурсы:
Почитайте об mxTextTools, быстрой библиотеке обработки текста для Python.
A regular expressions how-to документ на www.python.org.

Добавлено: 29 Мая 2018 10:35:01 Добавил: Андрей Ковальчук

Функциональное программирование на языке Python

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

Что такое Python?
Python - свободно распространяемый, очень высокоуровневый интерпретируемый язык, разработанный Гвидо ван Россумом (Guido van Rossum). Он сочетает прозрачный синтаксис с мощной (но необязательной) объектно-ориентированной семантикой. Python доступен почти на всех существующих ныне платформах и обладает очень высокой переносимостью между платформами.

Что такое функциональное программирование?
Лучше всего начать с труднейшего вопроса - а что, собственно, такое "функциональное программирование (FP)"? Один из возможных ответов - "это когда вы пишете на языке наподобие Lisp, Scheme, Haskell, ML, OCAML, Clean, Mercury или Erlang (или еще на некоторых других)". Этот ответ, безусловно, верен, но не сильно проясняет суть. К сожалению, получить четкое мнение о том, что же такое FP, оказывается очень трудно даже среди собственно функциональных программистов. Вспоминается притча о трех слепцах и слоне. Возможно также определить FP, противопоставив его "императивному программированию" (тому, что вы делаете на языках наподобие C, Pascal, C++, Java, Perl, Awk, TCL и на многих других - по крайнее мере, большей частью).

Хотя автор всеми силами приветствует советы со стороны тех, кто лучше него знает предмет, он мог бы приблизительно охарактеризовать функциональное программирование как обладающее как минимум несколькими из следующих свойств. В языках, называемых функциональными, хорошо поддерживаются нижеперечисленные подходы, а все прочие подходы поддерживаются плохо или не поддерживаются вовсе:

* Функции - объекты первого класса. Т.е., все, что можно делать с "данными", можно делать и с функциями (вроде передачи функции другой функции в качестве параметра).
* Использование рекурсии в качестве основной структуры контроля потока управления. В некоторых языках не существует иной конструкции цикла, кроме рекурсии.
* Акцент на обработке списков (lists, отсюда название Lisp - LISt Processing). Списки с рекурсивным обходом подсписков часто используются в качестве замены циклов.
* "Чистые" функциональные языки избегают побочных эффектов. Это исключает почти повсеместно распространенный в императивных языках подход, при котором одной и той же переменной последовательно присваиваются различные значения для отслеживания состояния программы.
* FP не одобряет или совершенно запрещает утверждения (statements), используя вместо этого вычисление выражений (т.е. функций с аргументами). В предельном случае, одна программа есть одно выражение (плюс дополнительные определения).
* FP акцентируется на том, что должно быть вычислено, а не как.
* Большая часть FP использует функции "высокого порядка" (функции, оперирующие функциями, оперирующими функциями).

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

Функциональные возможности, присущие Python
Python поддерживает большую часть характеристик функционального программирования, начиная с версии Python 1.0. Но, как большинство возможностей Python, они присутствуют в очень смешанном языке. Так же как и с объектно-ориентированными возможностями Python, вы можете использовать то, что вам нужно, и игнорировать все остальное (пока оно вам не понадобится). В Python 2.0 было добавлено очень удачное "синтаксическое украшение" - списочные встраивания (list comprehensions). Хотя и не добавляя принципиально новых возможностей, списочные встраивания делают использование многих старых возможностей значительно приятнее.

Базовые элементы FP в Python - функции map(), reduce(), filter() и оператор lambda. В Python 1.x введена также функция apply(), удобная для прямого применения функции к списку, возвращаемому другой. Python 2.0 предоставляет для этого улучшенный синтаксис. Несколько неожиданно, но этих функций и всего нескольких базовых операторов почти достаточно для написания любой программы на Python; в частности, все управляющие утверждения ('if', 'elif', 'else', 'assert', 'try', 'except', 'finally', 'for', 'break', 'continue', 'while', 'def') можно представить в функциональном стиле, используя исключительно функции и операторы. Несмотря на то, что задача реального удаления всех команд управления потоком, возможно, полезна только для представления на конкурс "невразумительный Python" (с кодом, выглядящим как программа на Lisp'е), стоит уяснить, как FP выражает управляющие структуры через вызовы функций и рекурсию.

Исключение команд управления потоком
Первое, о чем стоит вспомнить в нашем упражнении - то, что Python "замыкает накоротко" вычисление логических выражений.1 Оказывается, это предоставляет эквивалент блока 'if'/'elif'/'else' в виде выражения. Итак:

#------ "Короткозамкнутые" условные вызовы в Python -----#
# Обычные управляющие конструкции 
if <cond1>: func1()
elif <cond2>: func2()
else: func3()

# Эквивалентное "накоротко замкнутое" выражение
(<cond1> and func1()) or (<cond2> and func2()) or (func3())

# Пример "накоротко замкнутого" выражения
>>> x = 3
>>> def pr(s): return s
>>> (x==1 and pr('one')) or (x==2 and pr('two')) or (pr('other'))
'other'
>>> x = 2
>>> (x==1 and pr('one')) or (x==2 and pr('two')) or (pr('other'))
'two'

Казалось бы, наша версия условных вызовов с помощью выражений - не более, чем салонный фокус; однако все становится гораздо интересней, если учесть, что оператор lambda может содержать только выражения! Раз, как мы только что показали, выражения могут содержать условные блоки, используя короткое замыкание, выражение lambda позволяет в общей форме представить условные возвращаемые значения. Базируясь на предыдущем примере:
#--------- Lambda с короткозамкнутыми условными выражениями в Python -------#
>>> pr = lambda s:s
>>> namenum = lambda x: (x==1 and pr("one")) 
... or (x==2 and pr("two")) 
... or (pr("other"))
>>> namenum(1)
'one'
>>> namenum(2)
'two'
>>> namenum(3)
'other'

Функции как объекты первого класса
Приведенные примеры уже засвидетельствовали, хотя и неочевидным образом, статус функций как объектов первого класса в Python. Дело в том, что, создав объект функции оператором lambda, мы произвели чрезвычайно общее действие. Мы имели возможность привязать наш объект к именам pr и namenum в точности тем же способом, как могли бы привязать к этим именам число 23 или строку "spam". Но точно так же, как число 23 можно использовать, не привязывая ни к какому имени (например, как аргумент функции), мы можем использовать объект функции, созданный lambda, не привязывая ни к какому имени. Функция в Python - всего лишь еще одно значение, с которым можно что-то сделать.

Главное, что мы делаем с нашими объектами первого класса - передаем их во встроенные функции map(), reduce() и filter(). Каждая из этих функций принимает объект функции в качестве первого аргумента. map() применяет переданную функцию к каждому элементу в переданном списке (списках) и возвращает список результатов. reduce() применяет переданную функцию к каждому значению в списке и ко внутреннему накопителю результата; например, reduce(lambda n,m:n*m, range(1,10)) означает 10! (факториал 10 - умножить каждый элемент на результат предыдущего умножения). filter() применяет переданную функцию к каждому элементу списка и возвращает список тех элементов исходного списка, для которых переданная функция вернула значение истинности. Мы также часто передаем функциональные объекты нашим собственным функциям, но чаще некоторым комбинациям вышеупомянутых встроенных функций.

Комбинируя три этих встроенных FP-функции, можно реализовать неожиданно широкий диапазон операций потока управления, не прибегая к утверждениям (statements), а используя лишь выражения.

Функциональные циклы в Python
Замена циклов на выражения так же проста, как и замена условных блоков. 'for' может быть впрямую переведено в map(). Так же, как и с условным выполнением, нам понадобится упростить блок утверждений до одного вызова функции (мы близки к тому, чтобы научиться делать это в общем случае):
#---------- Функциональный цикл 'for' в Python ----------#
for e in lst: func(e) # цикл на утверждении 'for'
map(func,lst) # цикл, основанный на map()

Кстати, похожая техника применяется для реализации последовательного выполнения программы, используя функциональный подход. Т.е., императивное программирование по большей части состоит из утверждений, требующих "сделать это, затем сделать то, затем сделать что-то еще". 'map()' позволяет это выразить так:
#----- Функциональное последовательное выполнение в Python ----------#
# создадим вспомогательную функцию вызова функции
do_it = lambda f: f()

# Пусть f1, f2, f3 (etc) - функции, выполняющие полезные действия
map(do_it, [f1,f2,f3]) # последовательное выполнение, реализованное на map()

В общем случае, вся главная программа может быть вызовом 'map()' со списком функций, которые надо последовательно вызвать, чтобы выполнить программу. Еще одно удобное свойство функций как объектов - то, что вы можете поместить их в список.

Перевести 'while' впрямую немного сложнее, но вполне получается :
#-------- Функциональный цикл 'while' в Python ----------#
# Обычный (основаный на утверждении 'while') цикл
while <cond>:
 <pre-suite>
 if <break_condition>:
 break
 else:
 <suite>

# Рекурсивный цикл в функциональном стиле
def while_block():
 <pre-suite>
 if <break_condition>:
 return 1
 else:
 <suite>
 return 0

while_FP = lambda: (<cond> and while_block()) or while_FP()
while_FP()

Наш вариант 'while' все еще требует функцию while_block(), которая сама по себе может содержать не только выражения, но и утверждения (statements). Но мы могли бы продолжить дальнейшее исключение утверждений в этой функции (как, например, замену блока 'if/else' в вышеописанном шаблоне на короткозамкнутое выражение). К тому же, обычная проверка на месте <cond> (наподобие 'while myvar==7') вряд ли окажется полезной, поскольку тело цикла (в представленном виде) не может изменить какие-либо переменные (хотя глобальные переменные могут быть изменены в while_block()). Один из способов применить более полезное условие - заставить while_block() возвращать более осмысленное значение и сравнивать его с условием завершения. Стоит взглянуть на реальный пример исключения утверждений:
#---------- Функциональный цикл 'echo' в Python ------------#
# Императивная версия "echo()"
def echo_IMP():
 while 1:
 x = raw_input("IMP -- ")
 if x == 'quit':
 break
 else
 print x
echo_IMP()

# Служебная функция, реализующая "тождество с побочным эффектом"
def monadic_print(x):
 print x
 return x

# FP версия "echo()"
echo_FP = lambda: monadic_print(raw_input("FP -- "))=='quit' or echo_FP()
echo_FP()

Мы достигли того, что выразили небольшую программу, включающую ввод/вывод, циклы и условия в виде чистого выражения с рекурсией (фактически - в виде функционального объекта, который при необходимости может быть передан куда угодно). Мы все еще используем служебную функцию monadic_print(), но эта функция совершенно общая и может использоваться в любых функциональных выражениях , которые мы создадим позже (это однократные затраты).2 3 Заметьте, что любое выражение, содержащее monadic_print(x) вычисляется так же, как если бы оно содержало просто x. В FP (в частности, в Haskell) есть понятие "монады" для функции, которая "не делает ничего, и вызывает побочный эффект при выполнении".

Исключение побочных эффектов
После всей проделанной работы по избавлению от совершенно осмысленных конструкций и замене их на невразумительные вложенные выражения, возникает естественный вопрос - "Зачем?!". Перечитывая мои описания характеристик FP, мы можем видеть, что все они достигнуты в Python. Но важнейшая (и, скорее всего, в наибольшей степени реально используемая) характеристика - исключение побочных эффектов или, по крайней мере, ограничение их применения специальными областями наподобие монад. Огромный процент программных ошибок и главная проблема, требующая применения отладчиков, случается из-за того, что переменные получают неверные значения в процессе выполнения программы. Функциональное программирование обходит эту проблему, просто вовсе не присваивая значения переменным.

Взглянем на совершенно обычный участок императивного кода. Его цель - распечатать список пар чисел, чье произведение больше 25. Числа, составляющие пары, сами берутся из двух других списков. Все это весьма напоминает то, что программисты реально делают во многих участках своих программ. Императивный подход к этой задаче мог бы выглядеть так:
#--- Императивный код для "печати произведений" ----#
# Процедурный стиль - поиск больших произведений с помощью вложенных циклов
xs = (1,2,3,4)
ys = (10,15,3,22)
bigmuls = []
#...прочий код...
for x in xs:
 for y in ys:
 #...прочий код...
 if x*y > 25:
 bigmuls.append((x,y))
 #...прочий код...
#...прочий код...
print bigmuls

Этот проект слишком мал для того, чтобы что-нибудь пошло не так. Но, возможно, он встроен в код, предназначенный для достижения множества других целей в то же самое время. Секции, комментированные как "#...прочий код..." - места, где побочные эффекты с наибольшей вероятностью могут привести к ошибкам. В любой из этих точек переменные xs, ys, bigmuls, x, y могут приобрести неожиданные значения в гипотетическом коде. Далее, после завершения этого куска кода все переменные могут иметь значения, которые могут ожидаются, а могут и не ожидаться посдедующим кодом. Очевидно, что инкапсуляция в функциях/объектах и тщательное управление областью видимости могут использоваться, чтобы защититься от этого рода проблем. Вы также можете всегда удалять ('del') ваши переменные после использования. Но, на практике, указанный тип ошибок весьма обычен.

Функциональный подход к нашей задаче полностью исключает ошибки, связанные с побочными эффектами. Возможное решение могло бы быть таким:
#--- Функциональный код для поиска/печати больших произведений на Python ----#
bigmuls = lambda xs,ys: filter(lambda (x,y):x*y > 25, combine(xs,ys))
combine = lambda xs,ys: map(None, xs*len(ys), dupelms(ys,len(xs)))
dupelms = lambda lst,n: reduce(lambda s,t:s+t, map(lambda l,n=n: [l]*n, lst))
print bigmuls((1,2,3,4),(10,15,3,22))

Мы связываем в примере анонимные ('lambda') функции с именами, но это не необходимо. Вместо этого мы могли просто вложить определения. Мы использовали имена как ради большей читаемости, так и потому, что combine() - в любом случае отличная служебная функция (генерирует список всех возможных пар элементов из двух списков). В свою очередь, dupelms() в основном лишь вспомогательная часть combine(). Хотя этот функциональный пример более многословен, чем императивный, при повторном использовании служебных функций код в собственно bigmuls() окажется, вероятно, более лаконичным, чем в императивном варианте.

Реальное преимущество этого функционального примера в том, что в нем абсолютно ни одна переменная не меняет своего значения. Какое-либо неожиданное побочное влияние на последующий код (или со стороны предыдущего кода) просто невозможно. Конечно, само по себе отсутствие побочных эффектов не гарантирует безошибочность кода, но в любом случае это преимущество. Однако заметьте, что Python, в отличие от многих функциональных языков, не предотвращает повторное привязывание имен bigmuls, combine и dupelms. Если дальше в процессе выполнения программы combine() начнет значить что-нибудь другое - увы! Можно было бы разработать класс-одиночку (Singleton) для поддержки однократного связывания такого типа (напр. 's.bigmuls', etc.), но это выходит за рамки настоящей статьи.

Еще стоит отметить, что задача, которую мы только что решили, скроена в точности под новые возможности Python 2.0. Вместо вышеприведенных примеров - императивного или функционального - наилучшая (и функциональная) техника выглядит следующим образом:
#----- Код Python для "bigmuls" с использованием списочных встраиваний (list comprehensions) -----#
print [(x,y) for x in (1,2,3,4) for y in (10,15,3,22) if x*y > 25]

Заключение
Эта статья продемонстрировала способы замены практически любой конструкции управления потоком в Python на функциональный эквивалент (избавляясь при этом от побочных эффектов). Эффективный перевод конкретной программы требует дополнительного обдумывания, но мы увидели, что встроенные функциональные примитивы являются полными и общими. В последующих статьях мы рассмотрим более мощные подходы к функциональному программированию; и, я надеюсь, сможем подробнее рассмотреть "pro" и "contra" функционального подхода.

Добавлено: 24 Мая 2018 21:34:20 Добавил: Андрей Ковальчук

Подходы языка Python - забавный пример оптимизации

Однажды приятель задал мне, казалось бы, простой вопрос: как лучше всего преобразовать список целых чисел в строку, предполагая, что эти целые числа представлены в формате ASCII. Например, список [97, 98, 99] должен быть преобразован в строку 'abc'. Допустим, что мы хотим написать для этого некоторую функцию.

Первый вариант, который я придумал, был откровенно простым:

def f1(list):
 string = ""
 for item in list:
 string = string + chr(item)
 return string

"Этот способ не может быть самым быстрым,"- сказал мой приятель. Как насчет вот такого:
def f2(list):
 return reduce(lambda string, item: string + chr(item), list, "")

Этот вариант выполняет в точности тот же набор строковых операций, что и предыдущий, но тут мы отказались от накладных расходов на выполнение цикла for в пользу, как предполагалось, более быстрого неявного цикла функции reduce().

"Конечно,"- ответил я, - "но он делает все это за счет вызова функции (lambda) для каждого элемента списка. Могу спорить, что это медленнее, ведь вызов функции в языке Python требует больших накладных расходов, чем цикл".

(Хорошо, я уже сравнил перед этим: f2() потребовала на 60% больше времени, чем f1(). Вот так :-)

"Хмм,"- сказал мой знакомый - "мне нужно, чтобы все это работало быстрее". "Хорошо," - сказал я, - "как насчет такой версии":
def f3(list):
 string = ""
 for character in map(chr, list):
 string = string + character
 return string

К обоюдному удивлению, f3() оказалась вдвое быстрее, чем f1()! Причина нашего удивления была двоякой: во-первых, в этом случае использовался больший объем памяти (результат вызова map(chr, list) представляет собой еще один список той же длины); во-вторых, здесь содержалось два цикла вместо одного (тот, что заключен в функции map(), и цикл for).

Безусловно, пространство за счет времени - это известный компромисс, так что первое не должно было нас удивить. И все же как два цикла оказались быстрее, чем один? Этому есть две причины.

Во-первых, в f1() встроенная функции chr() ищется при каждой итерации, тогда как в f3() это делается только один раз (при обработке аргумента map()). "Поиск относительно дорог," - сказал я приятелю- "поскольку правила динамической области имен Python предполагают поиск сначала в общем словаре текущего модуля (где он оказывается неудачным), а затем в словаре встроенных функций (где и находят искомое). Хуже то, что неудачный словарный поиск в среднем чуть медленнее, чем успешный, из-за особенностей цепочечного хэширования."

Вторая причина того, что f3() быстрее, чем f1(), заключается в том, что обращение к chr(item), выполняемое интерпретатором байт-кода, вероятно, чуть медленнее, чем когда это делается функцией map() - интерпретатору байт-кода приходится выполнять три байт-кодовых инструкции для каждого обращения (load 'chr', load 'item', call), тогда как функция map() делает это все на C.

Все это привело нас к идее компромисса, который позволил бы не тратить лишнее пространство, но ускорил бы поиск функции chr():
def f4(list):
 string = ""
 lchr = chr
 for item in list:
 string = string + lchr(item)
 return string

Как и ожидалось, f4() оказалась медленнее, чем f3(), но только на 25%; и все же была примерно на 40% быстрее, чем f1(). Так получилось потому, что поиск локальных переменных происходит быстрее, чем поиск глобальных или встроенных переменных: "компилятор" языка Python оптимизирует большую часть тел функций таким образом, что для локальных переменных не требуется поиска в словаре, а достаточно простой индексации массива. Относительная скорость f4() в сравнении с f1() и f3() предполагает существование обоих названных выше причин быстрой работы функции f3(), однако первая причина (меньшее число поисков) чуть важнее. (Чтобы получить более точные данные об этом, мы должны были бы вкомпилировать соответствующие возможности в интерпретатор).

Тем не менее, наш лучший вариант, f3(), до сих пор был всего лишь в два раза быстрее, чем самое прямолинейное решение, f1(). Могли ли мы что-то улучшить?

Я беспокоился, что квадратичное поведение алгоритма нас погубит. До сих пор мы использовали в качестве тестовых данных список из 256 целых чисел, поскольку именно для этого моему знакомому и нужна была рассматриваемая функция. Но что было бы, если применить ее к списку из двух тысяч символов? Мы бы соединяли все более и более длинные строки, по одному символу за раз. Легко видеть, что, помимо накладных расходов, чтобы создать таким образом список длиной N, придется копировать 1 + 2 + 3 + ... + (N-1) символов, или N*(N-1)/2, или 0.5*N**2 - 0.5*N. Кроме того, существует N операций выделения строки, однако для достаточно большого N элемент, содержащий N**2, превосходит по накладным расходам эти операции. Действительно, для списка в 2048 элементов, который в 8 раз длиннее тестового, любая из этих функций выполняется медленнее много больше, чем в 8 раз; фактически, ближе к 16. Я не осмелился попробовать список, в 64 раза длиннее тестового.

Для того чтобы избежать квадратичного поведения подобных алгоритмов, существует общий подход. Я записал его для строк, состоящих точно из 256 элементов:
def f5(list):
 string = ""
 for i in range(0, 256, 16): # 0, 16, 32, 48, 64, ...
 s = ""
 for character in map(chr, list[i:i+16]):
 s = s + character
 string = string + s
 return string

К несчастью, для списка из 256 элементов эта версия работала немного медленнее (хотя и не более чем на 20%), чем f3(). Поскольку написание общей версии могло только замедлить процесс, мы не стали беспокоиться о том, чтобы далее рассматривать это направление (за исключением того, что мы все же сравнили его с вариантом, не использующим map(), который, конечно же, опять оказался медленнее).

В конце концов я попробовал радикально отличный от предыдущих подход: использовать только неявные циклы. Заметьте, что вся операция в целом может быть описана следующим образом: применить chr() к каждому из элементов списка; затем конкатенировать полученные символы. Мы уже использовали неявный цикл для первой части: map(). К счастью, в строковом модуле есть несколько реализованных на С функций конкатенации строк. В частности, string.joinfields(list_of_strings, delimiter) конкатенирует список строк, помещая заданный разделитель между каждыми двумя строками. Ничто не мешало нам произвести конкатенацию списка символов (которые всего лишь строки единичной длины в языке Python), используя пустую строку как разделитель. Слушайте и смотрите:
import string
 def f6(list):
 return string.joinfields(map(chr, list), "")

Эта функция работала в четыре-пять раз быстрее, чем самый быстрый из ее главных соперников, f3(). Более того, у нее нет квадратичного поведения прежних версий.

И победителем стал...

На следующий день я вспомнил об одной особенности языка Python: модуле array. Этот модуль имеет операции создания массива однобайтовых целых чисел из списка целых чисел языка Python, и каждый массив может быть записан в файл или преобразован в строку как бинарная структура данных. Вот наша функция, реализованная с использованием этих операций:
import array
 def f7(list):
 return array.array('b', list).tostring()

Это уже втрое быстрее, чем f6(), или в 12-15 раз быстрее чем f3()! Здесь также использован меньший объем промежуточный памяти - выделяются только два объекта из N байт (плюс фиксированные накладные расходы), тогда как f6() начинает с выделения списка из N элементов, которое обычно стоит 4N байт (8N байт на 64-битной машине) - в предположении, что символьные объекты разделяются с подобными объектами повсюду в программе (как для малых целых чисел, в большинстве случаев Python кэширует строки единичной длины).

"Стоп,"- сказал мой знакомый -"остановимся, пока мы не получили отрицательного времени выполнения - такой скорости вполне достаточно для моей программы". Я согласился, хотя мне хотелось попробовать еще один подход: написать всю функцию на С. Это помогло бы минимизировать потребности в объеме памяти (она будет выделять сразу строку длины N) и сэкономить несколько лишних инструкций в коде на С, которые, как я знал, были в модуле array, так как он более универсален (поддерживает целые числа шириной в 1, 2 и 4 байта). Тем не менее, при этом не удалось бы избежать необходимости извлекать элементы из списка по одному, а также получать из них целые числа С: обе эти операции являются достаточно дорогостоящими в Python-C API, так что я предполагал в лучшем случае небольшое ускорение по сравнению с f7(). Учитывая усилия, которые необходимо было бы затратить на написание и тестирование расширения (в сравнении с набрасыванием пары строк на Python), и зависимость от нестандартного расширения Python, я решил не исследовать этот вариант...
Вывод
Если вам крайне необходима скорость, обратитесь к встроенным функциям - вы не сможете создать цикл лучше, чем написанный на С. Поищите функции, делающие то, что вам нужно, в библиотечном руководстве по встроенным функциям. Если там нет такой функции, ниже приводятся некоторые принципы оптимизации циклов:

* Правило номер один: оптимизируйте только явно критические участки. Оптимизируйте только самый внутренний цикл. (Это правило существует независимо от языка Python, но невредно его повторить, поскольку оно может сэкономить много работы. :-)
* Маленькое красиво. Учитывая высокие накладные расходы на байт-кодовые инструкции и поиск переменных, редко стоит добавлять в код дополнительные проверки для экономии небольшой работы.
* Используйте встроенные операции. Неявный цикл в map() работает быстрее, чем явный цикл for; цикл while с явным счетчиком цикла работает еще медленнее.
* Избегайте вызова функций, написанных на Python, во внутреннем цикле. Это относится и к lambda. Развертка (inlining) внутреннего цикла может сэкономить много времени.
* Локальные переменные обрабатываются быстрее, чем глобальные; если вы используете глобальную константу в цикле, скопируйте ее в локальную переменную перед циклом. Кроме того, в языке Python функции (глобальные или встроенные) также являются глобальными константами!
* Попробуйте использовать map(), filter() или reduce() для замены явного цикла for, но только если вы можете использовать встроенную функцию: map() со встроенной функцией быстрее for, однако for с развернутым (in-line) кодом быстрее, чем map() с lambda-функцией!
* Проверьте ваш алгоритм на квадратичное поведение. Но заметьте, что более сложный алгоритм окупается только в случае больших значений N - для маленьких N сложность не окупается. В нашем случае 256 оказалось достаточно маленьким значением для того, чтобы более простая версия функции оставалась самой быстрой. Ваши затраты в разных случаях могут отличаться - это стоит исследовать.
* И последнее по упоминанию, но не по значению: собирайте данные. Великолепный модуль профилирования языка Python может быстро продемонстрировать вам узкое место в вашем коде. Если вы сравниваете разные версии некоторого алгоритма, тестируйте его в коротком цикле, используя функцию time.clock().

Кстати, вот функция хронометража, которую использовал я. Она вызывает функцию f n*10 раз с аргументом a, и печатает имя функции и следом - время, которое она отработала, округленное до миллисекунд. 10 повторных вызовов делаются для минимизации накладных расходов самой функции хронометража. Вы можете пойти даже дальше и сделать 100 вызовов... Заметьте также, что выражение range(n) рассчитывается вовне рамок измерения - другой прием минимизации расходов, вносимых функцией хронометража. Если вы обеспокоены этими расходами, вы можете откалибровать их с помощью вызова функции хронометража с пустой (ничего не делающей) функцией.
import time
 def timing(f, n, a):
 print f.__name__,
 r = range(n)
 t1 = time.clock()
 for i in r:
 f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a)
 t2 = time.clock()
 print round(t2-t1, 3)

Эпилог

Несколькими днями позже мой приятель снова обратился ко мне с вопросом: как ты произведешь обратную операцию? Т.е. создание списка ASCII-кодов из строки. О нет, вот мы и снова тут, промелькнуло у меня в голове...

Но в этот раз все оказалось относительно безболезненным. Было два кандидата, очевидный:
def g1(string):
 return map(ord, string)

И несколько менее очевидный:
import array
 def g2(string):
 return array.array('b', string).tolist()

Определение времени их работы показало, что g2() примерно в пять раз быстрее, чем g1(). Хотя была и ловушка: g2() возвращала целые числа в интервале -128..127, тогда как g1() возвращала целые числа в интервале 0..255. Если вам необходимы положительные числа, g1() будет быстрее, чем любая постобработка результатов, полученных с помощью g2(). (Примечание: с тех пор, как было написано это эссе, в модуль array был добавлен код типа 'B' для беззнаковых байт, таким образом теперь больше нет оснований для предпочтения функции g1()).

Добавлено: 24 Мая 2018 20:57:46 Добавил: Андрей Ковальчук

Итераторы и простые генераторы Python

В Python 2.2 появилась новая конструкция со своим ключевым словом. Эта конструкция - генератор, а ключевое слово - yield. Хотя генераторы позволяют реализовать новые, мощные и оригинальные идеи, все же не так-то просто понять, как они работают. Эта статья - попытка ненавязчивого объяснения этой конструкции, равно как связанного с ней понятия итераторов.

Что такое Python?
Python - свободно доступный, интерпретируемый язык программирования высокого уровня, разработанный Гвидо ван Россумом (Guido van Rossum). Он объединяет ясный синтаксис с мощной (но необязательно) объектно-ориентированной семантикой. Python может быть установлен на любой платформе и обеспечивает прекрасную совместимость при переходе с одной платформы на другую.

Введение
Добро пожаловать в мир экзотического управления потоками данных. В Python 2.2 разработчики получают возможности, которые раньше были недоступны, или, по крайней мере, не так удобоваримы, в более ранних версиях языка.

И хотя то, что предлагает Python 2.2, не настолько умопомрачительно, как, например, полные продолжения и микронити, представленные в Stackless Python, генераторы и итераторы действительно могут кое-что, что выделяет их среди традиционных функций и классов.

Давайте рассмотрим сначала итераторы, поскольку их легче понять. Прежде всего, итератор - это объект, у которого имеется метод .next(). Это не совсем верно, но достаточно близко. На самом деле, большая часть контекстов требует объект, который сгенерирует итератор, когда к нему применяется новая встроенная функция iter(). Для того, чтобы определенный пользователем класс (который имеет необходимый метод .next()) возвращал итератор, нужно всего лишь обеспечить возврат self методом __iter__(). Примеры ниже пояснят сказанное. Метод .next() может вызвать исключение StopIteration, если итерация логически завершилась.

Генератор немного сложнее и является более общим понятием. Генераторы используются в основном для определения итераторов; поэтому не всегда стоит учитывать все тонкости их применения. Генератор является функцией, которая запоминает точку в теле функции, из которой происходил последний возврат. Второй (или n-ный) вызов генератора оказывается в середине функции, причем все локальные переменные оказываются неизмененными с момента последнего вызова.

В некоторой степени генераторы похожи на замыкания (closure), о которых шла речь в предыдущих статьях о функциональном программировании. Подобно замыканию, генератор "помнит" состояние своих данных. Но с генератором можно достигнуть большего в том смысле, что он также "помнит" свою позицию в пределах структуры управления потоком данных (что в императивном программировании нечто большее, чем просто значения данных). Продолжения по-прежнему более общие конструкции, поскольку они позволяют произвольно перемещаться между кадрами стека, а не всегда возвращаться в контекст вызывающей функции (как делает генератор).

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

Случайное блуждание
С целью пояснения, позвольте мне поставить довольно простую задачу, которую можно решить различными способами: как новыми, так и старыми. Предположим, мы хотим получить поток случайных чисел меньших единицы, которые подчиняются обратному ограничению. А именно, мы хотим, чтобы каждое следующее число было, по крайней мере, на 0.4 больше или меньше предыдущего. Более того, сам поток не бесконечен, а заканчивается после случайного числа шагов. Например, мы прервем его, как только появится число меньшее 0.1. Описанные ограничения несколько схожи с теми, что можно найти в алгоритме "случайного блуждания", причем условие окончания напоминает "локальный минимум", но, определенно, эти требования мягче, чем при решении реальных задач.

Python 2.1 или его более ранние версии предлагают несколько методов решения этой задачи. В данном случае будем просто создавать и отправлять список чисел в поток. Это может выглядеть следующим образом;

# RandomWalk_List.py #
import random
def randomwalk_list():

# инициализация потенциальных элементов
last, rand = 1, random.random()

# пустой список
nums = []

# условие прерывания
while rand > 0.1:

  # принятие числа
  if abs(last-rand) >= 0.4:
    last = rand
    # добавление последнего
    # элемента в nums
    nums.append(rand)
  else:
    # отображение отклонения
    print '*',

  # новый потенциальный элемент
  rand = random.random()

  # добавление последнего малого элемента
  nums.append(rand)
  return nums
Использовать эту функцию очень просто:

# Iterate over Random Walk List #
for num in randomwalk_list():
  print num,

Однако данный подход обладает ощутимыми ограничениями. Крайне маловероятно, что данный пример сгенерирует длинный список; но, сделав условие прерывания более жестким, мы могли бы создавать произвольно длинные потоки (их точный размер будет случайным, но порядок величин можно спрогнозировать). В определенный момент проблемы памяти и эффективности могут сделать этот подход неприемлемым и излишним. Именно эта проблема и вынудила добавить функции xrange() и xreadlines() в более ранние версии Python. Еще более существенно то, что многие потоки зависят от внешних событий, и все же они должны быть обработаны, когда каждый элемент доступен. Например, поток может слушать порт или ожидать ввода пользователя. В этих случаях создание полного списка из такого потока просто неприемлемо. Python 2.1 и более ранние версии предлагали еще один прием: можно было использовать "статическую" локальную переменную для запоминания информации о последнем вызове функции. Очевидно, глобальные переменные могли бы сделать то же самое, но они порождают хорошо знакомые проблемы: засоряют глобальное пространство имен и допускают ошибки, вызванные нелокальностью. Возможно, это вас удивит - если вы не знакомы с этой хитростью - в Python нет "официального" объявления статической области. Однако, если именованные параметры имеют изменяемые значения по умолчанию, они могут быть долговременными хранилищами предыдущих вызовов. Списки, в частности, удобные изменяемые объекты, которые могут содержать даже множественные значения.

Используя "статический" подход мы можем написать следующую функцию:
# RandomWalk_Static.py #
import random

# инициализация "статических" переменных
def randomwalk_static(last=[1]):

# инициализация возможного результата
rand = random.random()

# условие прерывания
if last[0] < 0.1:
  # признак конца потока
  return None
  
# поиск приемлемого кандидата
while abs(last[0]-rand) < 0.4:
  # отображение отклонения
  print '*',
  # новый кандидат
  rand = random.random()
  # обновить "статическую" переменную
  last[0] = rand
  return rand

Эта функция весьма некритична к памяти. Ей достаточно помнить только одно предыдущее значение, она возвращает всего лишь единственное число (а не длинный список чисел). Подобная функция могла бы вернуть следующую величину, зависящую (частично или полностью) от внешних событий. Недостаток этого подхода в том, что он несколько менее лаконичен и много менее элегантен.
# Iterate over Static Random Walk #
num = randomwalk_static()
while num is not None:
  print num,
  num = randomwalk_static()

Новый способ блуждания
"Под капотом" Python 2.2 все последовательности - итераторы. Знаменитая питоновская конструкция 'for elem in lst:' теперь фактически запрашивает lst для создания итератора. Цикл for будет затем последовательно вызывать метод .next() этого итератора, пока не достигнет исключения StopIteration. К счастью, программистам на Python не нужно знать, что происходит в этом месте, поскольку все встроенные типы генерируют свои итераторы автоматически. На самом деле, сейчас словари имеют методы .iterkeys(), .iteritems() и .itervalues() для создания итераторов; первый соответствует новой конструкции: 'for key in dct:'. Подобно этому, новая конструкция 'for line in file:' поддерживается итератором, вызывающим .readline().

Но зная, что фактически происходит внутри интерпретатора Python, становится очевидным, как использовать пользовательские классы, которые генерируют свои собственные итераторы, а не итераторы встроенных типов. Пример пользовательского класса, позволяющего напрямую использовать randomwalk_list(), а также экономный - по-элеметный -randomwalk_static, приведен ниже:
# RandomWalk_Iter.py #
import random
class randomwalk_iter:
  def __init__(self):
  # инициализация предыдущего значения
  self.last = 1
  
  # инициализация кандидата
  self.rand = random.random()
  def __iter__(self):
  # создание простейшего итератора
  return self
  def next(self):
  
  # условие прерывания
  if self.rand < 0.1:
    # конец итерации
    raise StopIteration
    # поиск приемлемого кандидата
  else:
    while 
      abs(self.last-self.rand)<0.4:
      # отображение отклонения
      print '*',
      # новый кандидат
      self.rand = random.random()
      # обновление предыдущего значения
      self.last = self.rand
      return self.rand

Применение этого пользовательского итератора аналогично использованию истинного списка, сгенерированного функцией:
# Iterate with Random Walk Class #
for num in randomwalk_iter():
  print num,

На самом деле, выполняется даже конструкция 'if elem in itetator', которая проверяет только столько элементов итератора, сколько нужно для определения истинности (конечно, если она выдаст "ложь", ей потребуется проверить все элементы).

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

Генераторы просто обходят всю эту проблему. Генератор "возвращает управление" новым ключевым словом yield, но "помнит" точную точку исполнения, где произошел возврат. При следующем вызове генератора, он начинается с того места, где его оставили до этого, - и в смысле хода исполнения функции, и в смысле значения переменных.

В Python 2.2 генераторы не пишутся непосредственно. Вместо этого пишется функция, возвращающая генератор при вызове. Это может показаться странным, но, поскольку "фабрика функций" является естественной возможностью Python, "фабрика генераторов" кажется ее очевидным концептуальным развитием. Благодаря наличию в теле функции одной или нескольких директив yield, она превращается в фабрику функций. Если в теле кода встречается директива yield, оператор return может встречаться только без возвращаемого значения. Однако лучше составить тело функции так, что исполнение просто "вывалилось с конца" после того, как все директивы yield будут выполнены. Но если встречается оператор return, то он заставляет созданный генератор возбудить исключение StopIteration, а не вернуть дальнейшие значения.

Мне кажется, что выбор подобного синтаксиса для создания фабрик генераторов не совсем оправдан. Директива yield легко может оказаться глубоко в теле функции, и в пределах первых N строк функции будет невозможно определить, является ли функция фабрикой генераторов. Разумеется, это справедливо и в отношении фабрики функций, но реализация фабрики функций не меняет существующий *синтаксис* тела функции (и допускается, что иногда тело функции может вернуть простую величину; хотя, возможно, не от хорошего дизайна). По-моему, новое ключевое слово - generator вместо def - было бы лучшим выбором.

Оставив в стороне полемику о лучшем синтаксисе, отметим, что генераторы могут работать автоматически как итераторы, когда их для этого вызывают. Для этого не требуется никаких методов классов вроде .__iter__(). Каждая директива yield становится возвращаемой величиной для метода .next() генератора. Простейший пример поясняет сказанное:
# Simplest Possible Python 2.2 Generator #
>>>from __future__ import generators
>>>def gen():
 yield 1

>>>g = gen()
>>>g.next()
1
>>>g.next()
Traceback (most recent call last):
 File "", line 1, in ?
 g.next()
StopIteration
Давайте задействуем генератор для решения обсуждавшийся выше задачи:

# RandomWalk_Generator.py #
# нужно только для Python 2.2
from __future__ import generators
import random

def randomwalk_generator():
  # инициализация потенциальных элементов
  last, rand = 1, random.random()
  
  # условие прерывания
  while rand > 0.1:
    # отображение отклонения
    print '*',
    # принятие числа
    if abs(last-rand) >= 0.4:
      # update предыдущего числа
      last = rand
      # возврат В ЭТОЙ ТОЧКЕ
      yield rand
      # новый потенциальный элемент
      rand = random.random()
      # возврат последнего малого элемента
      yield rand

Простота этого определения более чем привлекательна. Можно использовать этот генератор вручную, либо в качестве итератора. В первом случае генератор может передаваться в пределах программы и вызываться там, где он нужен, и тогда, когда это требуется (что весьма гибко). Простой пример ниже реализует этот случай:
# Manual use of Random Walk Generator #
gen = randomwalk_generator()
try:
 while 1: print gen.next(),
except StopIteration:
 pass

Однако, скорее всего генератор гораздо чаще будет использоваться в качестве итератора, что более компактно (и выглядит как старая добрая последовательность):
# Random Walk Generator as Interator #
for num in randomwalk_generator():
 print_short(num)

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

В заключение, позвольте мне предложить вашему вниманию еще один пример, который можно найти в модуле test_generators.py дистрибутива Python 2.2. Предположим, у вас есть дерево, по всем узлам которого вы хотите пройти слева направо. Используя традиционные переменные состояния, достаточно сложно немедленно получить класс или функцию. Применение генератора делает выполнение этой задачи до смешного простым:
>>>> # A recursive generator that generates
 # Tree leaves in in-order.
>>> def inorder(t):
... if t:
... for x in inorder(t.left):
... yield x
... yield t.label
... for x in inorder(t.right):
... yield x

Добавлено: 20 Мая 2018 21:56:04 Добавил: Андрей Ковальчук

Программы на python


# Программа для расчета скорости метаболизма и количества необходимых калорий
# для поддержания актуальной массы тела в течении суток, в зависимости от # уровня дневной активности

# Функция для расчета для мужского организма
def man():
try:
weight = int(input("Ваш вес(кг): "))* 13.75
height = int(input("Ваш рост(см): "))* 5
age = int(input("Ваш возраст: "))* 6.76
meta = int(66.47 + weight + height - age)
except ValueError:
print("Ошибка!")
man()
else:
print("Скорость вашего метаболизма равна: " + str(meta))
print("Необходимое колличество каллорий в сутки (в зависимости от физ. активности) состовляет от " + str(int(meta*1.2))+ " до " + str(int(meta*1.9)) + " калорий ")

# Функция для расчета для женского организма
def woman():
try:
weight = int(input("Ваш вес(кг): "))* 9.56
height = int(input("Ваш рост(см): "))* 1.85
age = int(input("Ваш возраст: "))* 4.68
meta = int(655.1 + weight + height - age)
except ValueError:
print("Ошибка!")
woman()
else:
print("Скорость вашего метаболизма равна: " + str(meta))
print("Необходимое колличество каллорий в сутки (в зависимости от физ. активности) состовляет от " + str(int(meta*1.2))+ " до " + str(int(meta*1.9)) + " калорий ")

# Основная функция запуска приложения
def func():
q = input("Какой ваш пол? (м/ж)")
if q == 'м':
man()
elif q == 'ж':
woman()
else:
print("Ошибка!")
func()

func()

Добавлено: 26 Февраля 2016 09:50:07 Добавил: Евгений Лихачев

Решение квадратных уравнений

Решение уравнений вида ax^2+bx+c=0

from math import sqrt      # Импорт функции sqrt из стандартной библиотеки math

def sqr(x):                       # Описываем функцию возведения в квадрат
	sq = x*x
	return sq
 
def findroot(a, b, c):
	D = sqr(b) - 4 * a * c
	if D > 0:
		x1, x2 = ( - b + sqrt(D)) / 2 * a, ( - b - sqrt(D)) / 2 * a
		print("Two roots: ", x1, ", ", x2)
	elif D == 0:
		x = - b / 2 * a
		print("One root: ", x)
	else:
		print("No roots")
 
print("Enter the coefficients a, b and c")
a, b, c = int(input()), int(input()), int(input())
findroot(a, b, c)

Добавлено: 12 Июня 2014 03:32:30 Добавил: Андрей Ковальчук

Конфигуратор для web-разработчиков на Python(+Django), Ruby(+RoR) and PHP.

Основной идей проекта является предоставление средств для быстрого развертывания проектов на локальной машине разработчика(боевые сервера не исключение).

Утилита позволяет организовать настройку виртуальных хостов apache/nginx с учётом настроек для php, python и django, конфигурирование DNS-зон, управление пользователями FTP, создание БД и пользователей в MySQL, генерацию SSL-сертификатов, шифрование директорий и т.п.

Для Apache существует поддержка оптимизации статики с использованием директив mod_headers и mod_expires, а также возможность организации защиты через генерацию пользовательских сертификатов.

Есть возможность установить конфигурацию Nginx для проксирования запросов к Apache. С помощью Git реализован deploy. Проект ориентирован на пользователей, использующих дистрибутивы на основе Debian.

Git репозиторий проекта: https://github.com/gotlium/ahc

От установки к примерам:

Установка пакета:

Код:

$ sudo -i
 # apt-get install -y python-pip python-mysqldb python-pycurl python-flup
 # cd /usr/src/ && git clone https://github.com/gotlium/ahc.git
 # cd ahc/ && pip install -r requirements.txt && make install
 # cd && ahc -m install -s lamp

Файл конфигурации /etc/ahc.conf

Быстрый старт

Хост для веб-сервера Apache:

Код:
# ahc -m install -s apache2_ssl
# ahc -m test -s apache
# ahc -m apache -t php -a example.com

Хост для веб-сервера Nginx:

Код:
# ahc -m install -s nginx_ssl
# ahc -m test -s nginx
# ahc -m nginx -t php -a example.com

FTP пользователи:

Код:
# ahc -m install -s ftp
# ahc -m test -s ftp
# ahc -m ftp -a example.com -u User -p Password

MySQL пользователи:

Код:
# ahc -m install -s mysql
# ahc -m test -s mysql
# ahc -m mysql -a example.com -u User -p Password

Bind зоны:

Код:
# ahc -m install -s bind
# ahc -m test -s bind
# ahc -m bind -a example.com -i 127.0.0.1

Шифрование директории проекта на локальной машине:

Код:
# ahc -m crypt -a mount
# ahc -m crypt -a umount

Более детально можно посмотреть в [URL=https://github.com/gotlium/ahc/blob/master/README.RUS]README[/URL] пакета.

Добавлено: 17 Сентября 2013 03:30:58 Добавил: Андрей Ковальчук

Функция main() для Python

Перевод статьи Гвидо ван Россума, рассказывающей о том, как следует оформлять функцию main().

Хочу предложить программистам функцию main(), которую удобно использовать в различном контексте. Например в интерактивном режиме Python, когда вам хочется поэкспериментировать.

В свое время, я определял функцию main() различным образом. Приблизительно так:

"""Описание модуля.

Подробное описание использования.
"""
import sys
import getopt

def main():
    # Разбираем аргументы командной строки
    try:
        opts, args = getopt.getopt(sys.argv[1:], "h", ["help"])
    except getopt.error, msg:
        print msg
        print "для справки используйте --help"
        sys.exit(2)
    # process options
    for o, a in opts:
        if o in ("-h", "--help"):
            print __doc__
            sys.exit(0)
    # Анализируем
    for arg in args:
        process(arg) # process() определен в другом месте

if __name__ == "__main__":
    main()

Я уверен, что многие пишут нечто подобное main() функции. Несколько предложений, которые сделают эту функцию более гибкой. Тем более, что синтаксический анализ опций становится все более сложным.

Во первых, добавим дополнительный аргумент argv. Так, чтобы можно было вызывать функцию в интерактивном режиме:
def main(argv=None):
    if argv is None:
        argv = sys.argv
        # и т.д. заменяя sys.argv на argv в getopt запросах

Обратите внимание, что мы заполняем значения по умолчанию динамически. Это более гибко, чем:
def main(argv=sys.argv):
    # и т.д.

Таким образом теперь мы можем изменить параметры вызова в любой момент времени.

Вызов sys.exit() закрывает сессию интерпретатора. Доработаем программу:
if __name__ == "__main__":
    sys.exit(main())

Вызов sys.exit(main()) вернет результат функции.

Другое усовершенствование касается использования исключения Usage(), которое мы перехватываем в main:
import sys
import getopt

class Usage(Exception):
    def __init__(self, msg):
        self.msg = msg

def main(argv=None):
    if argv is None:
        argv = sys.argv
    try:
        try:
            opts, args = getopt.getopt(argv[1:], "h", ["help"])
        except getopt.error, msg:
             raise Usage(msg)
        # more code, unchanged
    except Usage, err:
        print >>sys.stderr, err.msg
        print >>sys.stderr, "for help use --help"
        return 2

if __name__ == "__main__":
    sys.exit(main())

Теперь мы имеем единственную точку выхода из функции, что предпочтительнее множественных return 2. Это также облегчает повторный анализ параметров: raise Usage вызывается просто во вспомогательной функции.

Вы можете возразить, что можно перенести конструкцию try/except из main() в конец модуля (if __name__ == "__main__": ...). Но это привело бы к возникновению ошибки при вызове в интерактивном режиме интерпретатора.

Однако, обобщение может быть полезным: определите другое исключение (возможно Error), которое обрабатывается так же, как и Usage, но возвращает 1. Его можно применять для ожидаемых ошибок типа отказа открыть необходимые файлы. Не ситаксические ошибки командной строки, но ожидаемые ситуации. Т.к. traceback не очень дружественное средство в таких случаях.

Добавлено: 17 Сентября 2013 03:27:11 Добавил: Андрей Ковальчук

Получение последнего сообщения из Twitter

Пишем сейчас на Django сайт, где требуется получать последнее сообщение из Twitter аккаунта корпоративного микроблога.

Небольшие отличия есть, а именно — мы получаем данные из Twitter API в формате JSON (используется библиотека [URL=http://pypi.python.org/pypi/simplejson/]simplejson[/URL]), а не в XML, как это было в PHP версии. Можно без проблем использовать и XML, просто с JSON мне удобнее работать.

Аналогично реализовано кеширование твитта в локальный файл и обновление через определенный промежуток времени.

Код, вся дополнительная информация в комментариях:

from django.conf import settings
from time import time
import urllib, os, simplejson

class Twitter:
  """
  Скачиваем последнее сообщение из Twitter пользователя.
  
  Требуется:
  - библиотека simplejson (http://pypi.python.org/pypi/simplejson/)
  - библиотека urllib
  - библиотека os
  - метод time.time()
  
  Необходимо в settings.py добавить переменные:
  
  TWITTER_ACCOUNT = 'Skaizer' # Логин пользователя, чью ленту будем читать.
  TWITTER_CACHE_PERIOD = 3600 # Частота обновления кеша в миллисекундах, когда 0, кеш игнорируется.
  TWITTER_CACHE_FILE = 'last_twitt.txt'; # Имя файла, куда будем дампить кеш. Строится путь относительно MEDIA_ROOT.
  
  """
  def __init__(self):
    self.twitt_file = getattr(settings,'MEDIA_ROOT','./') + getattr(settings,'TWITTER_CACHE_FILE','last_twitt.txt')
    self.cache_period = getattr(settings,'TWITTER_CACHE_PERIOD',0)
    self.username = getattr(settings,'TWITTER_ACCOUNT',None)
    
  def returnLastTwitt(self):
    """
    Возвращаем кеш, если он имеется, и по времени существует не менее установленного в конфигах периода.
    Иначе возвращаем сообщение из инета.
    """
    if self.cache_period !=0:
      if os.path.exists(self.twitt_file):
        if self.cache_period > self.getCacheDateDiff():
          return self.getLastFromCache()
    return self.getLastFromWeb()
    
  def getLastFromWeb(self):
    """
    Скачивает твиттер ленту в Интернет и выбирает последнее сообщение
    """
    feed = 'http://twitter.com/statuses/user_timeline/' + self.username + '.json';
    feed_obj  = simplejson.loads(urllib.urlopen(feed).read())
    last_twitt = feed_obj[0]['text']
    self.cache_twitt(last_twitt.encode("utf_8"))
    return last_twitt
    
  def cache_twitt(self, msg):
    """
    Записывает последний твитт в локальный файл
    """
    handle = open(self.twitt_file,'w')
    handle.write(msg)
    handle.close()
    
  def getCacheDateDiff(self):
    """
    Считает, как давно был создан файл кеша в миллисекундах.
    """
    diff = float(time()) - float(os.path.getmtime(self.twitt_file))
    return diff
    
  def getLastFromCache(self):
    """
    Возвращает закешированное сообщение из файла.
    """
    handle = open(self.twitt_file,'r')
    cached_twitt = handle.read()
    handle.close()
    return cached_twitt
    
  def getLast(self):
    if not self.username:
      return False
    return self.returnLastTwitt()

Вот так класс используется:
def last_twitt():
    t = Twitter()
    return {
      'last_twitt' : t.getLast(),
    }

Все просто, без заморочек, пользуйтесь на здоровье.

Добавлено: 17 Сентября 2013 03:24:54 Добавил: Андрей Ковальчук

Сравнение значений в шаблонах Django

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

{% if some_val > 4 %}
<p>Истина</p>
{% else %}
<p>Ложь</p>
{% endif %}

вызывают ошибку.

В поисках решения я нагуглил библиотеку, разработанную Джеймсом Беннеттом (James Bennett) — [URL=http://django-template-utils.googlecode.com/]django-template-utils[/URL].


Для использования достаточно добавить библиотеку в Python окружение, можно посредством установки:
tar zxvf template_utils-0.4p2.tar.gz
cd template_utils-0.4p2
python setup.py install

А можно просто добавить приложение в INSTALLED_APPS проекта.

В результате вам будут доступны функции сравнения значений, и другие полезные возможности в шаблонах Django.

Например проверка значения на условие «меньше или равно 4х»:
{% load comparison %}
{% if_less_or_equal some_val 4 %}
<p>Истина</p>
{% else %}
<p>Ложь</p>
{% endif_less_or_equal %}

Ссылка на библиотеку: [URL=http://django-template-utils.googlecode.com/]django-template-utils.googlecode.com[/URL].

Добавлено: 17 Сентября 2013 03:22:18 Добавил: Андрей Ковальчук

Автоматический ресайз загружаемых изображений

На данный момент мы занимаемся разработкой городской социальной сети. Не «убийцы» Вконтакте и Одноклассников, ее задачи будут в корне иными. В качестве программной основы был выбран Django, написанный на языке Python.

Разрабатывая интерфейс управления личной информацией необходимо было решить задачу: при загрузке пользователем собственной фотографии, ее размер должен быть не более некоторых значений, определенных настройками системы, если фото больше, то необходимо произвести ресайз с сохранением пропорций.

В этой статья я представлю наше решение поставленной задачи. Возможно, оно окажется не оптимальным, поэтому с удовольствием выслушаю ваши комментарии!


Django, ресайз изображений


Функция ресайза изображения. Автоматически изменяет размер, сохраняя пропорции:
def imageResize(data, output_size):
  """
  Resize image for thumbnails and preview
  data — image for resize
  output_size — turple, contains width and height of output image, for example (200, 500)
  """

  from PIL import Image

  image = Image.open(data)
  m_width = float(output_size[0])
  m_height = float(output_size[1])
  if image.mode not in ('L', 'RGB'):
    image = image.convert('RGB')
  w_k = image.size[0]/m_width
  h_k = image.size[1]/m_height
  if output_size < image.size:
    if w_k > h_k:
      new_size = (m_width, image.size[1]/w_k)
    else:
      new_size = (image.size[0]/h_k, m_height)
  else:
    new_size = image.size
  return image.resize(new_size,Image.ANTIALIAS)

Например, при максимально возможных размерах изображения 200×500 px, загружая изображения на 1024×768 px, новые изображения будут — 200×150 px.

Далее перекрываем стандартный джанговский models.ImageField, расширяя метод save_form_data, в котором и будем производить ресайз:
class AvatarImageField(models.ImageField):
  def save_form_data(self, instance, data):
    from StringIO import StringIO
    from django.core.files.uploadedfile import SimpleUploadedFile, UploadedFile

    if data and isinstance(data, UploadedFile):
      image = imageResize(data, settings.AVATAR_SIZE)
      new_image = StringIO()
      image.save(new_image, 'JPEG', quality=85)
      data = SimpleUploadedFile(data.name, new_image.getvalue(), data.content_type)

      # Удаление старого файла
      previous = u'%s%s' % (settings.MEDIA_ROOT, instance.avatar)
      if os.path.isfile(previous):
        os.remove(previous)
      # -
    super(AvatarImageField, self).save_form_data(instance, data)

Определяем функцию, которая будет возвращать путь к директории сохранения файла, а так же имя файла. Она будет возвращать нужный путь для upload_to файлового поля. В нашем случае имя файла генерируется некоторой хэш-функцией:
  def make_upload_path(instance, filename, prefix = False):
    # Переопределение имени загружаемого файла.
    from utils.hashfunc import get_hash

    filename = 'a_' + get_hash('md5') + '.jpg'
    return u"%s/%s" % (settings.AVATAR_UPLOAD_DIR, filename)

И, собственно, сама модель данных, поле avatar определяется нашим перекрытым классом AvatarImageField, следовательно, наследует всю его функциональность:
class Avatars(models.Model):
  user = models.ForeignKey(User, unique=True)
  avatar = AvatarImageField(
    upload_to=make_upload_path,
    null = False,
    blank = False,
    )

Готово. Теперь все загружаемые изображение, превышающие определенные в системе размеры будут ресайзиться, сохраняя пропорции.

С удовольствием готов ответить на вопросы, а так же выслушать конструктивную критику этого метода!

Добавлено: 17 Сентября 2013 03:20:09 Добавил: Андрей Ковальчук

Парсинг на Python или как скачать обои в большом разрешении

В сегодняшней заметки мы с вами получим порядка 1500+ в высоком разрешении, позаимствовав из с некоторого сайта путем парсинга html страниц.

Немного поковырялся я в Python (больно понравился мне его синтаксис) и чтобы закрепить полученные начальные знания решил на нем небольшую прикладную задачку, которая сводится к взятию с сайта b000.ru всех картинок. Чуть ниже исходный код:

# -*- coding: utf-8 -*-
''' 
image parser 
(C) vredniy
vredniy.ru
'''
from urllib2 import Request, urlopen, URLError, HTTPError
from urllib import urlretrieve
import os
import sys
import re
import time

def doRoutine(url):
     req = Request(url)
     try: response = urlopen(req)

except HTTPError, e:
     print e.code
     return 0
except URLError, e:
     print e.reason
     return 0
else:
     print url
     data = response.read()

m = re.search('<div id="image_list">[\w\W]*?<h1>(.*?)</h1>[\W\w]+?<a href="(.+?)"><img[\w\W]*?alt="(.*?)"', data, re.IGNORECASE & re.UNICODE);
if m:
     downloadImage(m.group(2), m.group(3))


def downloadImage(imageUrl, imageName):
     urlretrieve(imageUrl, './images/' + imageName + '.jpg')
     print imageName + ' скачано'

def main(url):
     counter = 1
     while (counter < 1900):
     counter = counter + 1
     doRoutine("%s%d" % (url, counter))

if __name__ == "__main__":
url = 'http://b000.ru/view/'
main(url)

И в папочке images сохраняются все обои, правда занимает это продолжительное время

Добавлено: 15 Сентября 2013 04:17:41 Добавил: Андрей Ковальчук

Примеры реализации сортировки пузырьком

Ассемблер
Синтаксис Intel

    mov bx, offset array
    mov cx, n
for_i:
    dec cx
    xor dx, dx
for_j:
    cmp dx, cx
    jae exit_for_j
    jbe no_swap
    mov ah, byte ptr bx[di]
    mov byte ptr bx[di], al
    mov byte ptr bx[si], ah
no_swap:
    inc dx
    jmp for_j
exit_for_j:
    loop    for_i


Синтаксис AT&T (GNU)

.text
# void bubble_sort (unsigned *array, unsigned length);
.globl bubble_sort
    .type   bubble_sort, @function
bubble_sort:
    mov 8(%esp), %ecx # unsigned length
    cmp $1, %ecx
    jbe exit
    mov 4(%esp), %eax # unsigned *array
    dec %ecx
for_ecx:
    xor %edi, %edi
for_edi:
    mov (%eax,%edi,4), %ebx
    cmp %ebx, 4(%eax,%edi,4)
    jae  no_xchng
    mov 4(%eax,%edi,4), %edx
    mov %edx, (%eax,%edi,4)
    mov %ebx, 4(%eax,%edi,4)
no_xchng:
    inc %edi
    cmp %edi, %ecx
    jne for_edi
    loop for_ecx
exit:
    ret


C

#define SWAP(A, B) { int t = A; A = B; B = t; }
 
void bubblesort(int *a, int n)
{
  int i, j;
 
  for (i = n - 1; i > 0; i--)
  {
    for (j = 0; j < i; j++)
    {
      if (a[j] > a[j + 1]) 
        SWAP( a[j], a[j + 1] );
    }
  }
}


C++
С использованием Template

#include <algorithm>
template< typename Iterator >
void bubble_sort( Iterator First, Iterator Last )
{
    while( First < --Last )
        for( Iterator i = First; i < Last; ++i )
            if ( *(i + 1) < *i )
                std::iter_swap( i, i + 1 );
}

Без использования Template

void bubble(int*a, int n)
{
for (int i=n-1;i>0;i--)
  {
    for (int j=0;j<i;j++)
      {
        if(a[j]>a[j+1])
          {
            int tmp=a[j];
            a[j]=a[j+1];
            a[j+1]=tmp;
          }
     }
  }
}


C#

void BubbleSort(ref int[] A)
{
   int temp;
 
   for(int i = 0; i < A.Length - 1; i++)
   {
      for(int j = 0; j < A.Length - i - 1; j++)
      {
         if(A[j] > A[j + 1])
         {
            temp = A[j];
            A[j]=A[j+1];
            A[j + 1] = temp;
         }
      }
   }
}


Delphi

Сортировка одномерного динамического целочисленного массива:

type
 TIntVec = array of Integer;
...
procedure BubbleSort(var a: TIntVec);
 var i,p,n: Integer; b: boolean;
begin
 n:= Length(a);
 if n < 2 then exit;
 repeat
  b:= false;
  Dec(n);
  for i:= 0 to n-1 do
   if a[i] > a[i+1] then
    begin
     p:= a[i];
     a[i]:= a[i+1];
     a[i+1]:= p;
     b:= true;
    end;
 until not b;
end;


D

void bubbleSort(alias op, T)(T[] inArray) {
    foreach (i, ref a; inArray) {
        foreach (ref b; inArray[i+1..$]) {
            if (mixin(op)) {
                auto tmp = a;
                a = b;
                b = tmp;
            }
        }
    }
}


Fortran

do i=n-1,1,-1
do j=1,i
    if (a(j).gt.a(j+1)) then
        t=a(j)
        a(j)=a(j+1)
        a(j+1)=t
    endif
enddo
enddo


Java

void swap(int[] arr, int i, int j) {
    int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
}
 
void bubblesort(int[] arr){
    for(int i = arr.length-1 ; i > 0 ; i--){
        for(int j = 0 ; j < i ; j++){
            if( arr[j] > arr[j+1] )
               swap(arr, j, j+1);
        }
    }
}


Pascal

for i:=n-1 downto 1 do {n - размер массива M[]}
    for j:=1 to i do
        if M[j]>M[j+1] then 
            begin
               tmp:= M[j];
               M[j]:= M[j+1];
               M[j+1]:= tmp;
            end;
write('вывод значений M[]: ');
for i:=1 to n do
    write(M[i]:4);
writeln;

Усовершенствованный алгоритм сортировки пузырьком:

P:=True; {есть перестановка?}
K:=1; {Номер просмотра}
While P Do
Begin
    P:=false;
    For i:=1 To n-k Do
        If X[i] > X[i+1] Then
        Begin
            A:=X[i];
            X[i]:=X[i+1];
            X[i+1]:=A;
            P:=true;
        End;
    k:=k+1;
End;


Perl

for(@out){
  for(0..$N-1){
    if($out[$_]gt$out[$_+1]){
      ($out[$_],$out[$_+1])=($out[$_+1],$out[$_]);
    }
  }
}


Ruby

arr = [5, 20, 3, 11, 1, 17, 3, 12, 8, 10]
swap = true
size = arr.length - 1
while swap
  swap = false
  for i in 0...size
    swap |= arr[i] > arr[i + 1]
    arr[i], arr[i+1] = arr[i + 1], arr[i] if arr[i] > arr[i + 1]
  end
  size -= 1
end
puts arr.join(' ')
# output => 1 3 3 5 8 10 11 12 17 20


Python

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]
 
def bubble_sort(arr):
    i = len(arr)
    while i > 1:
       for j in xrange(i - 1):
           if arr[j] > arr[j + 1]:
               swap(arr, j, j + 1)
       i -= 1

VBA

Sub Sort(Mus() As Long)
Dim i As Long, tmp As Long, t As Boolean
t = True
Do While t
    t = False
    For i = 0 To UBound(Mus()) - 1
        If Mus(i) > Mus(i + 1) Then
            tmp = Mus(i)
            Mus(i) = Mus(i + 1)
            Mus(i + 1) = tmp
            t = True
        End If
    Next
Loop
End Sub


PHP

$size = sizeof($arr)-1;
for ($i = $size; $i>=0; $i--) {
    for ($j = 0; $j<=($i-1); $j++)
        if ($arr[$j]>$arr[$j+1]) {
            $k = $arr[$j];
            $arr[$j] = $arr[$j+1];
            $arr[$j+1] = $k;
        }
}

JavaScript

function sortBubble(data) {
    var tmp;
 
    for (var i = data.length - 1; i > 0; i--) {
        for (var j = 0; j < i; j++) {
            if (data[j] > data[j+1]) {
                tmp = data[j];
                data[j] = data[j+1];
                data[j+1] = tmp;
            }
        }
    }
    return data;
}


JavaFX

function bubbleSort(seq:Number[]):Number[]{
 
    var sort = seq;
    var elem:Number;
 
    for(n in reverse [0..sizeof seq - 2]){
        for(i in [0..n] ){
            if(sort[i+1] < sort[i] ){
                elem = sort[i];
                sort[i] = sort[i+1];
                sort[i+1] = elem;
            }
        }
    }
 
    return sort;
}

Nemerle

using System.Console;
using Nemerle.Collections;
 
def arr = array [100, 45, 2, 5, 3, 122, 3, 5, 6, 1, 3];
 
foreach (i in [0..arr.Length-1])
    foreach (j in [0..arr.Length-2])
       when (arr[j] > arr[j+1])
           (arr[j], arr[j+1]) = (arr[j+1], arr[j]);
 
WriteLine($"Sorted list is a $(arr.ToList())");


TurboBasic 1.1

CLS
RANDOMIZE TIMER
DEFINT X, Y, N, I, J, D
N = 10 ' 32 766 - 62.7 SEC
DIM Y[N], Y1[N], Y2[N], Y3[N], Y4[N] 'FRE(-1)=21440-21456
 
PRINT " ZAPOLNENIE MASSIVA ELEMENTAMI"
 
FOR X = 1 TO N
   Y[X] = X
   PRINT Y[X];
NEXT X:PRINT
 
PRINT " PEREMESHIVANIJE ELEMENTOV MASSIVA"
 
PRINT " SLUCHAINYE CHISLA"
 
FOR X = 1 TO N
   YD=Y[X]
   XS=INT(RND*N)+1
   PRINT XS;
   Y[X]=Y[XS]
   Y[XS]=YD
NEXT X:PRINT
 
PRINT " PEREMESHANNYJ MASSIV"
 
FOR X=1 TO N
   PRINT Y[X];
NEXT X:PRINT
 
'ALGORITM "SORTIROVKA PROSTYM OBMENOM" O(N^2)
MTIMER
FOR J=1 TO N-1 STEP 1
   F=0
   FOR I=1 TO N-J STEP 1
      'IF Y[I] > Y[I+1] THEN D=Y[I]:Y[I]=Y[I+1]:Y[I+1]=D:F=1
      IF Y[I] > Y[I+1] THEN SWAP Y[I],Y[I+1]:F=1
 
      LOCATE 8,1                    REM
      PRINT " ANYMACIJA SORTIROVKI" REM
      FOR X1=1 TO N                 REM ANIMATION BLOCK
         PRINT Y[X1];               REM
      NEXT X1:PRINT                 REM
      DELAY .5                      REM
 
   NEXT I
   IF F=0 THEN EXIT FOR
NEXT J
T1=MTIMER
 
PRINT " OTSORTIROVANNYJ MASSIV"
 
FOR X=1 TO N
   PRINT Y[X];
NEXT X:PRINT
PRINT "ELAPSED TIME=";T1

Добавлено: 15 Августа 2013 01:39:23 Добавил: Андрей Ковальчук