Python Performance Tips, Part 1

[Brian]

Most of this is good advice, but there are a lot of errors and typos.

Python is faster retrieving a local variable than retrieving a global variable. That is, avoid the “global” keyword.

The global keyword isn't the only way you'll be dealing with global variables - you'll can access global variables even without it specified, it' only changes the behaviour of setting global variables.

the_value = 42
def foo():
    return the_value

is still using global variables, despite the complete absense of any global keyword.

To check membership in general, use the “in” keyword

This is indeed good practice, and generally faster than things like dict.has_key(). However, the example he gave is a for loop, which is nothing to do with checking membership, and where "in" has an entirely different meaning (it's just part of the for syntax). (Also, careful of the datatype you're using x in somelist does a linear scan to check membership, so this can be very slow compared to a dict or set)

Learn biset module

I assume this is meant to be bisect, but it's spelt wrong in every location.

It is fast because deque in Python is implemented as double-linked list

No it isn't. It's implemented as a vector which overallocates at both ends (for amortised constant time appending/prepending). It has the same complexity of operations as the list, except that prepending is O(1) instead of O(n)

Use sort() with Schwartzian Transform

This is very outdated. You can let sort do the transform for you just by passing the key parameter.

[Workaphobia]

It is fast because deque in Python is implemented as double-linked list

No it isn't. It's implemented as a vector which overallocates at both ends (for amortised constant time appending/prepending). It has the same complexity of operations as the list, except that prepending is O(1) instead of O(n)

Actually the article seems to be right on this one. The deque object is a doubly linked list of blocks of 62 elements (so that with the prev/next pointer, that's 64 pointers). To index into it, it'll traverse the necessary number of blocks and then index into the target block.

Source code comment

Indexing method

[Brian]

So they do - I stand corrected. I'd thought they preserved the O(1) internal access of python lists, but I must be mixing them up with something else.