Re:B-Heap vs. Binary Heap (2010)
by userbinator on Sunday March 18, 2018 @01:31AM
(#16610587)
It's pretty much the same reason why databases use B-trees and not binary trees --- when you have to consider the nonuniform latency of storage access, traditional algorithmic analysis that assumes every memory address is accessible in the same time as any other becomes extremely misleading.
[ Parent
| on HN ]
Every memory access could be limited with some big enough number (just assume that there's no cache in your CPU), so traditional analysis is fine. People usually don't like that memory access is so slow, it's another matter. O(N^2) might be faster than O(NlnN) if multiplier for the latter algorithm is bad enough.
Re:B-Heap vs. Binary Heap (2010)
by martincmartin on Sunday March 18, 2018 @08:03AM
(#16611555)
As I like to put it: "Random Access Memory isn't random access any more."