5 ms·

Just to be 100% clear, in case anyone who is new to the field stumbles on this thread, this is NOT breaking math or anything. This is a fun, but totally normal

by antics 12y ago

Just to be 100% clear, in case anyone who is new to the field stumbles on this thread, this is NOT breaking math or anything. This is a fun, but totally normal result. First of all, there are quite a few linear time sorting algorithms. Radix, pigeonhole, and counting sort are all linear time sorting algorithms. The popular result that any comparison-based sorting algorithm works in O(n log n) applies _specifically_ to comparison-based sorting algorithms, and not those like the above. So, even if you ignore the underlying mechanics of the OS scheduler and assume sleep works "perfectly", the result would not that unusual. Second off, in the comments there appears to be considerable time worrying about the technicalities of the scheduler, the nondeterministic nature of sleep, and so on, and whether this really implies linear time bound. IMHO these are not worth worrying about because we already have linear time sorting algorithms. It's fine to assume the scheduler adds no significant asymptotic cost here, even if we know differently. Third off, remember that all of these sorting bounds assume machines of the Von Neumann architecture. In particular, this model assumes constant time memory and constant time comparison operations. In cases where you're comparing really big numbers, these bounds get worse. This is easy to forget, but worth remembering just since we're on the subject anyway.

wcrichton 12y ago
This is not "linear time" in any decent sense--we shouldn't conflate the number of elements with the size of the elements (in this case, O(max element) is actually exponential in the input size!).
- duaneb 12y ago
  Yea, it's linear time for n where n is the largest number—pretty sure it's unbounded in terms of numbers of elements.
  - bnegreve 12y ago
    True, but writing a linear sort with bounded number of distinct elements is not really a challenge. E.g. Intput, T: array of n elements, m: number of distinct elements. for i in 1..m for j in 1..n if( T[j] == i ) print T[j]; This is O(n * m) which is O(n) since m is a constant.
- asdfaoeu 12y ago
  the max size of the elements is usually constant when comparing sorting algorithms. The complexity of this depends on the algorithm of the scheduler. With the right scheduler this could be O(nlog n).
- antics 12y ago
  This isn't really right. If the numbers can be arbitrary in size, then you can't compare them in constant time, which means that comparison-based sorts are quadratic. This is directly related to my third point. Traditional analysis of sorting algorithms assumes the Von Neumann architecture, and in particular, it assumes constant-time comparisons.
  - flebron 12y ago
    The computational model will define what you can and cannot compare in constant time. It is perfectly fine to say that comparing elements of arbitrary size is a constant time operation - that's precisely what a computational model is: an enumeration of the operations that are considered basic.
    - antics 12y ago
      Yeah, I know. Go read the parent again. The author claims that sorting in this case takes time proportional to the size of largest element, and I'm saying, if it takes time proportional to the space consumption of in the largest element (presumably where the cost of the sort comes from), you can't define a computational model where comparison takes constant time -- it still has to read the digits, which we know takes linear time. If your point is that you can define a model of computation with contradictions in it, then you should rethink whether what you are saying here is even relevant to the thread at all.
      - Retric 12y ago
        You can shurt circuit comparisons but that's not always going to happen. Consider it's completly reasonable to assume long int is sorted as fast as int on a 128 bit CPU. If nothing else it's useful to have a fairly long cycle even if you could in theory use a 20GHz CPU that has some comparisons finish in 4 cycles and others just 1. Sure, it might be slightly faster than a 5GHz CPU with constant time comparisons, but the added complexity is not free.
        antics 12y ago
- SilasX 12y ago
  I thought that too, but couldn't you make element size irrelevant by renormalizing the list? One pass to find the max, one pass to divide everything by it.
gpfault 12y ago
It's more like O(max(input)), not O(n) (see the first response)
- davrosthedalek 12y ago
  You can always scan through the array, rescale everything by 1/max(input). Then the sleep part is O(1) and the scan part is O(n) -> O(n) total.
  - JoshTriplett 12y ago
    Division isn't O(1) for arbitrary values (potentially larger than a machine word).
    - pdw 12y ago
      The same is true for comparison though, isn't it?
    - dalke 12y ago
      Sleep maxes out at 2147483647 = 2^31 seconds. Generally these problems assume the transdichotomous model, where the machine word size matches the problem size.
- fennecfoxen 12y ago
  Well. Let's distinguish between computational complexity and wall-clock time. The code you write yourself here performs operations with O(n) asymptotic complexity where n is the number of elements, but the system scheduler may be able to find additional work to do while the algorithm is waiting to resume, or even put the CPU into a lower-energy state. Of course, making lots of system calls to create processes and store them in your operating system's process table almost certainly invokes operations with greater than O(n) asymptotic complexity, but this complexity is still unrelated to max(input).
sorbits 12y ago
> there appears to be considerable time worrying about the technicalities of the scheduler […] whether this really implies linear time bound. IMHO these are not worth worrying about But it is not linear time, we shouldn’t let the existence of other algorithms make us confused about proper analysis of this one. The call to `sleep(n)` is not a trivial operation, it inserts our task into a priority queue, so we are piggybacking on the OS’ support for sorting tasks based on when they need to be woken up, and thus hide the actual complexity behind the call to `sleep` (which we call `n` times, so if it’s `lg(n)` then the time complexity of the entire algorithm is `O(n lg n)`).
- bane 12y ago
  It's also a good example of why O() isn't the entire story when it comes to how long an algorithm takes to run.
detrino 12y ago
This is not a linear time sort. This is just sorting using a priority queue (aka heap sort) with arbitrary pauses thrown in. Here is a simplified model of what is going on (http://ideone.com/azLsTc http://ideone.com/azLsTc). Note that line 31 (the sleep until) is totally irrelevant to the sorting.
- 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

wcrichton 12y ago

This is not "linear time" in any decent sense--we shouldn't conflate the number of elements with the size of the elements (in this case, O(max element) is actually exponential in the input size!).

duaneb 12y ago
Yea, it's linear time for n where n is the largest number—pretty sure it's unbounded in terms of numbers of elements.
- bnegreve 12y ago
  True, but writing a linear sort with bounded number of distinct elements is not really a challenge. E.g. Intput, T: array of n elements, m: number of distinct elements. for i in 1..m for j in 1..n if( T[j] == i ) print T[j]; This is O(n * m) which is O(n) since m is a constant.
asdfaoeu 12y ago
the max size of the elements is usually constant when comparing sorting algorithms. The complexity of this depends on the algorithm of the scheduler. With the right scheduler this could be O(nlog n).
antics 12y ago
This isn't really right. If the numbers can be arbitrary in size, then you can't compare them in constant time, which means that comparison-based sorts are quadratic. This is directly related to my third point. Traditional analysis of sorting algorithms assumes the Von Neumann architecture, and in particular, it assumes constant-time comparisons.
- flebron 12y ago
  The computational model will define what you can and cannot compare in constant time. It is perfectly fine to say that comparing elements of arbitrary size is a constant time operation - that's precisely what a computational model is: an enumeration of the operations that are considered basic.
  - antics 12y ago
    Yeah, I know. Go read the parent again. The author claims that sorting in this case takes time proportional to the size of largest element, and I'm saying, if it takes time proportional to the space consumption of in the largest element (presumably where the cost of the sort comes from), you can't define a computational model where comparison takes constant time -- it still has to read the digits, which we know takes linear time. If your point is that you can define a model of computation with contradictions in it, then you should rethink whether what you are saying here is even relevant to the thread at all.
    - Retric 12y ago
      You can shurt circuit comparisons but that's not always going to happen. Consider it's completly reasonable to assume long int is sorted as fast as int on a 128 bit CPU. If nothing else it's useful to have a fairly long cycle even if you could in theory use a 20GHz CPU that has some comparisons finish in 4 cycles and others just 1. Sure, it might be slightly faster than a 5GHz CPU with constant time comparisons, but the added complexity is not free.
      - antics 12y ago
SilasX 12y ago
I thought that too, but couldn't you make element size irrelevant by renormalizing the list? One pass to find the max, one pass to divide everything by it.

gpfault 12y ago

It's more like O(max(input)), not O(n) (see the first response)

davrosthedalek 12y ago
You can always scan through the array, rescale everything by 1/max(input). Then the sleep part is O(1) and the scan part is O(n) -> O(n) total.
- JoshTriplett 12y ago
  Division isn't O(1) for arbitrary values (potentially larger than a machine word).
  - pdw 12y ago
    The same is true for comparison though, isn't it?
  - dalke 12y ago
    Sleep maxes out at 2147483647 = 2^31 seconds. Generally these problems assume the transdichotomous model, where the machine word size matches the problem size.
fennecfoxen 12y ago
Well. Let's distinguish between computational complexity and wall-clock time. The code you write yourself here performs operations with O(n) asymptotic complexity where n is the number of elements, but the system scheduler may be able to find additional work to do while the algorithm is waiting to resume, or even put the CPU into a lower-energy state. Of course, making lots of system calls to create processes and store them in your operating system's process table almost certainly invokes operations with greater than O(n) asymptotic complexity, but this complexity is still unrelated to max(input).

sorbits 12y ago

> there appears to be considerable time worrying about the technicalities of the scheduler […] whether this really implies linear time bound. IMHO these are not worth worrying about But it is not linear time, we shouldn’t let the existence of other algorithms make us confused about proper analysis of this one. The call to `sleep(n)` is not a trivial operation, it inserts our task into a priority queue, so we are piggybacking on the OS’ support for sorting tasks based on when they need to be woken up, and thus hide the actual complexity behind the call to `sleep` (which we call `n` times, so if it’s `lg(n)` then the time complexity of the entire algorithm is `O(n lg n)`).

bane 12y ago
It's also a good example of why O() isn't the entire story when it comes to how long an algorithm takes to run.

detrino 12y ago

This is not a linear time sort. This is just sorting using a priority queue (aka heap sort) with arbitrary pauses thrown in. Here is a simplified model of what is going on (http://ideone.com/azLsTc http://ideone.com/azLsTc). Note that line 31 (the sleep until) is totally irrelevant to the sorting.

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.