deque vs list: performance notes

Courageous jkraska1 at san.rr.com
Tue May 30 00:46:43 EDT 2000


A C-native bidirectionally linked list (deque) was
tested versus the performance of native python lists
as a LIFO. Items were appended to the end of each
data structure, but always removed from the beginning.

Sets of 10, 100, 1,000, 10,000, and 100,000 objects
were tested and timed against each data structure.
In both cases, each datastructure was iteratively
appended until the test count was reached, and then
iteratively popped from the head until empty.

Each test run was performed within a function which
was then invoked by the profile module; tottime for
function invocation was recorded:

Results:

#              deque(tottime)            list(tottime)

10                         .004                    .004
100                        .004                    .004
1,000                      .10                     .24
10,000                     .12                    1.18
100,000                   1.14                  129.01

Conclusions:

For FIFO datastructures involving smaller sets of objects
(10-100), which are, in all likelihood typical container
size for average programs, execution times were dominated
by function call, loop control, and python interpreter
overhead (inferred).

Because pyton lists are implemented as dynamic resizeable
arrays, python lists guarantee O(1)+k complexity for
append and delete from the tail, but provide O(n)+k
overhead for inserting/removing at the head.

In contrast, the deque implementation guarantees O(1)+k
complexity for add/delete operations at both head and
tail. The cost, therefore of removing all n members from
a deque is O(n), while the cost of removing all n members
from a python list is O(n!).

As a matter of practice, however, the theoretical
mathematical limits of these algorithms are not the
limiting factors for smaller/average-sized containers
of these types. It should be noted that this author
deliberately selected a practical problem in which
he knew python lists would perform poorly, and yet
for everyday programming problems, this turned out
not to matter much.


Joe Kraska
San Diego
Ca



More information about the Python-list mailing list