5 ms·
>> In some cases amortized isn't good enough though, and games could certainly be one of them! Real time systems including games have hard limits on how long s
by phkahler 5y ago
>> In some cases amortized isn't good enough though, and games could certainly be one of them!
Real time systems including games have hard limits on how long something can take in the worst case, not the average. In games this manifests as: All the stuff has to be done in 16ms to render a frame on time, if we're late the user will perceive a glitch. The consequences can be worse in control systems in any number of real-world systems where a glitch can lead to stability problems.
So getting back to TFA, this is part of knowing what the "right" answer is for the context.
- tomxor 5y ago> worst case, not the average Yup, I can't remember which book but I'm pretty sure I remember reading some stuff from Michael Abrash about how some of the algorithms in quake were changed for worse average performance but better worst case performance. It's fairly intuitive when you think about the context... and that is the critical point - abstract problems are interesting, but it's important to evaluate them in their full context.
- SilasX 5y agoSo it would be fine if they had said, "okay, for this problem let's add the requirement that every add must be fast, because it's within a frame rendering loop", but (from OP's description) they didn't even seem to understand that's a separate desideratum, or that it doesn't mean the amortized time is bad.
- tomxor 5y agoIt's probably implicit, it's a gaming company, however it might be fair to say the interviewers didn't appreciate the possibilities outside of gaming and unconsciously assumed this context was understood.