3 ms·

No, sorry, that's not correct, it's not a decided issue whether it's linear time or not. It depends on what assumptions we _decide_ to make about the scheduler

by antics 12y ago

No, sorry, that's not correct, it's not a decided issue whether it's linear time or not. It depends on what assumptions we _decide_ to make about the scheduler and the OS, what the API for sleep is, and so on. One reasonable assumption is of course to assume that sleep works as it does on virtually all modern OSs, in which case, you're correct, but that is certainly not the only way it can be. You could easily imagine a specialized SortOS that executes one thread on one process and outputs messages at a specifically scheduled time after a program begins executing, in which case the result would be radix sort with extraneous waiting, rather than priority heap sort with extraneous waiting.

detrino 12y ago
We don't have to make any assumptions, we know how schedulers work, and the radix sort counterpart of a priority queue would probably be a radix tree, which would be impractical for use in a scheduler.
- antics 12y ago
  It's completely false to say that "we know how schedulers work". The _only_ reason there is confusion in this thread and the 4chan thread is because so few people actually know anything about schedulers. If they did, no one would be confused. The fact that there is confusion at all is basically a huge point for explicitly stating your assumptions. Moreover, that is essentially the whole point of the field of algorithms. Your job as an algorist is to abstract the algorithm away from the implementation details of wholly separate systems, and make all of your assumptions explicit. If you don't specify it, you can't analyze it. And, if an algorithm has to assume an entire, specific OS and scheduler is implemented under it, then you have gone about your job as an algorist completely wrong. That is the appeal to practicality. But as if to prove my point, you _do_ end up making assumptions. You are assuming that the scheduler is backed by a priority queue, which is certainly not universally true. You don't get to a hard mathematical bound by waving away a detail as important as the data structure that backs the core sort mechanic. If your approach is to say "y'know, like a _normal_ scheduler", then you should stop and rethink your approach to the problem.

by antics 12y ago

detrino 12y ago

We don't have to make any assumptions, we know how schedulers work, and the radix sort counterpart of a priority queue would probably be a radix tree, which would be impractical for use in a scheduler.

antics 12y ago
It's completely false to say that "we know how schedulers work". The _only_ reason there is confusion in this thread and the 4chan thread is because so few people actually know anything about schedulers. If they did, no one would be confused. The fact that there is confusion at all is basically a huge point for explicitly stating your assumptions. Moreover, that is essentially the whole point of the field of algorithms. Your job as an algorist is to abstract the algorithm away from the implementation details of wholly separate systems, and make all of your assumptions explicit. If you don't specify it, you can't analyze it. And, if an algorithm has to assume an entire, specific OS and scheduler is implemented under it, then you have gone about your job as an algorist completely wrong. That is the appeal to practicality. But as if to prove my point, you _do_ end up making assumptions. You are assuming that the scheduler is backed by a priority queue, which is certainly not universally true. You don't get to a hard mathematical bound by waving away a detail as important as the data structure that backs the core sort mechanic. If your approach is to say "y'know, like a _normal_ scheduler", then you should stop and rethink your approach to the problem.