Hacker News Reader

Hacker News

Comment by cygnus_a | Hacker News Reader

Parent Full thread

cygnus_a

Actually, even the subsection headings in bold give a very succinct summary:

- Python has easy development (https://xkcd.com/353/)

- Great libraries (ie, free matlab)

- Cython for efficiency via C

- The algorithms themselves determine speediness (ie numerical methods)

View on HN

The algorithms themselves determine speediness

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.

Which data structures did you use? In Python, I tend to rely on dict, list, and set for 90% or more of my code. I wouldn't want to rely on structures written in pure Python.

Nothing exotic. One of the changes for example was replacing a list of list with a set of tuples, which greatly sped up checking if an object was in the collection. Another change was using a generator comprehension and an included itertool function rather than hand rolled nested for loops.

Once you've exhausted all the low-hanging fruit, like people calling .keys() on dicts, or doing unnecessary linear searches, Cython really starts to shine. I've seen it perform ~40 times better than pure Python in time-consuming loops.

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.

Can you explain the context in which .keys() is called often and is not appropriate and the alternative?

.keys() returns a list (in python2) so if you write

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

then python first builds a list of all the keys, loops through them and then throws away the list. If the dict is large, this can be quite expensive. The correct way is to either use .iterkeys() which returns an iterator which generates the keys one at a time, or simply iterate directly over the dict, saving you need to first copy all the keys into a list you'll just throw away.

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())

The easiest is to never use .keys() or .iterkeys(), and always iterate over the bare dict:

    for k in dict:
        ...

    if k in dict:
        ...

If you do need a list of keys, list(dict) has the advantage of working in both Python 2 and 3.

Just to clarify your python 2 note: In python 3 keys() returns an iterator, so there is no penalty (i.e. iterkeys was dropped, keys assumed iterkeys interface).

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

> Numpy does 90% of the work

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.

In fairness, I should point out that the really slow version was also written by me :)

http://www.vetta.org/2008/05/scipy-the-embarrassing-way-to-c... ;)

Fantastic!

Have you written a blog post about this? If not, care to? Trying to speed up a codebase, it's of interest to me (and no doubt others too).

Yes, this is actually one of the rare moments where I find my past background in competitive programming helpful. There's a habit I've picked up of constantly running through techniques to speed up whenever I'm coding. Not necessarily the most efficient way to code, but it's a habit difficult to change.

Let me just add Numba to the list. It compiles numpy-using code to native via llvm and can remove temporary arrays in the process.

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.

If your code falls within the subset it supports :) I've not yet got it to run our code in nopython mode - I think the latest problem is a function expecting a function as an argument, but the error messages aren't helpful or enlightening, even with DEBUG turned on.

The dev team is pretty responsive and prioritize adding features based on bug reports like this. Can you open an issue?

https://github.com/numba/numba

Just typed "import antigravity" in python repl. It took me to the same link. :-)

Reply on news.ycombinator.com