3 ms·
See Alexandrescu’s Fastware talk on how amazingly sentinels can improve even textbook algorithms, and how to apply the approach intelligently. E.g., for a linea
by dundarious 6y ago
See Alexandrescu’s Fastware talk on how amazingly sentinels can improve even textbook algorithms, and how to apply the approach intelligently. E.g., for a linear search, overwrite the last element with the sought after value, and do a tiny bit of work to make that safe and to undo it before return.
If you’re skeptical, I really do encourage you to watch, he’s not sloppy.
https://youtu.be/AxnotgLql0k https://youtu.be/AxnotgLql0k
- deleted 6y ago[deleted]
- bjoli 6y agoThis brings back memories! I discovered the same thing in high school in a programming class. We had a speed-golfing assignment and in the end my program ended up quite a bit faster than the "golden reference" our teacher had. He refused to believe I had come up with it myself (though I got the highest grade on the assignment). This was back when we could assume 8-bit encodings(iso 8859-1 was the one we used). Simpler times!