6 ms·

Please do note that, depending on the dataset size, it may be faster to just use a plain old binary heap. In this case, the big O cost for Dijkstra's algorithm

Please do note that, depending on the dataset size, it may be faster to just use a plain old binary heap. In this case, the big O cost for Dijkstra's algorithm is O((E + V) log V), as opposed to the better O(E + V log V) for a Fibonacci heap. Note, also, that Fibonacci heap operations are amortized time, so if you're not operating on a large enough dataset, the costs will not amortize enough and you may end up with a slower real time. A binary heap also has better locality of reference, because you have more chances of a cache hit, especially when you're near the root. The Fibonacci heap, in contrast, keeps a number of pointers to memory locations that are all allocated on-the-go and possibly very far apart. If the binary heap is implemented as a B-heap, as described by PHK [1], it can be made even faster. My point is: please benchmark. Always benchmark. "Stupid" algorithms and data structures may work much better for your case than you would have thought. Programmers are notoriously bad at finding the real bottlenecks... so please benchmark and profile. Fibonacci heaps, AVL trees, KMP, Coppersmith-Winograd, these are all little works of art and theoretically great solutions. With big data, they will perform better than more naive solutions. But that big data doesn't happen as often as you might think. Computers are weird, have too many quirks, and their operation will surprise you, no matter how skilled you are. So profile your programs. [1]: http://queue.acm.org/detail.cfm?id=1814327 http://queue.acm.org/detail.cfm?id=1814327

mtdewcmu 12y ago
Another good reason to try a binary heap: it would have only taken a few hours to implement. Then you can do some benchmarking, count your gains, and perhaps quit while you're still ahead. Profiling is good, but I don't see how it would have helped her in this case. In order to profile the Fibonacci heap, you'd have to implement it first. She mentioned that it took twice as long as the original algorithm, and timing is a simple form of profiling, so she basically did profile (after implementing it). What would have helped is intuition about algorithms and the ability to estimate how fast they'll be without having to implement and time them. This was a good exercise for developing that intuition. It's useful to keep in mind that O(log n) is effectively O(1) in the real world, because on actual computers, integers are bounded by 2^64, which means that any logarithmic factor will be <= 64 (or some constant). When O(n) and O(n log n) algorithms differ in practical performance, the asymptotic difference is not usually the best explanation, IMO. Linear algorithms tend to be simple and make one pass over the data, which is going to make them fast. O(n log n) algorithms tend to be more complicated, make multiple passes over the data, and/or involve doing things that are slow in hardware, which is going to make them slower. However, that is just a general trend, and sometimes things are reversed.
taeric 12y ago
Among my favorite leading quotes from Knuth's works is this: "The asymptotically best algorithms frequently turn out to be worst on all problems for which they are used." — D. G. CANTOR and H. ZASSENHAUS (1981)
- icambron 12y ago
  I like "Fancy algorithms are slow when n is small, and n is usually small." -Rob Pike
- fdej 12y ago
  Fun story: Knuth claims in the 1997 edition of TAOCP vol. 2 that dense matrices of size larger than 250 "rarely occur in practice" and that asymptotically fast matrix multiplication is "strictly of theoretical interest". In 1998, Erich Kaltofen posed "Open Problem 7: Convince Donald Knuth that these asymptotically fast methods are of practical value. If he pays you $2.56 for this technical error, you have solved this problem." As far as I know, this is still an open problem. (250 is peanut-sized in cryptography, number theory or computer algebra, and asymptotically fast matrix multiplication is very much useful in practice in those domains.)
  - murbard2 12y ago
    In finance, I've dealt with larger (but not much larger) dense matrices.
  - ajtulloch 12y ago
    For a simple application in finance, consider a portfolio with n stocks. Then finding various statistics around - expected portfolio mean & variance - optimizing mean-variance subject to a risk budget (following Markowitz portfolio theory), etc. would all entail operating on the n×n covariance matrix, which is typically dense. If your universe is the Russell 1000, S&P 500, etc, then n will be significantly larger than 250.
  - jjoonathan 12y ago
    Are those matrices dense? It's an important qualifier. My corner of the computational world (finite-element related code) very frequently gets to millions of rows and columns but with only O(N) nonzero entries (where N is #rows which is approximately #cols too).
anaphor 12y ago
Thanks, this is a pet peeve of mine. Theoretical bounds are all nice and such, and it's cool if you can prove a better running time using some algorithm, but if it doesn't actually perform better in practice most of the time then it's not really worth much. I blame computer scientists who are in a rush to publish the best theoretical solution but never bother to consider whether it has practical impacts. Also textbooks who blithely claim you can do better with such and such a data structure using a certain algorithm. See this StackOverflow question for some nice insights: https://stackoverflow.com/questions/504823/has-anyone-actually-implemented-a-fibonacci-heap-efficiently https://stackoverflow.com/questions/504823/has-anyone-actual...
- alco 12y ago
  It is worth pointing out here that Quicksort has complexity of Ɵ(n²) in the worst case. Yet it has worked out as the best one in practice in many applications.
  - shanusmagnus 12y ago
    That's true, but it's also worth pointing out that the worst case can be trivially prevented by shuffling the array before you Quicksort it. Which is maybe a confirmation of your larger point.
    - mtdewcmu 12y ago
      Shuffling can never prevent the worst case of any algorithm. "Worst case" means the worst out of all possible cases. Shuffling doesn't change the set of cases, and it doesn't change anything about any individual case. Probably what you meant was that shuffling makes the worst case very unlikely. On a practical level, if you have to shuffle the data before sorting to make your sort algorithm work better, you've most likely already blown any performance advantage. So you might as well choose a different sort algorithm.
    - ruggeri 12y ago
      Strictly speaking, it is not true that shuffling first avoids the worst case. Given a deterministic shuffling function, some permutation of input needs to shuffle to sorted order, which will again trigger the worst case. Of course, shuffling is still potentially helpful because ascending/descending order is often common in many applications.
icambron 12y ago
I think as a practical matter, sure. But it's also really fun to explore "fancy" algorithms, even when you don't have a practical need for them. I certainly felt the tone of the article was less "I need to sort a shitton of data" and more "I'm checking out this cool thing."
usamec 12y ago
I would never put KMP and Coppersmith-Winograd into same place in terms of practicality. KMP gives you very good and fast results on some data (especially data with repeated sequences). Coppersmith-Winograd (and even Strassen) will never be practical on any reasonable data we will see in near future (http://www.ics.uci.edu/~fastmm/FMM-Reference/paoloA.ishp-vi.pdf http://www.ics.uci.edu/~fastmm/FMM-Reference/paoloA.ishp-vi....)

mtdewcmu 12y ago

Another good reason to try a binary heap: it would have only taken a few hours to implement. Then you can do some benchmarking, count your gains, and perhaps quit while you're still ahead. Profiling is good, but I don't see how it would have helped her in this case. In order to profile the Fibonacci heap, you'd have to implement it first. She mentioned that it took twice as long as the original algorithm, and timing is a simple form of profiling, so she basically did profile (after implementing it). What would have helped is intuition about algorithms and the ability to estimate how fast they'll be without having to implement and time them. This was a good exercise for developing that intuition. It's useful to keep in mind that O(log n) is effectively O(1) in the real world, because on actual computers, integers are bounded by 2^64, which means that any logarithmic factor will be <= 64 (or some constant). When O(n) and O(n log n) algorithms differ in practical performance, the asymptotic difference is not usually the best explanation, IMO. Linear algorithms tend to be simple and make one pass over the data, which is going to make them fast. O(n log n) algorithms tend to be more complicated, make multiple passes over the data, and/or involve doing things that are slow in hardware, which is going to make them slower. However, that is just a general trend, and sometimes things are reversed.

taeric 12y ago

Among my favorite leading quotes from Knuth's works is this: "The asymptotically best algorithms frequently turn out to be worst on all problems for which they are used." — D. G. CANTOR and H. ZASSENHAUS (1981)

icambron 12y ago
I like "Fancy algorithms are slow when n is small, and n is usually small." -Rob Pike
fdej 12y ago
Fun story: Knuth claims in the 1997 edition of TAOCP vol. 2 that dense matrices of size larger than 250 "rarely occur in practice" and that asymptotically fast matrix multiplication is "strictly of theoretical interest". In 1998, Erich Kaltofen posed "Open Problem 7: Convince Donald Knuth that these asymptotically fast methods are of practical value. If he pays you $2.56 for this technical error, you have solved this problem." As far as I know, this is still an open problem. (250 is peanut-sized in cryptography, number theory or computer algebra, and asymptotically fast matrix multiplication is very much useful in practice in those domains.)
- murbard2 12y ago
  In finance, I've dealt with larger (but not much larger) dense matrices.
- ajtulloch 12y ago
  For a simple application in finance, consider a portfolio with n stocks. Then finding various statistics around - expected portfolio mean & variance - optimizing mean-variance subject to a risk budget (following Markowitz portfolio theory), etc. would all entail operating on the n×n covariance matrix, which is typically dense. If your universe is the Russell 1000, S&P 500, etc, then n will be significantly larger than 250.
- jjoonathan 12y ago
  Are those matrices dense? It's an important qualifier. My corner of the computational world (finite-element related code) very frequently gets to millions of rows and columns but with only O(N) nonzero entries (where N is #rows which is approximately #cols too).

anaphor 12y ago

Thanks, this is a pet peeve of mine. Theoretical bounds are all nice and such, and it's cool if you can prove a better running time using some algorithm, but if it doesn't actually perform better in practice most of the time then it's not really worth much. I blame computer scientists who are in a rush to publish the best theoretical solution but never bother to consider whether it has practical impacts. Also textbooks who blithely claim you can do better with such and such a data structure using a certain algorithm. See this StackOverflow question for some nice insights: https://stackoverflow.com/questions/504823/has-anyone-actually-implemented-a-fibonacci-heap-efficiently https://stackoverflow.com/questions/504823/has-anyone-actual...

alco 12y ago
It is worth pointing out here that Quicksort has complexity of Ɵ(n²) in the worst case. Yet it has worked out as the best one in practice in many applications.
- shanusmagnus 12y ago
  That's true, but it's also worth pointing out that the worst case can be trivially prevented by shuffling the array before you Quicksort it. Which is maybe a confirmation of your larger point.
  - mtdewcmu 12y ago
    Shuffling can never prevent the worst case of any algorithm. "Worst case" means the worst out of all possible cases. Shuffling doesn't change the set of cases, and it doesn't change anything about any individual case. Probably what you meant was that shuffling makes the worst case very unlikely. On a practical level, if you have to shuffle the data before sorting to make your sort algorithm work better, you've most likely already blown any performance advantage. So you might as well choose a different sort algorithm.
  - ruggeri 12y ago
    Strictly speaking, it is not true that shuffling first avoids the worst case. Given a deterministic shuffling function, some permutation of input needs to shuffle to sorted order, which will again trigger the worst case. Of course, shuffling is still potentially helpful because ascending/descending order is often common in many applications.

icambron 12y ago

I think as a practical matter, sure. But it's also really fun to explore "fancy" algorithms, even when you don't have a practical need for them. I certainly felt the tone of the article was less "I need to sort a shitton of data" and more "I'm checking out this cool thing."

usamec 12y ago

I would never put KMP and Coppersmith-Winograd into same place in terms of practicality. KMP gives you very good and fast results on some data (especially data with repeated sequences). Coppersmith-Winograd (and even Strassen) will never be practical on any reasonable data we will see in near future (http://www.ics.uci.edu/~fastmm/FMM-Reference/paoloA.ishp-vi.pdf http://www.ics.uci.edu/~fastmm/FMM-Reference/paoloA.ishp-vi....)