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