Поиск информации — одно из основных использований компьютера. Одна из простейших задач поиска информации — поиск точно заданной подстроки в строке. Тем не менее, эта задача чрезвычайно важна — она применяется в текстовых редакторах, СУБД, поисковых машинах…
Архив метки: 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
Слайды с PyCon RU
Исключения в Питоне
Поговорим об исключениях.
Всё нижеизложенное относится к Python 3.3, хотя отчасти справедливо и для более ранних версий.
Для чего они применяются, наверное, все и так прекрасно знают: для передачи сообщений об ошибках внутри программы.
Рассмотрим простейший пример: открытие файла. Если всё нормально — open(filename, 'r') возвращает объект этого самого файла, с которым можно делать всякие полезные вещи: читать из него данные и т.д. Читать
Зачем в python with
Долгое время при работе с файлами из python я писал примерно следующий код:
def some_func(fname):
fd = open(fname)
some_data_processing(fd.read())
return result
def some_func(fname):
fd = open(fname)
some_data_processing(fd.read())
return result
Тут предполагается, что в любом случае при выходе из функции переменная fd уничтожится и вместе с ней закроется файл и все будут жить долго и счастливо.
Но что будет если в some_data_processing произойдет исключение?
Например так:
import sysclass TestClass(object):
def __del__(self):
print «I’m deleted»
def data_process():
obj = TestClass()
raise IndexError()
try:
data_process()
except:
print «In exception handler»
print «after except»
import sysclass TestClass(object):
def __del__(self):
print «I’m deleted»
def data_process():
obj = TestClass()
raise IndexError()
try:
data_process()
except:
print «In exception handler»
print «after except»
На консоли появляется:
In exception handler
after except
I'm deletedПочему-то «In exception handler» и «after except» выводятся раньше «I’m deleted».
Первая проблема в том, что вместе с исключением питон хранит и трейс стека, содержащий все фреймы вплоть до породившего исключение. А внутри фрейма живет f_locals — словарь локальных переменных, и именно он имеет ссылку на экземпляр класса TestClass. Таким образом до окончания обработки исключения obj будет жить точно. Почему же «after except» появляется раньше чем «I’m deleted»? Было бы логично чистить трейс после успешного выхода из блока try. Дело в том что 2.X питон не всегда чистит внутренние структуры после обработки исключения и в общем случае вы должны явно вызывать функцию sys.exc_clear чтобы очистить их. Когда я подошел с этим вопросом к Larry Hastings (одному из основных разработчиков ядра питона) ему потребовалось около 20ти минут, что-бы понять что происходит и найти в документации sys.exc_clear. (Правда стоит отметить, что он давно использует 3.X, где это поведение стало адекватнее.) В 3.X это поведение улучшили, и теперь sys.exc_clear автоматически вызывается окончанию обработки исключения.
Кстати, если вы напишете примерно такой код:
try:
data_process()
except:
fr = sys.exc_info()[2]
del fr
try:
data_process()
except:
fr = sys.exc_info()[2]
del fr
то не забудьте удалить fr используя del, как в последней строке — иначе он образует циклическую ссылку с текущим фреймом и тогда все станет совсем плохо.
Стоит отметить, что подобное поведение проявляется не всегда. Например сл