Программирование на Python 3. Руководство издательство СимволПлюс
 Скачать 3.74 Mb.
|
|
316 Глава 6. Объектно/ориентированное программирование self.__list = sequence.__list[:] else: self.__list = sorted(list(sequence), key=self.__key) Поскольку имя функции является ссылкой на объект (то есть на функ цию), мы можем хранить функции в переменных как ссылки на лю бые другие объекты. Здесь частная переменная self.__key хранит ссылку на ключевую функцию, передаваемую методу, или функцию идентичности. Первая инструкция метода использует тот факт, что оператор ИЛИ возвращает первый операнд, если в логическом контек сте он оценивается как True (то есть когда аргумент key имеет значение, отличное от None), или второй операнд – в противном случае. Немного более длинный, но более очевидный вариант: self.__key = key if key is not None else _identity Теперь, когда мы определились с ключевой функцией, мы используем инструкцию assert, чтобы убедиться, что эту функцию можно вызы вать. Встроенная функция hasattr() возвращает True, если объект, пе реданный в первом аргументе, имеет атрибут, имя которого передает ся во втором аргументе. Имеются соответствующие функции setattr() и delattr(), которые будут описываться в главе 8. Все вызываемые объекты, такие как функции или методы, имеют атрибут __call__. Чтобы порядок создания сделать максимально похожим на создание объектов типа list, мы определили необязательный аргумент sequence, соответствующий единственному аргументу функции list(). Класс SortedList включает в себя коллекцию типа list в виде частной пере менной self.__list и сохраняет в этой переменной элементы в отсорти рованном порядке, используя заданную ключевую функцию. Предложение elif проверяет, является ли заданная последователь ность объектом типа SortedList, и если это так, то проверяет, не ис пользуется ли для этой последовательности та же самая ключевая функция. Если последовательность удовлетворяет обоим критериям, то просто создается поверхностная копия последовательности без ее сортировки. Если большинство ключевых функций создается «на ле ту», с помощью инструкции lambda, при сравнивании они не будут рас цениваться как эквивалентные, даже если содержат один и тот же программный код, поэтому такая оптимизация на практике может не давать существенного эффекта. @property def key(self): return self.__key После создания сортированного списка его ключевая функция должна быть зафиксирована, поэтому мы сохраняем ее в частной переменной, чтобы предотвратить возможность ее изменения. Но у некоторых пользователей может возникнуть потребность получить ссылку на ключевую функцию (как будет показано в следующем подразделе), по Собственные классы коллекций 317 этому мы создаем свойство, доступное только для чтения, обеспечи вающее такую возможность. def add(self, value): index = self.__bisect_left(value) if index == len(self.__list): self.__list.append(value) else: self.__list.insert(index, value) Когда вызывается этот метод, он должен вставить указанное значение в частный список self.__list в нужную позицию, соблюдая порядок сортировки списка. Частный метод SortedList.__bisect_left() возвра щает индекс требуемой позиции, как будет показано чуть ниже. Если новое значение больше любого другого значения в списке, то его следу ет добавить в конец списка и в этом случае индекс позиции будет равен длине списка (номера позиций в списке начинаются с 0 и заканчива ются значением len(L) – 1 ). В этом случае добавление нового элемента должно выполняться методом append(). В противном случае произво дится вставка нового значения в найденную позицию, которая может иметь порядковый номер 0, если новое значение меньше любого друго го значения в списке. def __bisect_left(self, value): key = self.__key(value) left, right = 0, len(self.__list) while left < right: middle = (left + right) // 2 if self.__key(self.__list[middle]) < key: left = middle + 1 else: right = middle return left Этот частный метод вычисляет номер позиции в списке, куда должно быть вставлено новое значение. Он вычисляет ключ для нового значе ния, используя ключевую функцию, и сравнивает с вычисленными ключами проверяемых элементов. Алгоритм, используемый методом, называется алгоритмом двоичного поиска (или поиск методом поло винного деления), который обладает высокой скоростью даже в случае очень больших списков. Например, чтобы отыскать местоположение нового значения в списке, насчитывающем 1 000 000 элементов, тре буется выполнить не более 21 сравнения. 1 Сравните это с простым, не сортированным списком, для которого используется алгоритм линей ного поиска, требующий выполнить в среднем 500 000 сравнений, 1 Модуль bisect, входящий в состав стандартной библиотеки языка Python, содержит функцию bisect.bisect_left() и ряд других функций, но к момен ту написания этих строк ни одна из функций в модуле bisect не обеспечива ла возможность использования ключевых функций. 318 Глава 6. Объектно/ориентированное программирование а в самом тяжелом случае – до 1 000 000 сравнений, чтобы отыскать местоположение нового значения в списке, насчитывающем 1 000 000 элементов. def remove(self, value): index = self.__bisect_left(value) if index < len(self.__list) and self.__list[index] == value: del self.__list[index] else: raise ValueError("{0}.remove(x): x not in list".format( self.__class__.__name__)) Этот метод используется, чтобы удалить первое вхождение заданного значения. Он использует метод SortedList.__bisect_left(), чтобы оты скать позицию заданного значения, после чего проверяет, находится ли найденный индекс внутри списка и действительно ли в найденной позиции находится искомое значение. Если условия выполняются, производится удаление элемента; в противном случае возбуждается исключение ValueError (что полностью соответствует поведению мето да list.remove() в аналогичной ситуации). def remove_every(self, value): count = 0 index = self.__bisect_left(value) while (index < len(self.__list) and self.__list[index] == value): del self.__list[index] count += 1 return count Этот метод похож на метод SortedList.remove() и является расширени ем API списка. Сначала он отыскивает в списке номер позиции перво го вхождения заданного значения и затем в цикле, пока значение ин декса находится в пределах списка и значение элемента в данной пози ции совпадает с указанным значением, производит удаление элемен тов. В этом программном коде имеется очень тонкий момент – так как в каждой итерации происходит удаление элемента списка, то после удаления элемента в позиции с данным индексом оказывается эле мент, следовавший за удаленным. def count(self, value): count = 0 index = self.__bisect_left(value) while (index < len(self.__list) and self.__list[index] == value): index += 1 count += 1 return count Этот метод возвращает число вхождений заданного значения в список (которое может быть равно 0). Он использует очень похожий алго Собственные классы коллекций 319 ритм, что и метод SortedList.remove_every(), только здесь в каждой ите рации необходимо увеличивать номер позиции. def index(self, value): index = self.__bisect_left(value) if index < len(self.__list) and self.__list[index] == value: return index raise ValueError("{0}.index(x): x not in list".format( self.__class__.__name__)) Так как объект типа SortedList представляет собой отсортированный список, мы можем использовать метод половинного деления, чтобы отыскать (или не отыскать) заданное значение в списке. def __delitem__(self, index): del self.__list[index] Специальный метод __delitem__() обеспечивает поддержку синтаксиса del L[n] , где L – это отсортированный список, а n – целое число, опреде ляющее номер позиции в списке. Мы не выполняем проверку на выход индекса за пределы списка, поскольку в этом случае вызов self. __list[index] возбудит исключение IndexError, что нам и требуется. def __getitem__(self, index): return self.__list[index] Этот метод обеспечивает поддержку синтаксиса x = L[n], где L – это от сортированный список, а n – целое число, определяющее номер пози ции в списке. def __setitem__(self, index, value): raise TypeError("use add() to insert a value and rely on " "the list to put it in the right place") Нам требуется предотвратить возможность изменения пользователем элемента списка в заданной позиции (то есть запретить возможность выполнения операции L[n] = x), так как в этом случае может нару шиться порядок сортировки элементов в списке. Как правило, чтобы показать, что операция не поддерживается тем или иным типом дан ных, используется исключение TypeError. def __iter__(self): return iter(self.__list) Этот метод легко реализовать, потому что мы можем просто вернуть итератор частного списка, используя встроенную функцию iter(). Этот метод используется для поддержки синтаксиса for value in iterable. Обратите внимание: когда объект интерпретируется как последова тельность, то используется именно этот метод. Так, чтобы преобразо вать объект L типа SortedList в простой список, можно вызвать функ цию list(L), в результате чего интерпретатор Python вызовет метод SortedList.__iter__(L) , чтобы получить последовательность, необходи мую функции list(). 320 Глава 6. Объектно/ориентированное программирование def __reversed__(self): return reversed(self.__list) Этот метод обеспечивает поддержку встроенной функции reversed(), благодаря чему мы можем записать, например, for value in reversed(it erable) def __contains__(self, value): index = self.__bisect_left(value) return (index < len(self.__list) and self.__list[index] == value) Метод __contains__() обеспечивает поддержку оператора in. И снова мы можем использовать быстрый алгоритм двоичного поиска вместо медленного алгоритма линейного поиска, используемого классом list. def clear(self): self.__list = [] def pop(self, index=1): return self.__list.pop(index) def __len__(self): return len(self.__list) def __str__(self): return str(self.__list) Метод SortedList.clear() отбрасывает существующий список и заме щает его новым пустым списком. Метод SortedList.pop() удаляет эле мент из указанной позиции и возвращает его или возбуждает исключе ние IndexError, если индекс находится за пределами списка. В методах pop() , __len__() и __str__() мы просто перекладываем работу на объект self.__list Мы не предусматриваем переопределение специального метода __repr__() , поэтому, когда для объекта L типа SortedList пользователь вызовет функцию repr(L), будет использоваться метод object. __repr__() базового класса. Он воспроизведет строку ' , но, конечно, с другим значением число вого идентификатора. Мы не можем предоставить иную реализацию метода __repr__(), потому что для этого пришлось бы представить в строке ключевую функцию, но у нас нет возможности создать репре зентативное представление ссылки на объект функцию в виде строки, которую можно было бы передать функции eval(). Мы не предусматриваем реализацию методов insert(), reverse() или sort() , потому что ни один из них не соответствует понятию сортиро ванного списка. Если попытаться вызвать какой либо из них, будет возбуждено исключение AttributeError. Если мы скопируем сортированный список, используя прием L[:], в результате будет получен объект типа list, а не типа SortedList. Простейший способ получить копию сортированного списка состоит Собственные классы коллекций 321 в том, чтобы импортировать модуль copy и воспользоваться функцией copy.copy() – она достаточно интеллектуальна, чтобы скопировать сор тированный список (и экземпляры большинства других классов) без какой либо помощи. Однако мы решили реализовать явный метод copy() : def copy(self): return SortedList(self, self.__key) Передавая в первом аргументе сам объект self, мы гарантируем, что будет создана лишь поверхностная копия self.__list вместо копирова ния и пересортировки. (Благодаря тому, что в методе __init__() при сутствует предложение elif, выполняющее проверку типа.) Теорети чески высокая скорость копирования таким способом недостижима для функции copy.copy(), однако мы легко можем исправить этот не достаток, добавив строку: __copy__ = copy Когда вызывается функция copy.copy(), она сначала пытается исполь зовать специальный метод __copy__() объекта и только в случае его от сутствия выполняет свой собственный программный код. Благодаря этой строке функция copy.copy() теперь сможет при работе с отсорти рованными списками использовать метод SortedList.copy(). (То же са мое возможно в случае реализации специального метода __deepco py__() , но это немного сложнее – электронная документация модуля copy содержит все необходимые подробности.) Теперь мы завершили реализацию класса SortedList. В следующем подразделе мы будем использовать объект класса SortedList для хране ния ключей класса SortedDict. Создание классов коллекций посредством наследования Класс SortedDict, который демонстрируется в этом подразделе, стре мится максимально имитировать поведение класса dict. Основное от личие между ними состоит в том, что ключи класса SortedDict всегда упорядочены в соответствии с заданной ключевой функцией или в со ответствии с функцией идентичности. Класс SortedDict предоставляет тот же API, что и класс dict (за исключением поддержки функции repr() , обеспечивающей возможность создания репрезентативной фор мы представления, пригодной для передачи функции eval()), плюс два дополнительных метода, которые имеют смысл только для упорядо ченной коллекции. 1 1 Класс SortedDict, представленный здесь, отличается от аналогичного клас са из написанной этим же автором книги «Rapid GUI Programming with Py thon and Qt», ISBN 0132354187, и от похожего класса в каталоге пакетов Python (Python Package Index). 322 Глава 6. Объектно/ориентированное программирование Ниже приводятся несколько примеров, дающих представление о том, как работает SortedDict: d = SortedDict.SortedDict(dict(s=1, A=2, y=6), str.lower) d["z"] = 4 d["T"] = 5 del d["y"] d["n"] = 3 d["A"] = 17 str(d) # вернет: "{'A': 17, 'n': 3, 's': 1, 'T': 5, 'z': 4}" В реализации класса SortedDict используются оба механизма – агреги рование и наследование. Сортированный список ключей агрегирован в виде переменной экземпляра, тогда как сам класс SortedDict наследу ет встроенный класс dict. Наше знакомство с классом мы начнем с рас смотрения инструкции class и метода инициализации, а затем пооче редно рассмотрим все остальные методы. class SortedDict(dict): def __init__ (self, dictionary=None, key=None, **kwargs): dictionary = dictionary or {} super().__init__(dictionary) if kwargs: super().update(kwargs) self.__keys = SortedList.SortedList(super().keys(), key) В инструкции class указан базовый класс dict. Метод инициализации пытается имитировать функцию dict(), но при этом имеет второй до полнительный аргумент, в котором передается ключевая функция. Вызов super().__init__() использует для инициализации объекта клас са SortedDict метод dict.__init__() базового класса. Точно так же, если методу были переданы именованные аргументы, вызывается метод dict.update() базового класса, чтобы добавить их в словарь. (Обратите внимание, что принимается только одно вхождение любого именован ного аргумента, поэтому ни один из ключей среди именованных аргу ментов kwargs не может быть «dictionary» или «key».) Копии всех ключей словаря сохраняются в сортированном списке – в переменной self.__keys. При инициализации сортированного списка ему передается список ключей словаря с помощью метода базового класса dict.keys() – мы не можем использовать метод SortedDict.keys(), потому что он опирается на использование переменной self.__keys, ко торая появится только после того, как будет создан сортированный список SortedList ключей. def update(self, dictionary=None, **kwargs): if dictionary is None: pass elif isinstance(dictionary, dict): super().update(dictionary) else: Собственные классы коллекций 323 for key, value in dictionary.items(): super().__setitem__(key, value) if kwargs: super().update(kwargs) self.__keys = SortedList.SortedList(super().keys(), self.__keys.key) Этот метод используется для добавления в словарь элементов другого словаря, или именованных аргументов, или и того и другого. Элемен ты, существующие только в другом словаре, добавляются в данный словарь, а если элементы с одинаковыми ключами присутствуют в обо их словарях, значения элементов другого словаря заместят значения элементов данного словаря. Мы несколько расширили поведение сло варя, так как сохраняем исходную ключевую функцию словаря, даже если другой словарь является объектом класса SortedDict. Добавление элементов выполняется в два этапа. Сначала выполняется добавление элементов словаря. Если другой словарь является объек том подкласса, наследующего класс dict (что, безусловно, относится и к классу SortedDict), добавление выполняется вызовом метода dict.up date() базового класса – здесь очень важно использовать метод базово го класса, потому что в случае вызова SortedDict.update() он попадет в бесконечную рекурсию. Если словарь не является объектом подклас са, наследующего класс dict, то выполняются итерации по его элемен там, и каждая пара ключ значение добавляется отдельно. (Если сло варь не является объектом подкласса, наследующего класс dict, и не имеет метода items(), совершенно справедливо будет возбуждено ис ключение AttributeError.) Если были переданы именованные аргумен ты, точно так же вызывается метод update() базового класса, чтобы до бавить их в словарь. В результате добавления элементов список self.__keys становится не действительным, поэтому мы замещаем его новым списком типа SortedList , образованным из ключей словаря (опять же используя ме тод базового класса, потому что метод SortedDict.keys() опирается на использование списка self.__keys, который находится в процессе об новления), используя оригинальную ключевую функцию сортирован ного списка. @classmethod def fromkeys(cls, iterable, value=None, key=None): return cls({k: value for k in iterable}, key) Интерфейс класса dict включает метод класса dict.fromkeys(). Этот ме тод используется для создания нового словаря на основе итерируемого объекта. Каждый элемент итерируемого объекта становится ключом, а значением каждого ключа становится None или значение аргумента value Так как это метод класса, первый его аргумент автоматически переда ется интерпретатором Python и является классом. Объекту класса dict |