Первой проблемой, с которой можно столкнуться, начав использовать класс Set, оказывается производительность: его вложенные циклы for и проверки in замедляют выполнение с экспоненциальной скоростью. Библиотечные классы должны быть реализованы с максимально возможной эффективностью, иначе такая медлительность может оказаться весьма существенной для некоторых приложений.
Один из способов оптимизировать производительность множеств состоит в переходе к использованию словарей вместо списков для внутреннего хранения множеств — элементы могут храниться в виде ключей словаря, все значения в котором равны None. Так как время поиска в словарях постоянно и невелико, проверку в списке оператором in в первоначальном множестве в этой схеме можно заменить прямой выборкой из словаря. Говоря традиционным языком, при переходе к использованию словарей мы заменяем медлительный линейный поиск быстрыми хеш- таблицами. Программист мог бы пояснить, что повторяющееся сканирование списков в поисках пересечений является экс по нен ци аль ным алгоритмом, а выборка из словарей — ли нейным.
Эту идею реализует модуль в примере 18.11. Его класс является подклассом оригинального множества и переопределяет методы, связанные с внутренним представлением, но наследует остальные. Унаследованные методы перегрузки операторов & и | вызывают здесь новые методы intersect и union, а унаследованный метод len действует со словарями без изменений. Пока клиенты класса Set не зависят от порядка элементов в множестве, они могут непосредственно переключиться на эту версию, просто изменив имя модуля, из которого импортируется класс Set, — имя класса остается прежним.
Пример 18.11. PP4E\Dstruct\Basic\fastset.py
"оптимизация за счет применения линейного алгоритма сканирования по словарям"
import set
# fastset.Set расширяет set.Set
class Set(set.Set):
def __init__(self, value = []):
self.data = {} # управляет локальным словарем
self.concat(value) # хеширование: время поиска изменяется линейно
def intersect(self, other):
res = {}
for x in other: # other: последовательность или Set
if x in self.data: # поиск по хеш—таблицам; 3.X
res[x] = None
return Set(res.keys()) # новый экземпляр Set на основе словаря
def union(self, other):
res = {} # other: последовательность или Set
for x in other: # сканировать каждое множество только 1 раз
res[x] = None
for x in self.data.keys(): # ‘&’ и ‘|’ попадают сюда
res[x] = None # так они создают новые быстрые множества
return Set(res.keys())
def concat(self, value):
for x in value: self.data[x] = None
# inherit and, or, len
def __getitem__(self, ix):
return list(self.data.keys())[ix] # 3.X: вызов list() необходим
def __repr__(self):
return ‘<Set:%r>’ % list(self.data.keys()) # то же самое
Эта версия действует точно так же, как предыдущая, хотя ее внутренняя реализация радикально отличается:
> >> from fastset import Set
> >> users1 = Set([‘Bob’, ‘Emily’, ‘Howard’, ‘Peeper’])
> >> users2 = Set([‘Jerry’, ‘Howard’, ‘Carol’])
> >> users3 = Set([‘Emily’, ‘Carol’])
> >> users1 & users2
<Set:[‘Howard’]>
> >> users1 | users2
<Set:[‘Howard’, ‘Peeper’, ‘Jerry’, ‘Carol’, ‘Bob’, ‘Emily’]>
> >> users1 | users2 & users3
<Set:[‘Peeper’, ‘Carol’, ‘Howard’, ‘Bob’, ‘Emily’]>
> >> (users1 | users2) & users3
<Set:[‘Carol’, ‘Emily’]>
> >> users1.data
{‘Peeper’: None, ‘Bob’: None, ‘Howard’: None, ‘Emily’: None}
Главным функциональным отличием этой версии является порядок следования элементов в множестве: поскольку словари упорядочиваются произвольным образом, порядок будет отличаться от исходного. Более того, порядок следования может быть разным даже в разных версиях Python (фактически такая разница наблюдается между Python 2.X и 3.X в третьем и четвертом изданиях этой книги). Например, можно хранить в множествах составные объекты, но порядок элементов в этой версии отличается:
> >> import set, fastset
> >> a = set.Set([(1,2), (3,4), (5,6)])
> >> b = set.Set([(3,4), (7,8)])
> >> a & b
<Set:[(3, 4)]>
> >> a | b
> Set:[(1, 2), (3, 4), (5, 6), (7, 8)]>
> >> a = fastset.Set([(1,2), (3,4), (5,6)])
> >> b = fastset.Set([(3,4), (7,8)])
> >> a & b
<Set:[(3, 4)]>
> >> a | b
> Set:[(1, 2), (5, 6), (3, 4), (7, 8)]>
> >> b | a
> Set:[(1, 2), (5, 6), (3, 4), (7, 8)]>
Как бы то ни было, но от множеств не требуется упорядоченность, поэтому здесь нет никаких проблем. А вот отклонение, которое может иметь значение, состоит в том, что в этой версии нельзя хранить не хе- шируе мые объекты. Это следует из того, что ключи словаря должны быть неизменяемыми. Так как значения хранятся в ключах, множества, основанные на словарях, могут содержать только такие элементы, как кортежи, строки, числа и объекты классов, объявленные как неизменяемые. Изменяемые объекты, такие как списки и словари, нельзя использовать непосредственно в таких множествах на основе словарей, но можно в множествах оригинального класса. Однако в качестве составных элементов множеств вполне допустимо использовать кортежи, потому что они являются неизменяемыми — при их использовании интерпретатор будет вычислять хеш-значения и проверять равенство ключей, как обычно:
> >> set.Set([[1, 2],[3, 4]])
> Set:[[1, 2], [3, 4]]>
> >> fastset.Set([[1, 2],[3, 4]])
TypeError: unhashable type: ‘list’
> >> x = fastset.Set([(1, 2), (3, 4)])
>>> x & fastset.Set([(3, 4), (1, 5)])
<Set:[(3, 4)]>
Использованная литература:
Марк Лутц — Программирование на Python, 4-е издание, II том, 2011
