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

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

1 голос
/ 16 января 2010

Я играл с Python's 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 элементов) почти одинакова?

Ответы [ 3 ]

4 голосов
/ 16 января 2010

Модуль 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 один раз, так как он будет пустым. Эта проверка займет примерно столько же времени для списков и запросов.

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

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

3 голосов
/ 16 января 2010

Я всегда нахожу 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 голосов
/ 16 января 2010

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

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

Переписать тест так, чтобы построение списков находилось за пределами вызова timeit.

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

...