Архив рубрики: Python

Алгоритм Кнута-Морриса-Пратта (КМП)

Алгоритм был разработан Кнутом (Knuth) и Праттом (Pratt) и независимо от них Моррисом (Morris) в 1977 г.

Он относится к «правильным» подходам решения поставленной задачи, в отличии от тривиального подхода, рассмотренного ранее.

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

Однако я нашел пару статей, которые достаточно информативны, они приведены в ссылках и рекомендуемы для ознакомления.

Читать

Использование try-finally

Хочу обратить внимание на маленькую особенность написания конструкции try-finally.

Возьмём для примера многопоточность, а конкретно блокировки.

Где-то (наверное, в конструкторе класса) мы создали объект блокировки:

self.locker = threading.RLock()

Затем в каком-то методе мы пытаемся использовать эту блокировку в try-finally statement. Да, я знаю что RLock поддерживает context manager protocol и может использоваться в with statement. Так будет даже лучше, но мы сейчас говорим о другом варианте использования.

try:
self.locker.acquire()
do_some_work()
finally:
self.locker.release()

В чём ошибка? .acquire() может выбросить исключение. Блокировка не будет захвачена и попытка её освободить в .release() выбросит новое (другое) исключение. Что крайне нежелательно. Особенно в python 2.x, где нет цепочек исключений. Т.е. ошибка в .acquire() будет просто скрыта, понять в чём было дело невозможно.

Правильно писать так:

self.locker.acquire()
try:
do_some_work()
finally:
self.locker.release()

Если было исключение в .acquire() — то блокировка не захвачена и освобождать её не нужно. Пусть обработка исключения разворачивается своим ходом, .release() в finally block совершенно не нужен.

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

Проблема усугубляется тем, что обычно .acquire() работает успешно, и лишь в редких случаях выбрасывает исключение. Которое мы видим в логах (все используют логи, верно?) и недоумеваем, что именно произошло.

Это замечание относится к любому коду, выполняемому в finally block.

Переменные, блокировки, захват ресурсов, открытие файлов и т.д. должны быть выполнены перед try.

P.S.

На открытие файлов хочу обратить особое внимание как на самый частый случай. Куда более частый чем работа с многопоточностью. Правильно писать:

f = open('filename')
try:
f.read()
finally:
f.close()

Надеюсь, последний пример запомнится хорошо и внесёт ясность в головы уважаемых молодых коллег.

Автор: Andrew Svetlov

South. Документация. Конвертирование приложения

Конвертирование приложения

Конвертировать приложение для  использования South очень легко:
  • Отредактируйте ваш settings.py и укажите south в INSTALLED_APPS (мы предполагаем, что Вы установили south туда, куда нужно)
  • Запустите ./manage.py syncdb для того, чтобы загрузить таблицу South в БД. Обратите внимание, что теперь syncdb не такой как раньше — South его изменил
  • Запустите ./manage.py convert_to_south myapp — South автоматически подготовит и выполнит первую миграцию
Обратите внимание, что Вы должны конвертировать приложение до того, как Вы сделаете изменения; South обнаруживает изменения по сравнению с замороженным состоянием последней миграции, так что он не сможет обнаружить изменения, сделанные до конвертирования в South.

Конвертирование других установок и серверов

Команда convert_to_south рабоатет целиком на первой машине, на которой Вы его запустите. После того, как Вы подтвердите начальную миграцию, которую он сделал, в системе управления версиями, Вы должны запустить ./manage.py migrate myapp 0001 —fake на всех машинах, которые содержат копию кода (убедитесь, что они имеют обновлённый код и схему).
(Для тех, кому интересно, это нужно поскольку начальная миграция, которую делает convert_to_south, проверит и создат все существующие таблицы; вместо этого Вы говорите South, что это уже сделано при помощи —fake, так что следующие миграции будут применены корректно).
Помните, что новые установки кода после этого не потребуют этих шагов, Вам нужно будет лишь сделать syncdb а, затем, провести нормальную миграцию.

Автор: Ishayahu Lastov

Документация South — Перевод. Часть 4: Пользовательские поля

В South 0.7 появилось радикальное отличие от предыдущих версий. До сих пор, если у Вас было пользовательское поле, South пытался использовать очень сильное колдунство для того, чтобы определить, как «замораживать» это поле,так что оно могло быть отклонено в миграции (и это было не очень красивое колдунство — комбинация регулярных выражений и модуля parser).
Хотя это, как ни странно, работало хорошо у большинства пользователей, тем не менее в некоторых случаях что-то шло не так, и Вы даже не знали об этом, пока не проходило несколько недель… В целях большей вменяемости и меньшей магии теперь Вы должны указать South как замораживать ваши пользовательские поля.
Не волнуйтесь, это достаточно просто и Вам надо сделать это лишь раз для каждого поля.

Наше поле

В этом примере мы будем использовать пользовательское поле, которое хранит список тегов в БД. Мы будем просто хранить их в TEXT колонке с некоторым разделителем (по умолчанию мы будем использовать |, но можно использовать и любой другой символ — просто передайте его как именованный аргумент).
Вот класс этого поля. Я разместил его в appname/fields.py (более подробно о создании собственных полей смотрите документацию Django):
 from django.db import models

class TagField(models.TextField):

description = "Stores tags in a single database column."

__metaclass__ = models.SubfieldBase

def __init__(self, delimiter="|", *args, **kwargs):
self.delimiter = delimiter
super(TagField, self).__init__(*args, **kwargs)

def to_python(self, value):
# If it's already a list, leave it
if isinstance(value, list):
return value

# Otherwise, split by delimiter
return value.split(self.delimiter)

def get_prep_value(self, value):
return self.delimiter.join(value)
Для того, чтобы рассказать South об этом поле, Вам нужно сообщить две вещи: что этот класс можно использовать и как получить именованный аргумент из экземпляра поля.

Именованные аргументы

South замораживает поля сохраняя их имя класса и модуль (таким образом можно получить сам класс поля) и именованные аргументы, которые Вы используете для конкретного экземпляра класса (например, CharField(max_lengh=50) не то же самое, что CharField(max_lengh=150)).
Так как Python не хранит именованные аргументы, переданные конструктору класса, South должен восстановить их уже из полученного экземпляра класса. Например, мы знаем что значение именованного аргумента max_length класса CharField хранится в атрибуте self.max_lenght, тогда как ForeignKeys хранят свои именованные аргументы to (определяющие модель, на которую они указывают, так же первый позиционный аргумент) как self.rel.to.
South знает все эти правила для стандартных полей Django, но Вам необходимо объяснить все это касательно своих полей. Хорошая новость состоит в том, что South может отследить цепочку наследования, так что о полях, определённых в родительских классах говорить заново в дочерних классах не надо (или надо сообщить только о тех дополнительных именованных аргументах, которых не было в родительском классе).
В нашем примере мы определяем только один дополнительный именованный аргумент — delimiter. Вот код, который мы добавляем для того, чтобы South мог обработать наше новое поле. Чуть позже мы его объясним:

 from south.modelsinspector import add_introspection_rules
add_introspection_rules([
(
[TagField], # Класс(ы) к которым это применимо
[], # позиционные аргументы (не используется)
{ # именованные аргументы
"delimiter": ["delimiter", {"default": "|"}],
},
),
], ["^southtut.fields.TagField"])

Как Вы можете видеть, для того, чтобы рассказать South о вашем новом поле Вам нужно вызвать функцию south.modelsinspector.add_introspection_rules. Вы должны разместить этот код рядом с определением вашего поля. Так как последнее, что Вы хотели бы — это импортировать поле, но чтобы этот код не был выполнен.
add_introspection_rules принимает два аргумента: список правил и список регулярных выражений. Список регулярных выражений используется South для того чтобы понять, можно ли исследовать это поле. Просто иметь правило, которое подходит для поля недостаточно, так как наследование правил подразумевает, что любой пользовательский класс поля будет иметь хотя бы одно правило, под которое он подпадает (
опять — «(as they will inherit from «Field«, if not something more specificlike «CharField«), and some custom fields can get by with only those inherited rules (more on that shortly)«).
Первый аргумент — список правил. Каждое правило — это кортеж (или список) с тремя элементами:

  1. Список классов к которым применимы эти правила. Практически наверняка у Вас будет тут только одно поле, например, то, про которое мы сейчас говорим.
  2. Спецификация позиционных аргументов. Практически наверняка будет пустым списком — []
  3. Спецификация именованных аргументов: это словарь, где ключ — имя аргумента, а значение — список или кортеж (имя_аргумента, опции)
Имя аргумента определяет место, где может быть найдено значение именованного аргумента — в нашем случае это delimiter, так как значение именованного аргумента мы храним в self.delimiter. (Если бы это было правило ForeignKey, то тут бы стояло rel.to)
Опции- это словарь. Вы можете безопасно оставить этот аргумент пустым, но можно и использовать его для определения значения по умолчанию и если South обнаружит значение, соответствующее этому, то он не будет указывать это ключевое слово в определении заморозки, что позволит это определение сделать более простым и читаемым.

Простые наследования

Если ваше поле наследуется напрямую из другого поля Django, например, CharField, и не добавляет других именованных аргументов, то Вам не нужно добавлять какие-либо правила в add_introspection_rules. Вы можете просто сказать South, что с этим полем всё в порядке:
 class UpperCaseField(models.TextField):
"Убеждаемся, что содержимое всегда в верхнем регистре."

def to_python(self, value):
return value.upper()

def get_prep_value(self, value):
return value.upper()

from south.modelsinspector import add_introspection_rules
add_introspection_rules([], ["^southtut.fields.UpperCaseField"])

Больше информации

Более подробную документацию на эту тему можно обнаружить в разделе Extending introspection.

Автор: Ishayahu Lastov

MoinMoin2. Документация. Загрузка и установка

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

 Загрузка

Для moin2 пакеты пока не доступны, так что Вы должны получить его из репозитория. Вы можете использовать один или два URLa репозиториев и либо использовать Mercurial для поддержки кода в актуальном состоянии, или же скачать файлы в архие tar.gz:
  • Использование Mercurial для клонирования одного из репозиториев:
    hg clone http://hg.moinmo.in/moin/2.0 moin-2.0
    или
    hg clone http://bitbucket.org/thomaswaldmann/moin-2.0 moin-2.0
    после этого убедитесь, что ваша рабочая директория использует ветку default:
    cd moin-2.0
    hg up -C default
  • В качестве альтернативы посетите http://hg.moinmo.in/moin/2.0 и скачайте архив (обычно, для ветки default) и распакуйте его

Установка

Перед тем, как Вы запустите moin, Вы должны его установить:

Установка разработчика

Использование стандартной установки Python или каталога  virtualenv

Пожалуйста, убедитесь, что у Вас установлен virtualenv, который включает в себя pip.

Если вы всего лишь хотите запускать moin из рабочего каталога mercurial со стандартной установкой Python, выполните следующую комманду в этом каталоге. Вы не должны выполнять её как администратор машины, используйте стандартный аккаунт пользователя:
./quickinstall # для Linux и других POSIX OS
# или
quickinstall.bat # для Windows
На FreeBSD 9.1 bash не установлен по умолчанию, а он нужен для работы этого скрипта. Так что сперва Вам нужно установить bash:
cd /usr/ports/shells/bash/ && make install clean
после чего надо будет отредактировать первую строку скрипта, указав путь к bash:
#!/usr/local/bin/bash
Эта команда использует virtualenv для создания каталога env/ в текущем рабочем каталоге, создаёт виртуальное окружение для MoinMoin и затем устанавливает moin2 со всеми зависимостями в этот каталог. pip автоматически скачает все зависимости из PyPI и установит их, так что это может занять некоторое время. Кроме того, будут скомпилированы все переводы (файлы *.po) в бинарные файлы *.mo.
Просмотрите вывод скрипта quickinstall  и проверьте отсутствие ошибок.
Если у Вас плохое подключение к сети из-за чего скачивание прерывается, Вы можете попробовать выполнить шаги из quickinstall вручную.
Кроме того, quickinstall создаст скрипт moin для вашей платформы, который Вы сможете использовать для запуска встроенного сервера или команды moin.
После того, как Вы активируете виртуальное окружение (sourcer bin/activate выполненый в bash), встроенный серверный скрипт с именем moin будет находиться в вашем стандартном пути, так что Вы можете просто запустить команду moin из вашей командной строки.
Примечание: в этом специальном режиме MoinMoin код не будет скопирован в каталог env/, всё будет запускаться из вашей рабочей директории, так что Вы можете напрямую править код и смотреть, что получается. Процедуру установки надо выполнить только один раз.

Использование другого Python или другого каталога virtualenv

Например, если Вы хотите использовать PyPy и хотите, чтобы каталог для virtualenv назывался env-pypy, выполните команду:
# для Linux
DIR=env-pypy
PYTHON=/opt/pypy/bin/pypy
Таким образом, Вы можете проверить разные версии Python в разных каталогах вашего рабочего каталога.

Активирование виртуального окружения

ВАЖНО: Вы всегда должны активировать ваше виртуальное окружение перед запуском чего-либо, что будет выполнять код moin! Иначе не будет найдена ни команда moin, ни код moin, ни необходимые библиотеки. Кроме того, если Вы хотите установить дополнительное ПО в виртуальное окружение, активируйте его перед запуском pip!
source env/bin/activete # для Linux или других POSIX OS
# или
envScriptsactivate.bat # для Windows
После того, как Вы активировали виртуальное окружение, команда moin будет в вашем пути, так что Вы сможете выполнить её.

Помогаем moin найти конфигурацию wiki

moin так же должен обнаружить конфигурацию wiki. Если Вы хотите запустить moin самым простым способом, без передачи параметров команде moin, проще всего это будет сделать из каталога с конфигурационными файлами, т.е. wikiconfig.py.
Если Вы работаете в рабочем каталоге репозитория, то Вам нужен каталог верхнего уровня, где есть уже готовый к использованию wikiconfig.py.
В случае, если Вы хотите указать путь к файлу с конфигурацией, используйте абсолютный путь. moin будет искать конфигурационный файл в таком порядке:
  1. аргумент командной строки —config /path/to/wikiconfig.py
  2. переменная окружения MOINCFG=/path/to/wikiconfig.py
  3. текущий каталог, файл wikiconfig_local.py
  4. текущий каталог, файл wikiconfig.py

 Инициализация индекса и/или хранилища

Если у Вас уже есть хранилищи И индекс (для содержимого этого хранилища и для этой версии moin), Вы можете пропустить этот раздел.
Если Вы начинаете с самого начала, то есть ни хранилища ни индекса ещё не создано, то Вам нужно создать пустое хранилище и пустой индекс:
# создаём хранилище и индекс:
moin index-create -s -i

Загружаем некоторые элемента

Если Вы не хотите получить совсем пустую вики, Вы можете, по желанию, загрузить в хранилище некоторые примеры, например:
moin load —file contrib/serialized/items.moin

Строим индекс

Если у Вас уже есть некоторые элементы в хранилище, но индекса ещё нет, то его нужно построить:
moin index-build

Установка PIL

Для некоторых функций обработки изображений, котоыре использует MoinMoin, например, изменение размера или поворот, Вам нужен PIL — Python Imaging Library.
Пользователи Windows, которые хотят установить PIL должны пропустить этот раздел и перейти к Решение проблем — Установка PIL под Windows.
Если Вы устанавливаете PIL при помощи pip, тогда pip постарается найти библиотеку поддержки jpeg  и ассоциированные заголовки разработки в вашей системе, и если у Вас их нет — то Вы не получите поддержки jpeg в PIL. Так что если Вы хотите обеспечить эту поддержку, убедитесь, что у Вас есть jpeg библиотеки и заголовки:
# установка jpeg библиотеки и заголовков разработки
sudo apt-get install libjpeg62-dev # Ubuntu/Debian
yum install libjpeg-turbo-devel #Fedora/Redhat
cd /usr/ports/graphics/jpeg/ && make install clean # FreeBSD
После этого активируйте виртуальное окружение и установите PIL:
pip install pil

Решение проблем

PyPI не работает

Всегда может быть так, что PyPI окажется недоступен. В этом случае можно использовать зеркала b.pypi.python.org, c.pypi.python.org, d.pypi.python.org. Вам только нужно сказать об этом pip:
# разместите это в ~/.pip/pip.conf
[global]
index-url = http://c.pypi.python.org/simple
В случае, если и это не будет работать, попробуйте mini pypi, где должны быть все необходимые для moin пакеты:
# разместите это в ~/.pip/pip.conf
[global]
index-url = http://pypi.moinmo.in/simple

Проблемы с сетью

Если у Вас плохое или ограниченное подключение к сети, у Вас могут возникнуть проблемы с командами, выполняемыми скриптом quickinstall. Вы можете увидеть трассировку pip, ошибки таймаута и т.д. Обратите внимание на эти сообщения.
В этом случае попробуйте сделать это вручную:
# перейдите в виртуальное окружение:
source env/bin/activate
# убедитесь в проблемах, запустив
pip install -e .
После этого установите каждый пакет в ваше виртуальное окружение вручную:
  •  Найдите все нужные пакеты, перечисленные в install_requires из файла setup.py
  • Загрузите все нужные пакеты из http://pypi.python.org/
  • Установите все эти пакеты:
    pip install package.tar
  • Теперь попробуйте ещё раз:
    pip install -e .

Повторите эти шаги, пока не прекратится появление ошибок.

Установка PIP под Windows

PIL версии 1.1.7 не устанавливается корректно командой pip install pil на Windows. Некоторым пользователям удалось сделать это при помощи pip install pillow, установив форк PIL'a, устранающего эту проблему. Другие установили PIL 1.1.6 в каталог установки Python, скачав его с http://www.pythonware.com/products/pil/

Автор: Ishayahu Lastov

MoinMoin2 документация. Требования

MoinMoin требует Python >= 2.6 и < 3.0. Мы обычно тестируем работу на CPython и рекомендуем использовать его. Кроме того, можно попробовать PyPy >= 1.6

Сервера

Для moin можно использовать любой сервер, совместимый с WSGI:
  • встроенный сервер «moin» рекомендуется для однопользовательских wiki, тестирования, отладки, разработки и т.п.
  • Apache c mod_wsgi рекомендуется для больших/популярных вики
  • Другие WSGI совместимые сервера или middleware
  • Для cgi, fastcgi, ajp и т.д. можно использовать middleware flup
  • IIS со шлюзом ISAPI-WSGI тоже можно использовать

Зависимости

Зависимости перечислены в setup.py.

Если Вы используете easy_install, pip или наш скрипт quickinstall, тогда зависимости должны установиться автоматически.

Клиенты

На стороне клиента Вам нужны:
  • приличный веб-браузер, поддерживающий W3C стандарт HTML 5, CSS 2.1 и JavaScript:
    • Любая текущая версия Firefox, Chrome, Opera, Safari, IE (9/10) должны работать
    • Использование более старых версий IE не рекомендуется и не поддерживается
    • Для Windows 7/8 MS предоставляет IE 9/10
  • Java плагин для браузера (опционально, если Вы хотите использовать TWikiDraw или AnyWikiDraw для рисования аплетов)

Автор: Ishayahu Lastov