[Tutor] How to find optimisations for code

Mats Wichmann mats at wichmann.us
Fri Oct 19 12:40:06 EDT 2018

On 10/19/2018 10:12 AM, 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 think you've hit it in your last sentence ("except maybe write more
code and get more experience"): experience will let you recognize patterns.

> 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.

notwithstanding that the challenge is a little contrived... here's
something you will come to recognize.  You use the string replace
method, which is described thus, pasting from the official docs:

str.replace(old, new[, count])

Return a copy of the string with all occurrences of substring old
replaced by new. If the optional argument count is given, only the first
count occurrences are replaced.

Strings are not modifiable, so there is no replace-in-place.  Each time
you call string2.replace you build a new string... and then do nothing
with that string, as you never assign a name to it. So that line clearly
makes your code inefficient - you do some work that is just thrown away.
And it's not clear what the purpose of this replacement is, anyway.

Further it's not clear that you have the right answer.  What if string1
contains one 'r' and string2 contains three?  For the one 'r', the test
that it is also in string2 succeeds... but nowhere do you find out that
you actually needed to have three in order to be able to "rearrange to
make string2".

Solving this problem might benefit from thinking about tests first: if
you write a test where you know the answer is going to be negative, a
second where it is going to be positive, and a third that is a
non-trivial instance of positive (like the multiple-letter count), then
you have something to code your solution against. After it works, you
can then think about refactoring: is there a better way? This will kind
of naturally lead you to thinking in terms of efficiency.

Lesson 2: for very many tasks, someone has already done it, and you can
benefit by using some existing code, from the standard library or a
module installed separately.  That's often the difference between a
programming challenge, which may want you to code it yourself to show
you can, and real-world problem solving, where you are rewarded (in
time) by efficiently reusing existing code.

More information about the Tutor mailing list