On 25Dec2009 17:21, Rodrick Brown <rodrick.br...@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 <c...@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 -- http://mail.python.org/mailman/listinfo/python-list
