4 ms·
> I imagined, “what if we were able to just find the next vertex of minimum distance from the source in constant time?” > [...] > even if you have the right a
by isaacimagine 5y ago
> I imagined, “what if we were able to just find the next vertex of minimum distance from the source in constant time?”
> [...]
> even if you have the right algorithm, the choice of how you represent auxillary data in the algorithm matters.
I think this is a very useful insight and the core of the piece. It just goes to show how important the layout data is with respect to the algorithm using it.
- jacquesm 5y agoThis is true in most cases. It is all about the data and algorithm in concert, rarely about either one. Badly laid out data can kill your cache. Well laid out data with a crappy algorithm may outperform badly laid out data with a fantastic algorithm. The ability to visualize the impact of your layout on caching is the fastest pay-off you'll ever have as a programmer, just knowing the sizes of your caches can already make a huge difference. For instance: if you have a bunch of data and you need to do operations on that data it is much faster to pull in the data piecemeal, do all the operations on it bit-by-bit and then to move on to the next bit of data than to do several sequential passes over the data storing the intermediate results. The difference in speed can be multiple orders of magnitude.