Производительность Python deque для маленьких итераций

1

Я играл с Python collection.deque и написал следующий тест:

#!/usr/bin/python

import timeit

if __name__=='__main__':
    number = 1000000
    for r in (1,10,100,1000,5000,10000,100000):
        print r
        print timeit.timeit("while x: x.pop(0);",
                            "x = list(range("+str(r)+"))",
                            number=number)
        print timeit.timeit("while x: x.popleft();",
                            "from collections import deque; x = deque(range("+str(r)+"))",
                             number=number)

Это будет pop (0)/popleft() из списка /deque с различными размерами. Результаты:

1
0.0801048278809
0.0822219848633
10
0.081041097641
0.080836057663
100
0.0806250572205
0.0807700157166
1000
0.081248998642
0.082062959671
5000
0.0976719856262
0.0825741291046
10000
0.157499074936
0.0825819969177
100000
16.0247170925
0.097559928894

Мой вопрос: почему производительность для небольших требований и списков (~ 1000 элементов) почти одинакова?

  • 1
    Возможно, это связано с тем, что операторы import не являются бесплатными.
Теги:
performance
deque

3 ответа

4
Лучший ответ

Модуль timeit запускает код установки один раз, а затем временный код number раз (в этом случае number == 1000000). В вашем случае это выглядит как (для списка):

x = list(range(r))
#timer is started here
for iteration in xrange(1000000):
    while x: x.pop(0)
#timer is stopped here

Как вы можете видеть, только первая итерация делает что-либо, а остальные 999999 итераций будут просто проверять размер x один раз, так как он будет пустым. Эта проверка займет примерно такое же количество времени для списков и комментариев.

Для небольших списков /deques первая итерация коротка по сравнению с другими итерациями 999999, поэтому вы на самом деле ничего не измеряете и получаете одинаковые времена.

Если вы используете number==1, у вас не будет этой проблемы. Еще один вариант заключается в том, чтобы выставить импульс по времени и поместить элемент, чтобы список /deque оставался одного размера.

Поделиться
3

Я всегда нахожу timeit более подходящим для использования в командной строке оболочки. Здесь, например:

$ python -mtimeit -s'from collections import deque; base=range(100); ctr=list' 'x=ctr(base)' 'while x: x.pop(0)'
10000 loops, best of 3: 77.3 usec per loop
$ python -mtimeit -s'from collections import deque; base=range(100); ctr=deque' 'x=ctr(base)' 'while x: x.popleft()'
10000 loops, best of 3: 36 usec per loop

Необходимые меры предосторожности (выполнение импорта за пределами цикла, создание новой копии данных в цикле) гораздо проще увидеть и реализовать, таким образом...

Поделиться
2

Для небольшого числа элементов время, затрачиваемое на создание дека и списка, является значительным.

Как только число элементов f растет, это уже не является значимым в результатах.

Перепишите тест, чтобы конструкция списков была за пределами вызова timeit.

Изменить: Как указывает @Interjar, инициализация классов выполняется за пределами времени метода, поэтому это не является причиной аналогичных таймингов при малом количестве записей.

Поделиться
  • 1
    Это неверно: построение списка выполняется в параметре setup timeit , который не рассчитан.
  • 0
    @Interjay - Совершенно верно - я обновил ответ.

Ещё вопросы

Сообщество Overcoder
Наверх
Меню