3 ms·
There are obvious cases where you are improving efficiency without eliminating slack. I'm not making my application more fragile by rewriting an n^2 operation o
by Taek 6y ago
There are obvious cases where you are improving efficiency without eliminating slack. I'm not making my application more fragile by rewriting an n^2 operation over a large dataset to an n*log(n) operation that provides the same output. It's a win without tradeoffs.
This type of example exists in all industries. For example, finding a new alloy that has strictly superior properties across all dimensions for a specific use case. Or upgrading mail delivery routes using better pathfinding algorithms. Etc.
- hansvm 6y ago> I'm not making my application more fragile by rewriting an O(n^2) operation over a large dataset to an O(n log(n)) operation that provides the same output. It's a win without tradeoffs. Hopefully not nitpicking too much: it's a win without _many_ tradeoffs. E.g., in the usual places where you'd accidentally get an O(n^2) operation rather than O(n log(n)), the O(n^2) operation is constant-space. In a sufficiently anomalous computing environment with a low enough priority on fast results you might still consciously opt for the O(n^2) solution.
- Retric 6y agoPlenty of n log n operations are in constant space. Average Quicksort performance being perhaps the classic example. But most often you see these kinds of improvements by simply removing steps. Net result is less code, less memory use age, less of everything.
- hansvm 6y agoYep, I'm not arguing that it's always a good idea (or even usually...or even that I've seen it be a good idea in the wild), just that it could be. Taking quicksort as an example, it's only constant space if you're allowed/able to mutate in-place. If you need (for some bizarre reason) to stream sorted results in constant space without mutating the underlying data then you'll need some other tool.