6 ms·
Yeah. I am wondering since a while whether well-known algorithms like the binary heap are still efficient on modern architectures, because their random memory a
by jnxx 6y ago
Yeah. I am wondering since a while whether well-known algorithms like the binary heap are still efficient on modern architectures, because their random memory access patterns.
- lorenzhs 6y agoFor priority queues, which implementation is optimal depends a lot on your workload (do you need addressability, i.e., a decreaseKey operation? What is the typical ratio of insertions to deletions? Are your keys integers?). I found some slide decks that are mostly in English with some German in between that might go some way to answering your question: [1] https://algo2.iti.kit.edu/sanders/courses/algen20/vorlesung.pdf https://algo2.iti.kit.edu/sanders/courses/algen20/vorlesung.... slide 180-207, there are some up-to-date measurements on slide 204 [2] https://nms.kcl.ac.uk/stefan.edelkamp/lectures/ae/slide/AE-AllgemeineVorrangwarteschlangen.pdf https://nms.kcl.ac.uk/stefan.edelkamp/lectures/ae/slide/AE-A... There are also parallel priority queues which might be useful depending on your problem, especially if it can be reformulated to operate on batches ("give me the 20 smallest items", "insert these 50 items").
- contravariant 6y agoLook up cache-oblivious algorithms. Turns out that random memory access can often be improved upon with smart data structures.