Ниже приводятся некоторые результаты, которые были получены с помощью управляющего сценария. В трех тестах было получено время в секундах для трех реализаций: оригинальной, на основе кортежей и на основе непосредственного изменения списка в памяти. Для каждой разновидности стека тест создает 200 экземпляров стека и выполняет примерно 120 000 операций со стеком (200 повторов х (200 операций проталкивания в стек + 200 обращений по индексу + 200 операций выталкивания со стека)) в течение указанного в результатах времени. Эти результаты были получены на очень медлительном ноутбуке, работающем под управлением Windows 7, в Python 3.1. Как обычно, у вас могут получиться иные результаты.
C:\…\PP4E\Dstruct\Basic> python stacktime.py 200 200 200
stack2: 0.838853884098
stack3: 2.52424649244
stack4: 0.215801718938
C:\…\PP4E\Dstruct\Basic> python stacktime.py 200 50 200
stack2: 0.775219065818
stack3: 2.539294115
stack4: 0.156989574341
C:\…\PP4E\Dstruct\Basic> python stacktime.py 200 200 50
stack2: 0.743521212289
stack3: 0.286850521181
stack4: 0.156262000363
C:\…\PP4E\Dstruct\Basic> python stacktime.py 200 200 0
stack2: 0.721035029026
stack3: 0.116366779208
stack4: 0.141471921584
Если внимательно посмотреть, то можно заметить по результатам, что стек, основанный на кортежах (stack3), показывает лучшую производительность, когда производится больше операций проталкивания в стек и выталкивания со стека, но оказывается хуже, когда производится много обращений по индексу. Операция обращения по индексу происходит очень быстро для встроенных списков (stack2 и stack4), но очень медленно для деревьев кортежей — класс Python вынужден вручную выполнять обход дерева.
Стеки, основанные на непосредственной модификации списка в памяти (stack4), поч ти всегда действуют быстрее всего, кроме случаев, когда вообще не выполняется никаких операций обращения по индексу — в последнем тесте кортежи (stack3) победили с небольшим перевесом. При отсутствии операций обращения по индексу, как в последнем тесте, реализации на основе кортежей и на основе непосредственной модификации списка в памяти оказываются примерно в шесть и в пять раз быстрее, чем простая реализация на основе списка соответственно. Поскольку операции проталкивания в стек и выталкивания со стека являются основными операциями, необходимыми клиентам от стека, кортежи являются претендентом на победу, несмотря на слабую производительность при обращении по индексу.
Конечно, мы говорим о долях секунды после многих десятков тысяч операций. Во многих приложениях пользователи могут не почувствовать разницы. Однако если программа обращается к стеку миллионы раз, эта разница может стать весьма существенной.
Использованная литература:
Марк Лутц — Программирование на Python, 4-е издание, II том, 2011
