<p>Time-based sorting algorithm, just for fun. :)</p>
<p>I've seen this idea somewhere in internet, implemented in bash, so this is just rewriting it in Go.
I hope you find it funny and amazing as well. :)</p>
<p>I wonder if it can be implemented in even more compact and idiomatic way?</p>
<pre><code>package main
import (
"fmt"
"os"
"strconv"
"sync"
"time"
)
func main() {
var wg sync.WaitGroup
for _, arg := range os.Args[1:] {
num, _ := strconv.ParseUint(arg, 10, 0)
wg.Add(1)
go func(num uint64) {
// sorting magic happens here :)
time.Sleep(time.Duration(num) * time.Millisecond)
fmt.Printf("%d ", num)
wg.Done()
}(num)
}
wg.Wait()
fmt.Println()
}
</code></pre>
<hr/>**评论：**<br/><br/>dominikh: <pre><p>The scientific term for this is "sleep sort"</p></pre>Simpfally: <pre><p>I've never heard of it, thanks!</p></pre>SupersonicSpitfire: <pre><p>You could scale the sleeping time down to get a faster sleep sort. </p></pre>SupersonicSpitfire: <pre><p>But if you start scaling down to too small time values, the numbers would probably appear in the wrong order. If there was a time cap, some numbers could be lost, but it would guaranteed to run at a fixed time. Perhaps these errors would look interesting when applied as a 2D image filter, where some pixels were gone and some were in the wrong order? Perhaps there are uses for an overly optimized sleep sort algorithm? </p></pre>divan0: <pre><p>Yes, even 100 * time.Microsecond resolution does wrong order on my laptop. )</p></pre>SaidinWoT: <pre><p>Precomputing most of what's in the actual sort loop can get you a finer resolution:</p>
<pre><code>args := os.Args[1:]
nums := make([]uint64, len(args))
for i, arg := range args {
nums[i], _ = strconv.ParseUint(arg, 10, 0)
}
var wg sync.WaitGroup
wg.Add(len(nums))
for _, num := range nums {
go func(num uint64) {
time.Sleep(time.Duration(num * resolution) * time.Microsecond)
fmt.Print(num, " ")
wg.Done()
}(num)
}
wg.Wait()
fmt.Println()
</code></pre>
<p>Wherein <code>resolution</code> is whatever resolution you want to play with. I was consistently having no problems at the 100 * time.Microsecond resolution on my 4 year old laptop with this.</p>
<p>Edit: I agree with <a href="/u/SupersonicSpitfire" rel="nofollow">/u/SupersonicSpitfire</a> that, as the size of the input increases and the resolution decreases, some way of scaling non-linearly is probably necessary. I was playing with adding the length of the input list into the sleep calculation to reduce the impact of the input size - it does help to some extent.</p></pre>SupersonicSpitfire: <pre><p>The numbers would probavly have to be scaled non-linearly somehow for the resolution to be smaller, while the results are still correct. </p></pre>jerf: <pre><p>An "optimized" sleep sort will optimize the sleep away, and therefore no longer be a sleep sort. Unsurprisingly, there's no "saving" this bad idea/joke. Just chuckle.</p></pre>SupersonicSpitfire: <pre><p>If the sleep is as small as possible, while not getting rid of it completely, it could be a very predictable algorithm with a fixed runtime, while not being that inefficient. All algorithms have advantages and tradeoffs. Perhaps sleep sort could have a use, somehow?</p></pre>SwellJoe: <pre><blockquote>
<p>All algorithms have advantages and tradeoffs.</p>
</blockquote>
<p>Advantage: Funnier than most sort algorithms.</p>
<p>Tradeoff: Not useful.</p></pre>hobbified: <pre><p>No, because what you're really doing is forcing the kernel (or perhaps the Go runtime in this case since it has its own green thread scheduler) to do a <em>real</em> sort in order to figure out which task to wake up next.</p></pre>jerf: <pre><p>SwellJoe nailed what I was trying to express better than I could express it myself.</p>
<p>So I'd like to go slightly in an introspective direction, and ask you to ask yourself, why are you fighting for this so hard? I mean, not like you're going nuclear and scorching the earth or anything, but, why is it so hard to believe that this is just straight-up a bad idea?</p>
<p>I mention this as worth examining because it's an antipattern I frequently end up jousting with at work. Once someone gets an idea in their head, even before we've implemented anything, some criticisms or issues will emerge, and instead of realizing it's just a bad idea, the idea holder ends up continuously trying to tweak the idea and hammer on it and justify it and excuse it, instead of discarding it while it's still cheap. Sometimes all I have to do is re-orient the frame back to "let's go back to exploring the solutions"... sometimes, it goes far less well and people dig in and become political about it, at which point, goodbye good engineering. I have one particular example in mind at the company I work at that I would consider easily a multi-million dollar mistake. (How fortunate that we work in an industry where we can so easily generate so much value that we can afford such things. No sarcasm.)</p>
<p>Sometimes it's just a bad idea. It so happens that this one is quite clearly so. You really need to learn to let them go and keep exploring the idea space, or, in this case, just release it.</p></pre>SupersonicSpitfire: <pre><p>The thing you must understand is that people may have different motivation and that Reddit is not a workplace. With a background from the demoscene, I'm always on the lookout for algorithms that can be used for 2D or 3D effects. The sleep sort has the potential to be used for a 2D effect. Will it look interesting? That's to be seen, but who are you to discourage and demotivate a stranger?</p></pre>jerf: <pre><p>I was trying to <em>encourage</em> a stranger to truly think, instead of doing something that superficially looks like thinking but is really a profound failure to apply judgment.</p>
<p>But now I see you've fallen victim to the popular idea that any sort of judgment is somehow a threat to your self-image. Carry on then.</p></pre>SupersonicSpitfire: <pre><p>That's an inaccurate interpretation of the situation. You are the one that is unwilling to comprehend here. Lossy algorithms really can be useful for 2D effects. You are the one that is reacting like what I said is a threat instead of admitting you have no imagination and is incapable of understanding the motivations of others, and uses of algorithms thar you had not thought about. </p></pre>eldosoa: <pre><p>This may be a noob question but what's the difference between passing <code>num</code> as an argument to the goroutine (as in the code sample) and just actually using num inside the closure (remove passing <code>num</code> into the goroutine and remove the requirement of an arg)?</p></pre>Failstorm: <pre><p>The difference is between closing over a variable thus sharing it vs passing it by value thus copying it.</p>
<p>If you close over the variable, the loop may change the value by the time the goroutine actually begins execution. (the "go" statement only guarantees that the goroutine will start execution after the statement but it doesn't say anything about when)</p>
<p>see:
<a href="http://golang.org/ref/mem#tmp_5" rel="nofollow">http://golang.org/ref/mem#tmp_5</a></p></pre>zond: <pre><p>In this particular case the 'num' var gets allocated once each loop anyway, so there's really no need.</p></pre>mcvoid1: <pre><p>Rather than using a WaitGroup you could use a channel, with the channel receiver printing the statements.</p></pre>divan0: <pre><p>Well.. not sure it will be more compact. How to know, when to close the channel in this case?</p></pre>ManticoreX: <pre><p>You don't need to close channels. They will automatically be cleaned up. You can just wait for the expected number of values to be retrieved from the channel and then continue on.</p></pre>SaidinWoT: <pre><p>Rewriting my rewrite above, this would close the channel appropriately:</p>
<pre><code>args := os.Args[1:]
nums := make([]uint64, len(args))
for i, arg := range args {
nums[i], _ = strconv.ParseUint(arg, 10, 0)
}
c := make(chan uint64)
for _, num := range nums {
go func(num uint64) {
time.Sleep(time.Duration(num*resolution) * time.Microsecond)
c <- num
}(num)
}
for i := range nums {
nums[i] <-c
}
close(c)
fmt.Println(nums)
</code></pre>
<p>Note that we know ahead of time exactly how many outputs we're expecting, so we can wait for that many values to come out of the channel and then close up shop.</p></pre>divan0: <pre><p>Yes, that will work. But it could be easily messed up when you add errors handling for example. Number of output items could be different from number of input numbers in case of some wrong input, and you'll need to handle this somehow.
So I found WaitGroup way a bit flexible.</p></pre>SaidinWoT: <pre><p>The WaitGroup should not be any more flexible, as it will wait until the appropriate number of goroutines have called Done (any fewer and it will wait indefinitely, any extra would not be waited for, which can lead to bugs depending on use).</p>
<p>You could just as easily increment a counter in the for loop and loop up to that counter amount when receiving from the channel. In cases where the output and input amounts differ, your logic should increment and decrement the counter just as it would Add and Done the WaitGroup.</p></pre>mcvoid1: <pre><p>you know how many goroutines you spawned so the receiving end can just stop listening or close it themselves after x reads from the channel.</p></pre>LordButtersI: <pre><p>Honestly, this is a great tongue in cheek demo of why Go is so great for concurrency: this is the most succinct implementation of Sleep Sort I've ever seen.</p></pre>
