Архив рубрики: 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», которая за линейное время от размера массива, осуществляет такую перестановку элементов, относительно некоторой «оси» — заданного значения, равного одному из значений сортируемого интервала массива, что переставленный массив состоит из трех интервалов, идущих по порядку:

  1. Элементы меньшие «оси»
  2. Элементы равные «оси»
  3. Элемент

Сервис онлайн тестирования Quizful

    Недавно в блоге Алена С++ прочитал пост о бесплатном прохождении тестов на сайте Brainbench. Халява была ограниченна по времени, так что я задался вопросом найти бесплатный аналог и на русском. Больше всего мне понравился сайт онлайн тестов Quizful.

 На котором есть достаточно большое количество тестов по различным тематикам:

  • тесты по администрированию (Unix, Linux, Windows, MacOS)
  • тесты по программированию (C++, Java, C#, 1C, PHP, Python, Ruby, Delphi)
  • тесты по базам данных (SQL, Oracle, MS SQL, MySql)
  • тесты по веб-технологиям (HTML, CSS, JavaScript, HTTP)
  • тесты по управлению проектами (экстремальное программирование, Scrum)

Прохождение тестов для меня это возможность узнать свои слабые места и подтянуть знания.

Преимущества сервиса Quizful

  • Это некоммерческий сервис направленный на помощь IT сообществу
  • После прохождения тестов можно просмотреть правильные ответы с объяснениями
  • Сайт поддерживается сообществом и пройдя пару тройку тестов, можно добавить свои вопросы или задачи.  

Автор: Dmitriy Falko
Дата публикации: 2012-03-19T10:08:00.003+04:00

Выражение 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 на одну, тогда как последний метод вызывается только когда количество ссылок достигает нуля. В некоторых часто встречающихся случаях могут возникнуть ситуации, мешающие обнулению счётчика, как то:
  1. взаимные ссылки между объектами (в списках или в деревьях)
  2. ссылки на объекты в стеке функции, где было вызвано исключение, так как в таком случае ссылки на объекты этого стека сохранены в sys.exc_traceback
  3. ссылки на объекты в стеке, если было вызвано не перехваченное исключение в интерактивном режиме (так как в таком случае ссылки на объекты сохранены в 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 для этих вызовов сделает написаный один раз код. Читать →

Технические задачки

1. Что будет выведено в результате исполнения программы? Почему?

 

class A:
     def __init__(self, name):
          self.name = name
     def __del__(self):
          print self.name,

aa = [A(str(i)) for i in range(3)]
for a in aa:
del a

 Читать →