3 ms·
We had one of those, except it was two loops and a python "in" on a list, so actually O(n^3). Changing the "in" to be on a set brought it from around two hours
by Izkata 1y ago
We had one of those, except it was two loops and a python "in" on a list, so actually O(n^3). Changing the "in" to be on a set brought it from around two hours to around five minutes. And the best part is related to the topic at hand: This was a small postprocessing function, and other more experienced developers had tried to speed up the overall process but assumed the slowness was earlier in the process instead of in this function, and after failing they assumed it couldn't be sped up further. They never bothered to check which part of the process was actually slow.
- sfn42 1y agoNice work! The example I used was based on a report I looked at once. The two lists were 50k and 80k elements respectively, the report took nearly 30 minutes to generate. Changing two lines of code to make a dictionary instead of a list and then use the dictionary instead of linear search brought it from 30 minutes to 5. Could probably have optimized it even more but it wasn't my task so I just left it at that. Nice improvement for a few minutes of work. I've seen the same mistake and similar ones many times, though usually the inputs aren't large enough to have that much of an impact. Still usually worth fixing though. It's kind of astounding how few people seem to understand these things. We all (me and my colleagues who are generally university educated) learned about complexity analysis, algorithms and data structures, but it seems like quite few actually understood the material.