Algorithms are important but are especially powerful in combination of knowing computer architecture and programming language intricacies.
Many years ago I was asked to look at the program written in C++ that calculated Kendall-tau correlation matrix for a large amount of data. Basically Kendall Tau is a robust replacement for Pearson correlation and it had to be calculated for 0.5M^2 elements and calculation of each element needed calculation of Kendall Tau on two series of numerical data of length N. Both M and N were on an order of few thousand and naive implementation has the complexity O(N^2 x M^2). The program ran for 6+ hours.
After looking at C++ I realized that a lot of time is spent just copying data needlessly (a result of not knowing the difference between passing a vector and reference to it) and needless memory allocations and deallocations. I did a rewrite from scratch, keeping the tests, but not copying anything and allocating a minimum amount of memory only once, employing the cache locality, spreading the calculation with OpenMP and finally - realizing that Kendall Tau can be done in O(M^2 x Nlog(N)) I found that out on my own, just by squinting and realizing that calculation of Kendall tau for two series is essentially sorting, but later found out that e.g. scipy implementation uses the same approach.
The resulting program ran for 4 minutes on a 2-core and 4 threads.
Many years ago I was asked to look at the program written in C++ that calculated Kendall-tau correlation matrix for a large amount of data. Basically Kendall Tau is a robust replacement for Pearson correlation and it had to be calculated for 0.5M^2 elements and calculation of each element needed calculation of Kendall Tau on two series of numerical data of length N. Both M and N were on an order of few thousand and naive implementation has the complexity O(N^2 x M^2). The program ran for 6+ hours.
After looking at C++ I realized that a lot of time is spent just copying data needlessly (a result of not knowing the difference between passing a vector and reference to it) and needless memory allocations and deallocations. I did a rewrite from scratch, keeping the tests, but not copying anything and allocating a minimum amount of memory only once, employing the cache locality, spreading the calculation with OpenMP and finally - realizing that Kendall Tau can be done in O(M^2 x Nlog(N)) I found that out on my own, just by squinting and realizing that calculation of Kendall tau for two series is essentially sorting, but later found out that e.g. scipy implementation uses the same approach.
The resulting program ran for 4 minutes on a 2-core and 4 threads.