Python 3.3 продолжает радовать. Сегодня в него вошли изменения от Bratt Cannon. Теперь import реализован почти весь на питоне, в библиотеке importlib. Она и раньше присутствовала — но теперь __import__ ведёт напрямую в importlib. Читать
Архив рубрики: Python
Быстрая сортировка(quicksort, сортировка Хоара)
Быстрая сортировка (англ. quicksort), часто называемая qsort по имени реализации в стандартной библиотеке языка Си — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром в 1960 году. Один из быстрых известных универсальных алгоритмов сортировки массивов (в среднем O(n log n) обменов при упорядочении n элементов), хотя и имеющий ряд недостатков. Например, в худшем случае (на некоторых входных массивах) использует время Ω(n2)
Функция QuickSort сводит сортировку данного ей массива к разделению (partitioning) этого массива на две группы элементов и сортировке этих двух групп по отдельности.
Пример рекурсивного алгоритма с детерменированным(определённым) выбором оси:
Пусть нам нужно отсортировать участок массива A с p-го по q-й элемент включительно, будем называть этот участок подмассивом и обозначать как A[p..q].
- ШАГ 1: Возьмем элемент A[p] за ось и «раскидаем» остальные элементы A[(p+1)..q] по разные стороны от него стороны — меньшие влево, большие — вправо, то есть переставим элементы подмассива A[p..q] так, чтобы вначале шли элементы меньше либо равные A[p] потом элементы, больше либо равные A[p]. Назовет этот шаг разделением (partition).
- ШАГ 2: Пусть r есть новый индекс элемента A[p]. Тогда, если q — p > 2, вызовем функцию сортировки для подмассивов A[p..(r-1)] и A[(r+1)..q].
Ключевая идея алгоритма заключается в процедуре «partition», которая за линейное время от размера массива, осуществляет такую перестановку элементов, относительно некоторой «оси» — заданного значения, равного одному из значений сортируемого интервала массива, что переставленный массив состоит из трех интервалов, идущих по порядку:
- Элементы меньшие «оси»
- Элементы равные «оси»
- Элемент
Сервис онлайн тестирования Quizful
Недавно в блоге Алена С++ прочитал пост о бесплатном прохождении тестов на сайте Brainbench. Халява была ограниченна по времени, так что я задался вопросом найти бесплатный аналог и на русском. Больше всего мне понравился сайт онлайн тестов Quizful.
Читать
Выражение raise
raise_stmt ::= «raise» [expression [«from» expression]]
В случае отсутствия expression, повторно возбуждается последнее исключение, которое было активно в данной области. Если такого исключения нет, то возбуждается исключение RuntimeError, чтобы сообщить о данной ошибке.
В противном случае raise выполняет первый expression и получает объект исключения. Он должен являться либо подклассом либо экземпляром BaseException. Если первый expression является именем класса, то создается объект путём вызова класса без передачи аргументов. Читать
object.__del__(self) 2.7
Вызывается когда экземпляр должен быть уничтожен (другими словами — это деструктор). Если родительский класс тоже имеет метод __del__(), то производный класс в своём методе __del__(), если он определён, должен явно вызывать метод родительского класса, чтобы гарантированно уничтожить методы родительского класса. Стоит отметить, что возможно (хотя и не рекомендуется) сделать так, чтобы в методе __del__() было отложено уничтожение самого объекта. Это достигается созданием на него другой ссылки перед удалением текущей, и уже при уничтожении последней ссылки надо будет уничтожить сам объект. Гарантии того, что метод __del__() будет вызван для существующих объектов при завершении работы интерпретатора нет.
Заметка
del x не является прямым вызовом x.__del__() — первая форма сокращает количество ссылок на объект x на одну, тогда как последний метод вызывается только когда количество ссылок достигает нуля. В некоторых часто встречающихся случаях могут возникнуть ситуации, мешающие обнулению счётчика, как то:
- взаимные ссылки между объектами (в списках или в деревьях)
- ссылки на объекты в стеке функции, где было вызвано исключение, так как в таком случае ссылки на объекты этого стека сохранены в sys.exc_traceback
- ссылки на объекты в стеке, если было вызвано не перехваченное исключение в интерактивном режиме (так как в таком случае ссылки на объекты сохранены в sys.last_traceback)
В первом случае необходимо явно разрушить циклические ссылки; во втором и третьем — сохранить None в sys.exc_traceback или sys.last_traceback. Циклические ссылки определяются сборщиком мусора, если активирована соответствующая опция (как оно и есть по умолчанию), однако, если вызывается метод __del__() в коде, такие ссылки не будут обработаны автоматически. Обратитесь к документации модуля gc для более подробной информации, особенно к разделу, описывающему значение garbage.
Предупреждение
В связи с неопределёнными обстоятельствами, когда вызывается метод __del__(), исключения, возникающие в процессе выполнения этого метода игнорируются, а предупреждения об этом выводятся в sys.stderr. Кроме того, когда вызывается метод __del__(), относящийся к удалению модуля (например, когда завершено выполнение программы) другие объекты, определённые в этом методе могут быть уже уничтожены или быть в процессе уничтожения (например, когда происходит выключение механизма импортирования). По этой причине метод __del__() должен содержать минимум внешних зависимостей. Начиная с версии 1.5 Python гарантирует, что глобальные имена, начинающиеся с _ удаляются из модуля прежде остальных глобальных имён; поэтому если нет других ссылок на эти переменные, по их наличию можно определить доступность импортированного модуля в процессе вызова метода __del__().
Автор: Ishayahu Lastov
Генерируем внешние API по-питоновски
В python есть негласное правило — никогда не повторяйся. Чаще всего если в программе приходиться писать почти одно и то-же два раза, значит вы что-то сделали не так. Я приведу пример, как можно автоматизировать генерацию внешних API таким образом, что достаточно будет в одном месте в удобной и универсальной форме описать поддерживаемые вызовы, а все внешнее API для этих вызовов сделает написаный один раз код. Читать