This is so important I wish people would focus more on it. I recently rewrote some Javascript code in (pure) python and got a good 2 orders of magnitude speed up on large inputs just by picking the right data structures and replacing an O(n^3) nested loop with an O(n log n) approach.

We do scientific computing at my company. Numpy does 90% of the work, but there are some algorithms that just aren't easily expressed with arrays. That's where Cython comes in.

Numpy and scipy have been the core of a huge amount of my optimisations. The first question I try and ask is

"Could this be solved with matrix multiplications and summing?"

Often the answer is "yes" and allows you to group a huge amount of calculations all together, and use the heavily optimised code available numpy/scipy.

I recently swapped out something that was running at about 100 rows calculated/second to about half a million in about 0.2s.

  for k in dict.keys():
    ...

This has been 'fixed' in python3 and .keys() now returns an iterable view of the keys, and if you actually want a list of the keys you have to explicit and write list(dict.keys())

    for k in dict:
        ...

    if k in dict:
        ...

The equivalent python2 behaviour can be obtained using list(somedict.keys())

I tried a very simple toy program the other day and while I had to write some things slightly un-pythonically (it can't deal with syntax like a[:] = b+c yet), it performed practically as good as hand-written C code.

https://github.com/numba/numba