5 ms·
Many years ago, as an undergrad, I was telling a grad student friend how I'd been learning about the Selection algorithm- it lets you pick the Kth largest eleme
by mabbo 3y ago
Many years ago, as an undergrad, I was telling a grad student friend how I'd been learning about the Selection algorithm- it lets you pick the Kth largest element from an unsorted list in linear time, which is pretty neat.
I said "It's O(n), but the constant is ridiculous in most implementations so it's usually better just to sort and then pick the kth element". The grad student friend said something that stuck with me: "Sure, but the algorithm proves it's possible to find the kth element in linear time. That was never guaranteed. Now we just need to find a better way to do it."
Random conversation that stuck with me, and they probably forgot it a moment later.
- gyrovagueGeist 3y agoRelatedly, quickselect (and it’s variants) are very important for distributed computing where sorting has higher communication costs.
- riversflow 3y ago> That was never guaranteed Branching off into a philosophical thought here, but I find this to be completely wrong. It was always guaranteed; logic, like physics and chemistry is not an environment that changes. We have discovered a functioning technique which might be improved upon. What wasn’t guaranteed was that it would be found. Biology is the root of most, perhaps all, uncertainty. After all, it is our biology that makes us imperfect observers, thinkers, and makers(but also enables us to do those things at all!). I think this is important, because their is a significant difference in mindset between making something, and looking for something. Science is looking, technology is making. Things are always “seen” before they are “made”.
- mabbo 3y agoI think the point is that we live in either a universe where X is possible or a universe where X is not possible. What we don't know is which we exist in.