Queues vs List

Cameron Simpson cs at zip.com.au
Fri Dec 25 18:19:15 EST 2009


On 25Dec2009 17:21, Rodrick Brown <rodrick.brown at gmail.com> wrote:
| Was reading the official python document and I noticed they mentioned queues
| being more efficient for adding/removing elements vs list so I wrote a quick
| test the validate this claim and I wasn't very impressed by the results it
| seems queues are just slightly faster so my question to the list, is deque
| used much in python over general lists?

A deque has O(1) behaviour for adding or removing elements from the
front or back of the deque. It has O(n) behaviour for lookups.

A list has O(n) behaviour for adding/removing, roughly. It has O(1)
behaviour for lookups. Removing from the front requires copying all
the higher elements down, for example. Adding to the end _may_ cost a
copy-the-whole-list if memory needs reallocating.

But your lists/deques are VERY small. A deque is a more complicated
structure (probably a linked list - I haven't checked). Its basic
operation is more expensive and for your test cases probably overwhlems
things. You need to use bigger test cases before the deque wins over the
list, and of course a deque is only better than a list of your program
has behaviour that is expensive for a list.

Cheers,
-- 
Cameron Simpson <cs at zip.com.au> DoD#743
http://www.cskk.ezoshosting.com/cs/

Team work is essential.  It gives the enemy other people to shoot at.
        - Murphy's Laws of Combat



More information about the Python-list mailing list