[Tutor] How to find optimisations for code

[Peter Otten]

Mats Wichmann wrote:

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

This is probably retyped from memory. If the line were

string2 = string2.replace(i,"",1)

it would address your concern below about repeated chars.

>>> def contains(s, t):
...     for c in s:
...         if c not in t: return False
...         t = t.replace(c, "", 1)  # remove one occurence of c from t
...     return True
... 
>>> contains("ata", "attax")
True
>>> contains("tata", "attax")
True
>>> contains("tatat", "attax")  # not enough 't's
False

> 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.
> 
> 
> 
> _______________________________________________
> Tutor maillist  -  Tutor at python.org
> To unsubscribe or change subscription options:
> https://mail.python.org/mailman/listinfo/tutor