4 ms·
I'm not immediately convinced by your no-op example because I can conceive of situations that needs a little extra time to be passed between actions, such as in
by AndrewOMartin 10y ago
I'm not immediately convinced by your no-op example because I can conceive of situations that needs a little extra time to be passed between actions, such as in the case of sorting elements whose value isn't easily determinable and is best estimated n clock ticks after the previous action.
This is of course a million miles away from the kind of sorting problems you get in Computer Science 101, but this is my point, the traditional sorting problems happen in a very well defined context, as soon as that changes, you might find any algorithm being optimal. Including Bogosort and, for example, quicksort with some extra no-ops.
I like your point, but for the reason above I still think the No Free Lunch theorem is valuable, else I wouldn't have had this insight in the first place. At least, I consider it an insight, YMMV.
- rincebrain 10y agoSure, it's certainly valuable to realize that you rarely get an optimization in one case that's not pessimal in another, and it is well-removed from the constrained environments that people work through for demoing algorithms. I was just thinking in terms of more abstract optimization (e.g. platform-agnostic ones that just strictly reduce work to be done) versus platform-specific optimizations/workarounds/bin-packing (like nops to prevent your pipelines or cache lines from being pathological).