Добились ли мы оптимизации? Напомню еще раз, что ожидания не всегда соответствуют действительности, хотя алгоритмическая сложность данной реализации выглядит веским основанием. Чтобы убедиться, в примере 18.12 приводится сценарий, сравнивающий производительность классов множеств. Он повторно использует модуль timer из примера 18.6, с помощью которого ранее сравнивались различные реализации стеков (наш программный код может реализовывать различные объекты, но это никак не влияет на порядок измерения времени).
Пример 18.12. PP4E\Dstruct\Basic\settime.py
"сравнение производительности альтернативных реализаций множеств" import timer, sys import set, fastset
def setops(Class): # 3.X: использование range вполне допустимо
a = Class(range(50)) # множество из 50 целых чисел
b = Class(range(20)) # множество из 20 целых чисел
c = Class(range(10)) d = Class(range(5)) for i in range(5):
t = a & b & c & d # 3 пересечения
t = a | b | c | d # 3 объединения
if __name__ == ‘__main__’: rept = int(sys.argv[1]) print(‘set => ‘, timer.test(rept, setops, set.Set)) print(‘fastset =>’, timer.test(rept, setops, fastset.Set))
Функция setops создает четыре множества и пять раз обрабатывает их операторами пересечения и объединения. Число повторений всего процесса определяется аргументом командной строки. Точнее, при каждом вызове setops создается 34 экземпляра Set (4 + [5 х (3 + 3)]) и выполняются методы intersect и union по 15 раз каждый (5 х 3) в теле цикла for.
На этот раз на том же самом ноутбуке с Windows 7 и Python 3.1 был достигнут резкий прирост производительности:
C:\…\PP4E\Dstruct\Basic> python settime.py 50 set => 0.637593916437 fastset => 0.20435049302
C:\…\PP4E\Dstruct\Basic> python settime.py 100 set => 1.21924758303 fastset => 0.393896570828
C:\…\PP4E\Dstruct\Basic> python settime.py 200 set => 2.51036677716 fastset => 0.802708664223
Результаты во многом зависят от общего быстродействия компьютера и могут отличаться в разных версиях Python. Но, по крайней мере в этом контрольном примере, реализация множества на основе словаря (fastset) оказалась втрое быстрее, чем реализация множества на основе списка (set). На самом деле такое троекратное ускорение вполне объяснимо. Словари Python уже являются оптимизированными хеш-таблицами, усовершенствовать которые еще больше весьма затруднительно. Пока не появится свидетельств того, что основанные на словарях множества все же слишком медлительны, наша работа здесь закончена.
Для сравнения, результаты, полученные в Python 2.4 в предыдущем издании этой книги, показывали во всех тестах шестикратный прирост скорости реализации fastset по сравнению с реализацией set. Отсюда можно сделать вывод, что в Python 3.X либо увеличилась скорость выполнения итераций, либо замедлилась скорость работы словарей. В еще более старой версии Python 1.5.2, во втором издании книги, были получены точно такие же относительные результаты, как в современной версии Python 3.1. В любом случае, это подчеркивает тот факт, что вам обязательно следует самостоятельно провести тестирование на своем компьютере и со своей версией Python — нынешние результаты тестирования производительности Python легко могут стать основой для анекдотов в будущем.
Использованная литература:
Марк Лутц — Программирование на Python, 4-е издание, II том, 2011
