The Python IAQ: не часто отвечаемые вопросы

Вопрос может быть не часто отвечаемым либо из-за того, что мало людей знают на него ответ, либо, речь идет о каком-то тонком моменте (но о моменте, который может стать ключевым для вас). Я придумал новый термин для моего Java IAQ, но, как оказалось, он также есть на сайте About.com Urban Legends. Существует множество FAQ по Python, но это единственный Python IAQ, за исключением китайского перевода Вэйяня Чена, и японского — Акихиро Такизавы.

Может ли когда-нибудь произойти сбой при выполнении кода в операторе finally?

Что значит когда-нибудь? Ну, вряд ли когда-либо. Код в операторе finnaly выполнится после оператора try независимо от произошедших внутри исключений, и даже если вызван sys.exit. Но как бы там ни было, оператор finnaly никогда не будет выполнен, если это выполнение попросту до него не дойдет. Это может происходить независимо от содержимого choise, как показано ниже:

try:

if choice:

while 1:

pass

else

print "Пожалуйста, выбросите уже Ваш компьютер..."

time.sleep(60 * 60 * 24 * 365 * 10000)

finally:

print "Наконец-то..."

Полиморфизм это прекрасно; можно сортировать список элементов любого типа, так ли это?

Это не так. Рассмотрим следующий пример:

>>> x = [1, 1j]
>>> x.sort()
Traceback (most recent call last):
File "<pyshell#13>", line 1, in ?
x.sort()
TypeError: cannot compare complex numbers using <, <=, >, >=

(Число 1j это корень квадратный из -1.) Проблема в том, что метод sort (в данной реализации) сравнивает элементы, используя метод __lt__, который отказывается сравнивать комплексные числа (т.к. они не упорядочиваемы). Любопытно, что у complex.__lt__ нет сомнений при сравнении комплексных чисел со строками, списками и с любым другим типом, за исключением самих комплексных чисел. Итак, ответ таков: сортировать последовательности объектов, которые поддерживают метод __lt__ можно (и, возможно, другие методы, если произойдут изменения в реализации).

Что касается первой части вопроса "Полиморфизм это прекрасно", то я бы хотел с этим согласиться, но иногда Python делает это затруднительным, т.к. многие типы (такие как последовательность и число) определены неформально.

Можно ли использовать в Python ++x и x++?

Если буквально, то, да и нет; но для практических целей, нет. Что я имею в виду?

Да, в Python это возможно, но оно не всегда будет соответствовать тому значению, которое вкладывают в него C++ или Java программисты. + является унарным префиксным оператором, поэтому, ++x расписывается как +(+(x)), что (по крайней мере для чисел) приводит только к x.
Нет, x++ само по себе не является разрешенным выражением, хотя в некотором контексте, оно может быть использовано. Например, x++ - y рассматривается как x + +(-(y)), что для чисел эквивалентно x - y. Можно создать класс, где ++x будет иметь некий смысл; например, класс может хранить число и имея унарный оператор + увеличивать его на 0.5 (или на 1 с возможностью увеличения на 0.5, если вам нравятся рандомизированные алгоритмы), но все же …

Нет, это было бы глупо. Лучше воспользоваться x += 1, что добавлено в Python 2.0.

При более глубоком рассмотрении, вопрос заключается в следующем: почему Python не разрешает использование x++? Я уверен в том, что по той же причине в Python не разрешена операция присваивания в выражениях: Python хочет четко разграничить операторы и выражения. Если вы уверены, что они должны быть отделены друг от друга, тогда, возможно, запрет ++ будет лучшим решением. С другой стороны, сторонники функциональных языков утверждают, что операторы должны быть выражениями. Я со своим коллегой Бьёрном Страуструпом сторонники этого. В Дизайн и эволюция языка C++ он сказал: "Если бы я был при разработке языка с самого начала, то придерживался пути Algol68 и сделал все операторы и определения выражением, которое возвращает некое значение".

Можно ли использовать синтаксис C++ для ostreams: cout << x << y ... ?

Это возжно. Если вам не нравится писать "print x, y", тогда попробуйте это:

class ostream:
def __init__(self, file):
self.file = file

def __lshift__(self, obj):
self.file.write(str(obj));
return self

cout = ostream(sys.stdout)
cerr = ostream(sys.stderr)
nl = '\n'

cout << x << " " << y << nl

(Здесь приведен код файла, который находится выше горизонтальной линии, а пример его использования, ниже.) Это дает другой синтаксис, но не даст новой конвенции для печати — это всего лишь пакеты выше конвенции str, которые уже существуют в Python. Это схоже с конвенцией toString() в Java. У C++ много разных конвенций: вопреки каноническому пути преобразования объекта в строку, существует канонический путь выведения объекта в поток (хорошо, не совсем канонический — множество кода на C++ по-прежнему использует printf). Подход к потоку более сложен, но все же имеет преимущество в том, что если вам необходимо напечатать действительно огромный объект, то необязательно создавать для этого реально огромные временные сроки.

Что если мне больше нравится printf из C++?

Определить printf в Python — не плохая идея. Можно аргументировать это тем, что printf("%d = %s", num, result) более природно, чем print "%d = %s" % (num, result), т.к. круглые скобки находятся в более привычном месте (и можно пренебречь %). Более того, все же так просто:

def printf(format, *args): print format % args,

Хотя это и было сказано в шутку, здесь есть несколько коварных моментов. Во-первых, мне пришлось решить: добавлять запятую в конце или нет. Чтобы все было более похожим на C++, я решил ее добавить (что значит, если вы захотите напечатать новую строку, тогда придется добавить ее самому к концу форматируемой). Второе, по-прежнему будут печататься пробелы в конце строки. Если вы этого не хотите, используйте sys.stdout.write, а не print. В-третьих, насколько оно будет полезно, кроме того, что похоже на C? Да; нам нужна функция для печати (для противопоставления оператору print), для использования в местах, которые принимают функции, но не такие операторы, как в lambda-выражениях или в качестве первого аргумента для map. Фактически, такая функция настолько удобна, что можно даже не захотеть проводить само форматирование:

def prin(x): print x,

Теперь map(prin, seq) станет печатать каждый элемент seq, но map(print, seq) уже будет синтаксической ошибкой. Я знаю некоторых невнимательных программистов (ну хорошо, им был я, но я знал, что был невнимателен) считающих, что подогнать обе эти функции под одну - было бы хорошей идей, как показано ниже:

def printf(format, *args): print str(format) % args,

В таком случае, все printf(42), printf('A multi-line\n message') и printf('%4.2f', 42) работают. Но "хорошая идея" становится тем "о чем я уже думал", после того, как попробовать printf('100% guaranteed'), или что-нибудь другое с символом %, который не является директивой форматирования. Если вы будете использовать эту версию printf, то понадобится комментарий наподобие этого:

def printf(format, *args):
"""Форматируем args с первым аргументом как форматирование строки, затем распечатываем.
Если формат не является строкой, то собираем его в одно целое с помошью str.
Используйте printf('%s', x) вместо printf(x), если x, возможно, содержит символы \ или %."""
print str(format) % args,

Есть ли более удобная запись для литералов словаря? Все мои ключи — индефикаторы.

Конечно! Я согласен, что печатать ключи в кавычках может быть утомительно, особенно, для большого литерала. Поначалу я думал, что для этого было бы удобно внести в Python специальный синтаксис; возможно {a=1, b=2}, для того, чтобы теперь писать {'a':1, 'b':2}. Из Python 2.3 можно воспользоваться dict(a=1, b=2, c=3, dee=4), что будет достаточно, как для того, что меня интересовало. До Python 2.3 я использовал строчную функцию def Dict(**dict): return dict.

Читатель говорит, что у Perl есть подобные специальные примечания для хешей, т.е. можно писать ("a", 1, "b", 2) или (a => 1, b => 2), для хеш-литералов в Perl. Это правда, но не полная. "man perlop" говорит "The => digraph is mostly just a synonym for the comma operator ...", что фактически значит, что можно писать (a, 1, b, 2), где a и b просто слова. Но, Даг Асхайм указывает на то, что если вы включите strict, то получите ошибку; вам понадобится использовать строки или оператор =>. Ларри Уолл также заявил: "В Perl 6 слов без кавычек не будет".

Существуют ли быстрый способ создания объектов?

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

class Struct:
def __init__(self, **entries): self.__dict__.update(entries)

>>> globals = Struct(answer=42, linelen = 80, font='courier')

>>> globals.answer
42
>>> globals.answer = 'plastics'
>>> vars(globals)
{'answer': 'plastics', 'font': 'courier', 'linelen': 80}

В действительности все, что мы здесь сделали, так это создали анонимный класс. Хорошо, я знаю, что класс globals это Struct, но из-за того, что мы добавили к нему слоты — это как создать новый, безымянный класс (также как lambda создает анонимные функции). Я ненавижу путаться со Struct, т.к. он на столько краток, на сколько это возможно, но если добавить следующий метод, то получаем приятную версию печати каждой структуры:

def __repr__(self):
args = ['%s=%s' % (k, repr(v)) for (k,v) in vars(self).items()]
return 'Struct(%s)' % ', '.join(args)

>>> globals
Struct(answer='plastics', font='courier', linelen=80)

Это отлично подходит для создания объектов; как насчет усовершенствования?

У словарей есть метод update, поэтому можно сделать d.update(dict(a=100, b=200)), где d — словарь. На практике надлежащего метода для объектов не существует, и приходится использовать obj.a = 100; obj.b = 200. Или же можно определить функцию, которая позволит сделать update(x, a=100, b=200), где x это также словарь или объект:

import types

def update(x, **entries):
if type(x) == types.DictType: x.update(entries)
else: x.__dict__.update(entries)
return x

Это особенно хорошо подходит для конструкторов:

def __init__(self, a, b, c, d=42, e=None, f=()):
update(self, a=a, b=b, c=c, d=d, e=e, f=f)

Могу я создать dict с начальным значением 0 или [ ], или с чем-то вроде этого?

Я поддерживаю вас в том, что подсчитывать что-либо намного удобнее, с помощью count[x] += 1, чем count[x] = count.get(x, 0) + 1. Что касается Python 2.2, то проще будет сделать встроенный класс dict в качестве подкласса. Я называю это своей версией DefaultDict. Отмечу использование copy.deepcopy; оно не должно заставлять каждый ключ в словаре делиться тем же [], как и значение по умолчанию (мы, возможно, попусту тратим время, копируя 0, но потеря будет не так ощутима, если сделать больше обновлений и обращений чем инициализаций):

class DefaultDict(dict):
"""Словарь придающий начальные значениея новым ключам."""
def __init__(self, default):
self.default = default

def __getitem__(self, key):
if key in self: return self.get(key)
return self.setdefault(key, copy.deepcopy(self.default))

>>> d = DefaultDict(0)

>>> d['hello'] += 1
>>> d
{'hello': 1}
>>> d2 = DefaultDict([])
>>> d2[1].append('hello')
>>> d2[2].append('world')
>>> d2[1].append('there')
>>> d2
{1: ['hello', 'there'], 2: ['world']}

def bigrams(words):
"Подсчет пар слов в словаре словарей."
d = DefaultDict(DefaultDict(0))
for (w1, w2) in zip([None] + words, words + [None]):
d[w1][w2] += 1
return d

>>> bigrams('i am what i am'.split())
{None: {'i': 1}, 'i': {'am': 2}, 'what': {'i': 1}, 'am': {None: 1, 'what': 1}}

Отмечу, что без DefaultDict, d[w1][w2] += 1 из bigrams должно выглядеть на подобии этого:

d.setdefault(w1,{}).setdefault(w2, 0); d[w1][w2] += 1

Можно ли написать код для транспонирования матрицы в 0.007KB или меньше?

Я уже думал, вы об этом никогда не спросите. Если представить матрицу как последовательность последовательностей, тогда zip может выполнить всю работу за нас:

>>> m = [(1,2,3), (4,5,6)]
>>> zip(*m)
[(1, 4), (2, 5), (3, 6)]*

Для того чтобы понять это, надо знать, что f(*m) это как apply(f, m). Корни этого идут от старого вопроса из Lisp, ответ на который map(None,*m) из Python, но версия с zip, предложенная Чи-Чан Чаном, будет даже более изящной. Вы наверно думаете, что это годится только для показа в "Тупых программерских трюках Лэттермана", но уже в ближайшие дни я столкнулся с этой проблемой: дан список из рядов базы данных, где каждый ряд состоит из списка упорядоченных значений, и надо найти список уникальных значений, которые встречаются в каждой колонке. Итак, решение:

possible_values = map(unique, zip(*db))

Классный трюк с f(m). Будет ли все также работать с использованием метода вызова, например, x.f(y)?

Этот вопрос показывает общее заблуждение. Ведь синтаксиса для метода вызова нет! Есть синтаксис для вызова функции, есть для извлечения поля объекта, есть сразу оба эти метода. Вместе эти три метода задуманы для того, чтобы x.f(y) выглядело как один целый синтаксический кусок, когда в действительности это эквивалентно (x.f)(y), что в свою очередь эквивалентно (getattr(x, 'f'))(y). Как я вижу, вы мне не верите. Смотрите:

class X:
def f(self, y): return 2 * y

>>> x = X()
>>> x.f
<bound method X.f of <__main__.X instance at 0x009C7DB0>>
>>> y = 21
>>> x.f(y)
42

>>> (x.f)(y)
42
>>> (getattr(x, 'f'))(y)
42
>>> xf = x.f
>>> xf(y)
42
>>> map(x.f, range(5))
[0, 2, 4, 6, 8]

Итак, ответ на этот вопрос таков: можно поместить *y или **y (либо то, что вы хотите поставить в вызов функции) в метод вызова, потому что вызов метода является всего лишь вызовом функции.

Можно ли встроить в Python абстрактные классы длиной в 0 срок кода? Или в 4?

В Java есть ключевое слово abstract, поэтому можно определить абстрактные классы, не являющиеся экземплярами и которые могут стать подклассами, если вы снабдите этот класс всеми абстрактными методами. Малоизвестный факт, что использовать abstract в Python можно практически тем же способом; отличие лишь в том, что если вы будете пытаться вызвать невстроенный метод, то получите ошибку при выполнении программы, а не во время ее компиляции. Сравнение:

## Python
class MyAbstractClass:
def method1(self): abstract

class MyClass(MyAbstractClass):
pass

>>> MyClass().method1()
Traceback (most recent call last):
...
NameError: name 'abstract' is not defined

/* Java */
public abstract class MyAbstractClass {
public abstract void method1();
}

class MyClass extends MyAbstractClass {}

% javac MyAbstractClass
MyAbstractClass.java:5:
class MyClass must be declared abstract.
It does not define void method1() from class MyAbstractClass.

Не тратьте попусту время в поисках ключевого слова abstract в справочном руководстве для Python; его там нет. Я добавил это в язык, и самое интересное то, что оно заняло 0 строк кода! При вызове method1 мы получим NameError, т.к. нет переменной abstract. (Возможно, вы скажете, что это мошенничество, из-за того, что возможна ошибка, если кто-нибудь определит переменную называемую abstract. Но также это может произойти, если кто-нибудь переопределит переменную, от которой зависит код. Единственное отличие здесь в том, что мы зависим скорее от недостатка определения, чем в самом определении.)

Если вы готовы писать abstract() взамен abstract, то можете определить функцию, которая ставит NotImplementedError вместо NameError, что придает большего смысла. (Также, если кто-то переопределит abstract, чтобы это было не больше чем функция без аргументов, вы по-прежнему получите сообщение об ошибке.) Чтобы сделать сообщение об ошибке от abstract более приятным, просто загляните в стековый фрейм, и посмотрите, кто этот нарушитель:

def abstract():
import inspect
caller = inspect.getouterframes(inspect.currentframe())[1][3]
raise NotImplementedError(caller + ' must be implemented in subclass')

>>> MyDerivedClass().method1()
Traceback (most recent call last):
...
NotImplementedError: method1 must be implemented in subclass

Как можно реализовать перечисляемый тип (enums) в Python?

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

red, green, blue = range(3)

Но здесь есть одно препятствие, где бы мы не добавили новую переменную слева, нам придется увеличить число, стоящее справа. Тем не менее, это не так уж и плохо, потому что если получим его неправильно, Python выдаст ошибку. Это, возможно, будет лучшим способом изолировать enums в класс:

class Colors:
red, green, blue = range(3)

Теперь Colors.red приносит нам 0, и может стать полезным dir(Colors) (также надо игнорировать вхождения __doc__ и __module__). Если потребуется контролировать каждое содержимое, которое будут иметь переменные в enum, то можно использовать функцию Struct из нескольких уже разобранных ранее вопросов:

Enum = Struct
Colors = Enum(red=0, green=100, blue=200)

Пока что, этих обычных подходов хватает, но некоторые люди хотят большего. Вот несколько дополнений для Enum на python.org, ASPN, и faqts. Возможно вас заинтересует моя версия, которая подходит (практически) для всех случаев и для всех людей, и которая в тоже время является достаточно сжатой:

class Enum:
"""Создаем перечисляемый тип, затем добавляем в него пары переменная/значение.
Конструктор и метод .ints(names) принимает список имен переменных
и присваивает им последовательные целые числа в качестве значения. Метод .strs(names)
присваивает каждой переменной имя самой себя (что значит, переменная 'v' будет иметь значение 'v').
Метод .vals(a=99, b=200) позволяет присваивать переменным любые значения.
'Список имен переменных' может быть строкой, которая будет обладать .split().
Метод .end() возвращает на единицу больше чем максимальное целое значение.
Пример: opcodes = Enum("add sub load store").vals(illegal=255)."""

def __init__(self, names=[]): self.ints(names)

def set(self, var, val):
"""Ставит для var значение val в enum."""
if var in vars(self).keys(): raise AttributeError("дублирующийся var в enum")
if val in vars(self).values(): raise ValueError("дублирующееся value в enum")
vars(self)[var] = val
return self

def strs(self, names):
"""Ставит для каждого из names само себя (как строку) в enum."""
for var in self._parse(names): self.set(var, var)
return self

def ints(self, names):
"""Ставит для каждого из names целое увеличенное число в enum."""
for var in self._parse(names): self.set(var, self.end())
return self

def vals(self, **entries):
"""Ставит каждую пару var=val в enum."""
for (var, val) in entries.items(): self.set(var, val)
return self

def end(self):
"""Возвращает на единицу больше чем наибольшее целое значение в enum, либо 0, если ничего нет."""
try: return max([x for x in vars(self).values() if type(x)==type(0)]) + 1
except ValueError: return 0

def _parse(self, names):
### If names is a string, parse it as a list of names.
if type(names) == type(""): return names.split()
else: return names

Пример использования:

>>> opcodes = Enum("add sub load store").vals(illegal=255)
>>> opcodes.add
0
>>> opcodes.illegal
255
>>> opcodes.end()
256
>>> dir(opcodes)
['add', 'illegal', 'load', 'store', 'sub']
>>> vars(opcodes)
{'store': 3, 'sub': 1, 'add': 0, 'illegal': 255, 'load': 2}
>>> vars(opcodes).values()
[3, 1, 0, 255, 2]

Отмечу, что методы являются каскадными, поэтому можно комбинировать .strs, .ints и .vals в одной строке после конструктора. Также отмечу полезное использование dir и vals, которые позволяют избежать перемешивания с любыми другими переменными, которые вы определяете. Чтобы пройтись через все пронумерованные значения, используйте for x in vars(opcodes).values(). Также, если понадобится, можно использовать нецелые значения для enum переменных, используя методы .strs и .vals. И, наконец, замечу, что дублирование имени переменной или ее значение, приведет к ошибке. Иногда требуется иметь дублирующиеся значения (например, для псевдонимов); если вам это понадобится, тогда либо удалите строку, которая вызывает ValueError, или, например, воспользуйтесь vars(opcodes)['first_op'] = 0. Но есть одна вещь, которая меня очень тревожит, это возможность конфликта между vals и values; стоит подумать о более лучшем названии для vals.

Почему в Python нет типа данных "Set"?

Когда этот вопрос был впервые сформулирован, он не был единственным, и программисты взамен ему использовали словари. Но сейчас в Python 2.4 есть хорошая собственная поддержка типа set.

Должен ли я, и могу ли использовать тип Boolean?

При первом рассмотрении этого вопроса Python еще не поддерживал тип Boolean, но уже с Python 2.3 можно использовать тип bool.

Возможна ли альтернатива (test ? result : alternative) в Python?

Java и C++ имеют тройной условный оператор (test ? result : alternative). Python пытается противостоять этому, но уже с версией 2.5 будут разрешены выражения вида (result if test else alternative). Таким образом подрывается чистое распознавание в Python между выражениями и операторами, но это компромисс, на который приходится идти ради многих людей.

Что можно сделать до того, как выйдет Python 2.5?

Можно попробовать [alternative, result][test]. Отмечу, что требуется и alternative и result, поэтому будет не хорошо, если одно из них вызывается рекурсивно либо требует дорогостоящих вычислений. Если test может вернуть не bool, то попробуйте
[result, alternative][not test]
test and result or alternative Кто-то может подумать, что это естественно, в то время как другие считают это затруднительным. Такое возможно только когда result гарантированно будет не false.
(test and [result] or [alternative])[0] позволяет избежать действующее ограничение.
[lambda: result, lambda: alternative][not not test]() проходит через все ограничения, возникающие на сегодняшний день (за исключением удобочитаемости), но не говорите, что я сказал вам это использовать. Можете даже запаковать это в вызов. Утвержденная конвенция именования переменных, которые имитируют ключевые слова, заключается в добавлении замыкающего подчеркивания. Поэтому:
if_(test, result, lambda: alternative) где мы определяем

def if_(test, result, alternative=None):
"Если test является true, 'выполняем' result, в противном случае alternative. 'Выполняем' значит вызываем если это возможно."
if test:
if callable(result): result = result()
return result
else:
if callable(alternative): alternative = alternative()
return alternative

>>> fact = lambda n: if_(n <= 1, 1, lambda: n * fact(n-1))
>>> fact(6)
720

Теперь, предположим, что по некоторым причинам вы выберете синтаксис "if (test) ...", а не "if(test, ..." (и ни за что не хотите оставить часть alternative). Тогда попробуйте:

def if_(test):
return lambda alternative: \
lambda result: \
[delay(result), delay(alternative)][not not test]()

def delay(f):
if callable(f): return f
else: return lambda: f

>>> fact = lambda n: _if (n <= 1) (1) (lambda: n * fact(n-1))
>>> fact(100)
9332621544394415268169923885626670049071596826438162146859296389521759999322991
5608941463976156518286253697920827223758251185210916864000000000000000000000000L

Какие еще основные типы отсутствуют в Python?

В Python есть одна великолепная вещь: использования чисел, строк, списков и словарей (а теперь и set и bool) может быть достаточно. Но все же есть несколько основных типов, которые по-прежнему отсутствуют. Как для меня, самое важное это способность строк к изменениям. Делать str += x снова и снова, очень медленно, а манипулировать списками символов (или списками подстрок) подразумевает вызовы функций для работы со строками. Один из возможных вариантов обойти это, воспользоваться array.array('c'). Другой — UserString.MutableString, хотя его предполагаемое использование скорее образовательное, чем практическое. Третье, это mmap модуль и четвертое, cStringIO. Ни одно из них не идеально, но вместе они дают достаточный выбор. После я понял, что мне хотелось бы реализовать некую очередь сортировок. Есть стандартная библиотека Queue module, но она специализирована на thread-очереди. Благодаря тому, что существует такой большой выбор, не будем лоббировать стандартные библиотечные реализации очереди. Как бы там ни было, я предлагаю собственную реализацию трех типов очередей, FIFO, LIFO, а также очередности:

"""
Этот модуль предоставляет три типа очередей, со следующими конструкциями:
Stack([items]) -- создает LIFO очередь; реализовано ввиде списка
Queue([items]) -- создает FIFO очередь
PriorityQueue([items]) -- создает очередь, где минимальный эдемент (<) стоит первым
Здесь [items] необязательный список начальных элементов; если опущено, очередь пуста.
Каждый тип поддерживает следующие методы и функции:
len(q) -- число элементов в q (также q.__len__())
q.append(item) -- добавить элемент в очередь
q.extend(items) -- добавить элементы в очередь
q.pop() -- удалить и вернуть "первый" элемент из очереди
"""

def Stack(items=None):
"Стек или LIFO чередь; реализовано ввиде списка."
return items or []

class Queue:
"FIFO чередь."
def __init__(self, items=None): self.start = 0; self.A = items or []
def __len__(self): return len(self.A) - self.start
def append(self, item): self.A.append(item)
def extend(self, items): self.A.extend(items)

def pop(self):
A = self.A
item = A[self.start]
self.start += 1
if self.start > 100 and self.start > len(A)/2:
del A[:self.start]
self.start = 0
return item

class PriorityQueue:
"Очередь в которой минимальный элемент (определенный cmp) стоит первым."
def __init__(self, items=None, cmp=operator.lt):
self.A = []; self.cmp = cmp;
if items: self.extend(items)

def __len__(self): return len(self.A)

def append(self, item):
A, cmp = self.A, self.cmp
A.append(item)
i = len(A) - 1
while i > 0 and cmp(item, A[i//2]):
A[i], i = A[i//2], i//2
A[i] = item

def extend(self, items):
for item in items: self.append(item)

def pop(self):
A = self.A
if len(A) == 1: return A.pop()
e = A[0]
A[0] = A.pop()
self.heapify(0)
return e

def heapify(self, i):
"Предполагается, что A является массивом чьи правые и левые дети -- кучи,"
"передвигаем A[i] в правильное положение. Смотри CLR&S стр. 130"
A, cmp = self.A, self.cmp
left, right, N = 2*i + 1, 2*i + 2, len(A)-1
if left <= N and cmp(A[left], A[i]):
smallest = left
else:
smallest = i
if right <= N and cmp(A[right], A[smallest]):
smallest = right
if smallest != i:
A[i], A[smallest] = A[smallest], A[i]
self.heapify(smallest)

Отмечу идиому "items or []". Было бы неправильно сделать что-нибудь наподобие:

def Stack(items=[]): return items

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

s = Stack(items)

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

Как реализовать синглтон шаблон (одиночка) в Python?

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

def singleton(object, instantiated=[]):
"Вызываем исключение, если экземпляр объекта этого класса уже был создан."
assert object.__class__ not in instantiated, \
"%s является классом синглтон, но его экземпрял уже создан" % object.__class__
instantiated.append(object.__class__)

class YourClass:
"Что-нибудь делаем ..."
def __init__(self, args):
singleton(self)
...

Кроме того, можно попытаться воспользоваться метаклассами, для возможности писать class YourClass(Singleton), но зачем это беспокойство? До того, как "Gang of Four" стали мучить нас своими обоснованиями, "singleton" (без формального имени) было всего лишь простой идеей, которая заслуживала одной строки кода, а не целой религии.

Хорошо ли, что нет "news"?

Я допускаю, что вы считаете положительным то, что в Python нет ключевого слова new. Так оно и есть. В C++, new используется для выделения памяти в куче, вместо стека. Таким образом, оно является полезным. В Java, все объекты придерживаются динамического выделения памяти, поэтому new не имеет реальной цели; оно только служит для напоминания в отличиях между конструктором и другими статическими методами. Но это различие, возможно, приносит Java скорее больше вреда, чем пользы, т.к. различие низкоуровневое и силовая реализация решений должна быть отложена. Я считаю, что в Pyton был сделан правильный выбор, оставив синтаксис вызова конструктора таким же, как и синтаксис вызова обычной функции.

Например, до того, как появился класс bool, мы хотели его реализовать. Давайте назовем его Bool, чтобы было отличие с уже существующим. Допустим, мы хотим реализовать идею, в которой должен быть только один объект true и один false, типа Bool. Один из способов сделать это, переименовать класс Bool в _Bool (так, чтобы оно не экспортировалось), а затем определим функцию Bool, как показано далее:

def Bool(val):
if val: return true
else: return false

true, false = _Bool(1), _Bool(0)

Это делает Bool фабрикой для _Bool объектов (хотя, безусловно, завод с необычно малым потенциалом). Дело в том, что программист, который вызывает Bool(1), не должен волноваться о том, вернет ли объект еще один новый или повторно использованный объект (по крайней мере, в случае с неизменными объектами). Синтаксис Python позволяет скрывать эти отличия, в то время как Java нет.

Существует некоторая путаница в литературе; некоторые люди используют термин "Singleton Pattern" для этого типа фабрики, где существует единственный объект для каждого различного аргумента конструктора. Я голосую за то, что я верю, в преобладание моего определения Singleton из предыдущего вопроса. Вы, конечно же, можете заключить этот образец в класс. Мы назовем это "CachedFactory". Идея в том, что вы пишете

class Bool:
... ## смотри здесь определение Bool

Bool = CachedFactory(Bool)

и тогда, в первый раз, когда вы вызовете Bool(1), список аргументов (1,) передается оригинальному классу Bool, но любой следующий вызов Bool(1) вернет первый объект, который уже хранился в кэше:

class CachedFactory:
def __init__(self, klass):
self.cache = {}
self.klass = klass

def __call__(self, *args):
if self.cache.has_key(args):
return self.cache[args]
else:
object = self.cache[args] = self.klass(*args)
return object

Единственное, что надо отметить, ничего не зависит от классов и конструкторов; этот образец будет работать с любым способным к вызову. Применительно к функциям в целом, это называется "Memoization Pattern". Реализация таже, меняются только названия:

class Memoize:
def __init__(self, fn):
self.cache = {}
self.fn = fn

def __call__(self, *args):
if self.cache.has_key(args):
return self.cache[args]
else:
object = self.cache[args] = self.fn(*args)
return object

Теперь можно использовать fact = Memoize(fact) и рассчитывать факториалы с амортизацией времени O(1), а не O(n).

Можно ли реализовать механизм истории как в shell?

Конечно. Это то, что вы хотите?

>>> from shellhistory import h
h[2] >>> 7*8
56
h[3] >>> 9*9
81
h[4] >>> h[2]
56
h[5] >>> 'hello' + ' world'
'hello world'
h[6] >>> h
[None, 9, 56, 81, 56, 'hello world']
h[7] >>> h[5] * 2
'hello worldhello world'
h[8] >>> h[7] is _ is h[-1]
1

Как это работает? Переменная sys.ps1, это системная переменная. По умолчанию, это строка '>>> ', но ее можно задать любой. Если сделать ее не объектом string, тогда будет вызываться метод __str__ этого объекта. Поэтому мы создадим объект, чей строковой метод добавляет последний результат (переменная _) в список, называемый h (для истории), а затем вернем строку приглашения, которая включает в себя длину списка следующего за '>>>'. Или, по крайней мере, таков был план. Как выяснилось (в крайнем случае, для IDLE 2.2 реализации под Windows), sys.ps1.__str__ будет вызвано три раза, а не только один, прежде чем будет напечатано приглашение. Не спрашивайте меня почему. Для борьбы с этим я просто добавил _, для случая, когда существует не только последний элемент в списке истории. И меня не смущает тот факт, что надо вставить None в конец списка истории, т.к. это не отображается интерактивным циклом Python, и я не вставлял сам h в h, потому что замкнутость может привести к возникновению проблем с печатью или с сравнением. Еще одна сложность заключается в том, что интерпретатор Python в действительности пытается напечатать '\n' + sys.ps1 (когда он должен печатать '\n' отдельно, или напечатать '\n' + str(sys.ps1)), что означает, sys.ps1 нуждается в методе __radd__. Наконец, моя первая версия потерпит неудачу, если импортировать в качестве самого первого ввода в сессию Python (или в загружаемый файл .python). После некоторых расследований выяснилось, что это происходит из-за того, что переменная _ не связана до того, как будет вычислено первое выражение. Поэтому я отловил исключение, когда _ не связано. Это все дает нам:

import sys

h = [None]

class Prompt:
"Создаем приглашение, которое хранит результаты (т.е. _) в массиве h."
def __init__(self, str='h[%d] >>> '):
self.str = str;

def __str__(self):
try:
if _ not in [h[-1], None, h]: h.append(_);
except NameError:
pass
return self.str % len(h);

def __radd__(self, other):
return str(other) + str(self)

sys.ps1 = Prompt()

Как можно вычислить время работы моих функций?

Вот вам простой ответ:

def timer(fn, *args):
"Время применения fn к args. Возвращает (результат, секунды)."
import time
start = time.clock()
return fn(*args), time.clock() - start

>>>timer(max, range(1e6))
(999999, 0.4921875)

Также, существует более сложный ответ на этот вопрос, который можно найти в моем модуле с утилитами.

Как выглядит ваш начальный файл .python?

В настоящее время он выглядит так, но постоянно подвергается изменениям:

from __future__ import nested_scopes
import sys, os, string, time
from utils import *

################ Интерактивное приглашение и отладка ################

try:
import readline
except ImportError:
print "Модуль readline недоступен."
else:
import rlcompleter
readline.parse_and_bind("вкладки: завершено.")

h = [None]

class Prompt:
def __init__(self, str='h[%d] >>> '):
self.str = str;

def __str__(self):
try:
if _ not in [h[-1], None, h]: h.append(_);
except NameError:
pass
return self.str % len(h);

def __radd__(self, other):
return str(other) + str(self)

if os.environ.get('TERM') in [ 'xterm', 'vt100' ]:
sys.ps1 = Prompt('\001\033[0:1;31m\002h[%d] >>> \001\033[0m\002')
else:
sys.ps1 = Prompt()
sys.ps2 = ''