3 ms·

The underlying lesson here is having a process to identify hotspots (profile), and then being able to swap one data structure for a contextually better one (pol

The underlying lesson here is having a process to identify hotspots (profile), and then being able to swap one data structure for a contextually better one (polymorphic collections). Presumably the developer of the topological sort was operating on small graphs where time complexity was not an issue. Its better to have the inefficient but numerically correct algorithm at hand than no implementation at all. So I don't think the author of the original topological sort has make a mistake. The best method for developing high performance algorithms is write the least error prone implementation first, with no eye on efficiency. Then build a separate high performance implementation. You test the second one is working by blowing random data into both and double check the fast one computes the same thing as the simple to understand implementation. That's how I built a persistent red-black tree over a space of two weeks[1] 1: http://wiki.edinburghhacklab.com/persistentredblacktreeset http://wiki.edinburghhacklab.com/persistentredblacktreeset

jeffasinger 13y ago
I wonder if it would be possible for a sufficiently intelligent compiler to do this automatically.
bunderbunder 13y ago
The author might not have even chosen an inefficient implementation. For smal sets of data, arrays can easily be faster at search and insertion than hash tables, particularly if the hash function or collision resolution scheme is inefficient. X having a higher growth rate than Y does not mean that Y is unconditionally faster. It means that there exists some problem size n such that Y is faster than X for all problems larger than n. Below that value, all those terms that big-O notation ignores are still significant performance factors.
xixi77 13y ago
While we should avoid premature optimizations, it is quite important to keep efficiency considerations in mind from the beginning. If we are talking about internal workings of one isolated function, fine -- but quite often a data structure picked "with no eye on efficiency" early on gets baked into the rest of the code so deep that by the time it becomes a problem, only extensive refactoring and debugging can get it out of there. And quite often the error-proneness of the more efficient data structure is no worse -- the classic structure-of-arrays vs. array-of-structures question is one example.

jeffasinger 13y ago

I wonder if it would be possible for a sufficiently intelligent compiler to do this automatically.

bunderbunder 13y ago

The author might not have even chosen an inefficient implementation. For smal sets of data, arrays can easily be faster at search and insertion than hash tables, particularly if the hash function or collision resolution scheme is inefficient. X having a higher growth rate than Y does not mean that Y is unconditionally faster. It means that there exists some problem size n such that Y is faster than X for all problems larger than n. Below that value, all those terms that big-O notation ignores are still significant performance factors.

xixi77 13y ago

While we should avoid premature optimizations, it is quite important to keep efficiency considerations in mind from the beginning. If we are talking about internal workings of one isolated function, fine -- but quite often a data structure picked "with no eye on efficiency" early on gets baked into the rest of the code so deep that by the time it becomes a problem, only extensive refactoring and debugging can get it out of there. And quite often the error-proneness of the more efficient data structure is no worse -- the classic structure-of-arrays vs. array-of-structures question is one example.