[Tutor] How to find optimisations for code

[Peter Otten]

Pat Martin wrote:

> Sorry my first email didn't have a subject line
> 
> TLDR; How do you figure out if code is inefficient (if it isn't
> necessarily obvious) and how do you find a more efficient solution?
> 
> I use code wars sometimes to get some practice with Python, there was a
> challenge to compare two strings and if string1 had enough characters to
> be rearranged to make string2 return True, otherwise return False.
> 
> I wrote a script that was like this:
> 
> for i in string1:
>     if i not in string2:
>         return False
>     string2.replace(i,"",1)
> return True
> 
> This worked but I kept getting that my function was too inefficient and it
> took too long. I did a search for the problem and found someone was using
> collections.Counter. This basically takes the string and returns the
> number of times each character occurs in it. Then just compare the count
> of one string to another to see if there is enough of each letter to make
> the other string. This seems like an elegant way to do it.
> 
> My question is, how do I know something is inefficient and more
> importantly how do I go about finding a more efficient solution?
> 
> I have just discovered dir() and it has really helped in finding methods
> for items but that doesn't help when finding actual packages especially if
> I don't know exactly what I am looking for.
> 
> Sorry about the long email, not sure if there is even an answer to this
> question except maybe write more code and get more experience?

In Python my rule of thumb is: replace lists and loops with dict and set 
lookups whenever possible. One small challenge with this pattern is that not 
all loops look like a loop:

char in some_string  # "slow"; have to loop through the whole string
char in set_of_chars # "fast"; calculate some hash value and then likely
                     # jump to the right set entry