How to improve Python code speed

Question

I was solving this python challenge http://coj.uci.cu/24h/problem.xhtml?abb=2634 and this is my answer

c = int(input())
l = []
for j in range(c) :
    i = raw_input().split()[1].split('/')
    l.append(int(i[1]))
for e in range(1,13) :
    print e , l.count(e)

But it was not the fastest python solution, so i tried to find how to improve the speed and i found that xrange was faster than range. But when i tried the following code it was actually slower

c = int(input())
l = []
for j in xrange(c):
    i = raw_input().split()[1].split('/')[1]
    l.append(i)
for e in xrange(1,13) :
    print e , l.count(`e`)

so i have 2 questions :

1. How can i improve the speed of my script
2. Where can i find information on how to improve python speed

When i was looking for this info i found sites like this one https://wiki.python.org/moin/PythonSpeed/PerformanceTips but it doesn't specify for example, if it is faster/slower to split a string multiple times in a single line or in multiple lines, for example using part of the script mentioned above :

i = raw_input().split()[1].split('/')[1]

vs

i = raw_input().split()
i = i[1].split('/')
i = i[1]

Edit : I have tried all your suggestions but my first answer is still the fastest and i don't know why. My firs answer was 151ms and @Bakuriu's answer was 197ms and my answer using collections.Counter was 188ms.

Edit 2 : Please disregard my last edit, i just found out that the method for checking your code performance in the site mentioned above does not work, if you upload the same code more times the performance is different each time, some times it's slower and sometimes faster

Solution

Assuming you are using CPython, the golden rule is to push as much work as possible into built-in functions, since these are written in C and thus avoid the interpreter overhead.

This means that you should:

• Avoid explicit loops when there is a function/method that already does what you want
• Avoid expensive lookups in inner loops. In rare circumstances you may go as far as use local variables to store built-in functions.
• Use the right data structures. Don't simply use lists and dicts. The standard library contains other data types, and there are many libraries out there. Consider which should be the efficient operations to solve your problem and choose the correct data structure
• Avoid meta-programming. If you need speed you don't want a simple attribute lookup to trigger 10 method calls with complex logic behind the scenes. (However where you don't really need speed metaprogramming is really cool!)
• Profile your code to find the bottleneck and optimize the bottleneck. Often what we think about performance of some concrete code is completely wrong.
• Use the dis module to disassemble the bytecode. This gives you a simple way to see what the interpreter will really do. If you really want to know how the interpreter works you should try to read the source for PyEval_EvalFrameEx which contains the mainloop of the interpreter (beware: hic sunt leones!).

Regarding CPython you should read An optimization anecdote by Guido Van Rossum. It gives many insights as to how performance can change with various solutions. An other example could be this answer (disclaimer: it's mine) where the fastest solution is probably very counter intuitive for someone not used to CPython workings.

An other good thing to do is to study all most used built-in and stdlib data types, since each one has both positive and negative proporties. In this specific case calling list.count() is an heavy operation, since it has to scan the whole list every time it is performed. That's probably were a lot of the time is consumed in your solution.

One way to minimize interpreter overhead is to use collections.Counter, which also avoids scanning the data multiple times:

from collections import Counter

counts = Counter(raw_input().split('/')[-2] for _ in range(int(raw_input())))

for i in range(1, 13):
    print(i, counts[str(i)])

Note that there is no need to convert the month to an integer, so you can avoid those function calls (assuming the months are always written in the same way. No 07 and 7).

Also I don't understand why you are splitting on whitespace and then on the / when you can simply split by the / and take the one-to-last element from the list.

An other (important) optimization could be to read all stdin to avoid multiple IO calls, however this may not work in this situation since the fact that they tell you how many employees are there probably means that they are not sending an EOF.

---

Note that different versions of python have completely different ways of optimizing code. For example PyPy's JIT works best when you perform simply operations in loops that the JIT is able to analyze and optimize. So it's about the opposite of what you would do in CPython.

Comments

[Charles Duffy]

Trying to microoptimize rather than trying to improve your algorithm overall is, generally speaking, Doing It Wrong. Any formulaic document on "improving Python speed" would, necessarily, consist principally of microoptimizations, because large-scale algorithmic improvements aren't Python-specific in any way. If you care so much about constant-factor improvements that implementation details matter, Python is the wrong language to be using anyhow.

[roippi]

You are probably just looking at OS timing artifacts, the difference between range and xrange on 13 elements is tiny. The reason your script is slow is that you are calling count in a loop. You should build up a proper counter (by, say, using a collections.Counter) instead.

[Xirion11]

Thanks! It did'nt cross my mind to use that -2, i guess i was so fixated on having a pair in each input that i did'nt see that possibility. I'm just starting in this challenges so i have much to learn.