python tip

O(1) vs O(N) dictionary `in` search.

I recently came across this and it made a huge difference in some of my programs. I figured the issue was just because I was a noob, but I found it (via a grep search) in tons of other production codes.If you're interested in seeing if a dictionary, mydict has the key, 'mykey', the following is O(N): if 'mykey' in mydict.keys(): # do stuffwhile the following is O(1): if 'mykey' in mydict: # do stuffThis is because the dictionary will use a hash-lookup with the latter (like searching a set) while the former will first generate a list and then iterate over it for the in statement (so it may scale as 2N but that is still O(N)).By the way, these are based on average case. See Time Complexity for more detail.