3 ms·
Well said. Another example of this is using the right algorithm for the job. I see a lot of code like let's say you have two lists and you need to go through t
by sfn42 1y ago
Well said.
Another example of this is using the right algorithm for the job. I see a lot of code like let's say you have two lists and you need to go through the first one and find the corresponding element by id in the second. The naive implementation uses linear search of the second list, making the algorithm O(n^2). This will stall and take hours, days or longer to run when the lists get large, say into the tens to hundreds of thousands of elements.
If both lists come from your own database then you should have used a foreign key constraint and had the database join them for you. If you can't do that, let's say one or both lists come from a third-party api, you can create a dictionary(hashmap) of the second list to allow O(1) lookup rather than O(n) which brings your full algorithm's complexity to O(n). Now the you can have millions of elements and it'll still run in milliseconds or seconds. And if this is something you need to do very often then consider storing the second list in your database so you can use a join instead. Avoid doing the work, as you say.
These are the most common mistakes I see people make. That and situations where you make one request, wait for a response, then use that to make another request, wait for response and so on.
You don't need a profiler to avoid this type of problem, you just need to understand what you're doing at a fundamental level. Just use a dictionary by default, it doesn't matter if it might be slightly slower for very small inputs - it'll be fast enough and it'll scale.
- sgarland 1y agoRelated, people not understanding that the latency alone from a DB call (especially when the DB has network-based storage, which is most of the cloud offerings) is substantial. I’ve found so many cases where people are unknowingly doing serialized queries because the ORM obscured everything, and they didn’t realize they could get everything in a single query with joins.
- sfn42 1y agoYeah, I have that problem right now. A colleague and I recently took over development of an application that two others have started. It's not even in prod yet but everything is slow. Loading a page can take up to a minute. The reason for this is they have a frontend where they do stuff like let a = await fetchA(); let b = await fetchB(a.id); let c = await fetchC(b.id); // ... This on its own is obviously slow. But then you look at the backend code and it turns out the backend code for A, B and C also do this same kind of thing. Even worse, it's fetching way more data than is actually needed so even a single request is quite slow simply because there's a lot of data. And worse yet, it's fetching the data in a shape that is completely wrong for the application, so the frontend has thousands of lines of code that reshapes the data before it can be used - making things even slower, and making our jobs difficult because it's really hard to wrap your head around everything that's happening. And there's no technical reason for it, it doesn't have to be like this. We're working on refactoring it at the moment, we have a deadline approaching quite fast so we don't really want to spend time refactoring but the system they've created is complete ass and we eventually decided we have to spend the time to refactor now. It'll be much more difficult to fix the database schema and such when we're in prod and need to worry about losing data.
- Izkata 1y agoWe 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.