[Tutor] How to find optimisations for code

Pat Martin wpmartin at gmail.com
Fri Oct 19 13:50:22 EDT 2018


So should we always use sets or dictionaries if possible? Are these more
efficient because of not keeping track of their position?

On Fri, Oct 19, 2018 at 10:47 AM Pat Martin <wpmartin at gmail.com> wrote:

> That's correct sorry, I reassigned with replace back to string2, I forgot
> that in my retyping of the snippet.
>
> That makes sense, when it comes to strings and it taking so long. Thanks
> for explaining that.
>
> On Fri, Oct 19, 2018 at 10:09 AM Peter Otten <__peter__ at web.de> wrote:
>
>> 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
>>
>>
>> _______________________________________________
>> Tutor maillist  -  Tutor at python.org
>> To unsubscribe or change subscription options:
>> https://mail.python.org/mailman/listinfo/tutor
>>
>


More information about the Tutor mailing list