4 ms·

Why am I doing all these interviews that grill me on big O(n) if they’re not even using it?!

Tommah 3y ago
It is important to understand asymptotic complexity, but the places where it's useful in the real world are very different from textbook examples or Leetcode problems. You'll rarely have a triple loop in your code that makes you think, hmm, maybe I can reduce this to a double loop. That can happen, but these are more frequent problems I've seen: * Application code is issuing too many queries to the database. The classic N+1 problem is of this type. Another common problem is issuing one query for each item in a set, when an aggregate query could be issued instead. For example, suppose we have a database that contains students and exams, and every time a student takes an exam, a row is added to the table student_exam with the student id and the exam id. Now suppose that we want to build a dashboard that lists each exam and the number of students that took each exam. We could do this by iterating through the exam ids and querying SELECT COUNT(*) FROM student_exam WHERE exam_id = ? where we fill in the exam id as a parameter. But it will be faster to query SELECT exam_id, COUNT(*) FROM student_exam GROUP BY exam_id since this calculates the result in a single query. * Missing database indexes. A lot has been written about this, and it can cause a slowdown of N or N^2 times in some cases. Adding an index in the right place can change a linear scan into a much faster B-tree search. * Too much overhead. If your request handler is performing a small number of operations, but they include slow operations like making API calls over the network, then your handler will be slow, and network problems could make it even slower. If you’re writing Java code that has to make calls ten levels deep to get anything done, those levels of indirection aren’t free. * Using the wrong data structures, or using them suboptimally. If you want to determine whether two lists have an element in common, you could loop through both lists, but this will take O(mn) time. The faster way is to build a search structure out of one of the lists, then go through the other list and look for its elements in the search structure. For example, if your lists are A and B, you can build an AVL tree out of list A, call this tree T, then look for each element of B in T. This will run in O((m+n) log n) time. Using a hashtable works here too. Another common cause for slowdown is constructing a string by adding to its end repeatedly. This usually causes quadratic running time; it is better to build a list of strings and then concatenate them at the end. In the abstract, these cases are the same as having a double loop in your code; the difference is that the double loop isn’t in your code, it’s in library code or in the database’s code. So you should avoid writing code that is slow like this, but you should also avoid calling code in a way that will cause slowdowns. My third point is a little different from the rest; it’s not really talking about slowdowns by a factor of n, but by a large constant factor. When we’re talking about theory, we normally ignore the constant factors… but in the real world, those constants can matter a lot. This is why things like bitsets and B-trees are used. They only provide a constant factor improvement over regular sets and binary search trees respectively, but that constant factor sometimes matters a lot.
- Sohcahtoa82 3y ago
  > * Missing database indexes. A lot has been written about this, and it can cause a slowdown of N or N^2 times in some cases. Adding an index in the right place can change a linear scan into a much faster B-tree search. I can give a personal piece of anecdata on this. I was using a static application security testing tool on a huge repo (over 2M lines of code). It reported a couple thousand issues, nearly all of which were issues on code style rather than actual security issues. Generating a report would take literally 2 DAYS and would grind the database server so hard that any other use of the SAST suite had a noticeable impact. I decided to run a profiler and see what queries were hitting it so hard. Turns out there was a SELECT that was being used a lot, but the columns being searched weren't indexed. I don't remember the exact query, but I'm guessing it was searching all the code in the repo that was stored in the database repeatedly. I manually ran a CREATE INDEX. It took about a day for it to complete, and it added a couple gigabytes to the database. But now, those reports went from 2 days to about 20 minutes. > If you’re writing Java code that has to make calls ten levels deep to get anything done, those levels of indirection aren’t free. I'm of the opinion that any time you're performing type introspection, reflection, and ".invoke()", it's a code smell, but I suppose middleware in Java is impossible without them due to its draconian type system.

It is important to understand asymptotic complexity, but the places where it's useful in the real world are very different from textbook examples or Leetcode problems. You'll rarely have a triple loop in your code that makes you think, hmm, maybe I can reduce this to a double loop. That can happen, but these are more frequent problems I've seen: * Application code is issuing too many queries to the database. The classic N+1 problem is of this type. Another common problem is issuing one query for each item in a set, when an aggregate query could be issued instead. For example, suppose we have a database that contains students and exams, and every time a student takes an exam, a row is added to the table student_exam with the student id and the exam id. Now suppose that we want to build a dashboard that lists each exam and the number of students that took each exam. We could do this by iterating through the exam ids and querying SELECT COUNT(*) FROM student_exam WHERE exam_id = ? where we fill in the exam id as a parameter. But it will be faster to query SELECT exam_id, COUNT(*) FROM student_exam GROUP BY exam_id since this calculates the result in a single query. * Missing database indexes. A lot has been written about this, and it can cause a slowdown of N or N^2 times in some cases. Adding an index in the right place can change a linear scan into a much faster B-tree search. * Too much overhead. If your request handler is performing a small number of operations, but they include slow operations like making API calls over the network, then your handler will be slow, and network problems could make it even slower. If you’re writing Java code that has to make calls ten levels deep to get anything done, those levels of indirection aren’t free. * Using the wrong data structures, or using them suboptimally. If you want to determine whether two lists have an element in common, you could loop through both lists, but this will take O(mn) time. The faster way is to build a search structure out of one of the lists, then go through the other list and look for its elements in the search structure. For example, if your lists are A and B, you can build an AVL tree out of list A, call this tree T, then look for each element of B in T. This will run in O((m+n) log n) time. Using a hashtable works here too. Another common cause for slowdown is constructing a string by adding to its end repeatedly. This usually causes quadratic running time; it is better to build a list of strings and then concatenate them at the end. In the abstract, these cases are the same as having a double loop in your code; the difference is that the double loop isn’t in your code, it’s in library code or in the database’s code. So you should avoid writing code that is slow like this, but you should also avoid calling code in a way that will cause slowdowns. My third point is a little different from the rest; it’s not really talking about slowdowns by a factor of n, but by a large constant factor. When we’re talking about theory, we normally ignore the constant factors… but in the real world, those constants can matter a lot. This is why things like bitsets and B-trees are used. They only provide a constant factor improvement over regular sets and binary search trees respectively, but that constant factor sometimes matters a lot.

Sohcahtoa82 3y ago
> * Missing database indexes. A lot has been written about this, and it can cause a slowdown of N or N^2 times in some cases. Adding an index in the right place can change a linear scan into a much faster B-tree search. I can give a personal piece of anecdata on this. I was using a static application security testing tool on a huge repo (over 2M lines of code). It reported a couple thousand issues, nearly all of which were issues on code style rather than actual security issues. Generating a report would take literally 2 DAYS and would grind the database server so hard that any other use of the SAST suite had a noticeable impact. I decided to run a profiler and see what queries were hitting it so hard. Turns out there was a SELECT that was being used a lot, but the columns being searched weren't indexed. I don't remember the exact query, but I'm guessing it was searching all the code in the repo that was stored in the database repeatedly. I manually ran a CREATE INDEX. It took about a day for it to complete, and it added a couple gigabytes to the database. But now, those reports went from 2 days to about 20 minutes. > If you’re writing Java code that has to make calls ten levels deep to get anything done, those levels of indirection aren’t free. I'm of the opinion that any time you're performing type introspection, reflection, and ".invoke()", it's a code smell, but I suppose middleware in Java is impossible without them due to its draconian type system.