4 ms·
in a purely functional language like Haskell, you can sort a billion numbers in nanoseconds, all with no performance crushing side effects. Yes, it's true, that
by brashrat 11y ago
in a purely functional language like Haskell, you can sort a billion numbers in nanoseconds, all with no performance crushing side effects. Yes, it's true, that's the kind of results you get with lazy evaluation!
When you start searching the resultant sorted list, it might be somewhat slower than if you sorted using other techniques, but--silver lining--search times will only improve after that!
I'd give you the actual stats but so far I've only lazy evaluated them.
- tanlermin 11y agoAre you being sarcastic?
- brashrat 11y agoI pointed it out to be lighthearted, but it's true not sarcasm, and not only true, it's also meaningfully instructive to think about the benefits of lazy evaluation. For example, a priority queue (list of tasks) does not need to be fully sorted, only sorted to the extent that the highest priorty item is quickly determinable, and there are algorithms and data structures designed for this behavior. Sorting (other than to print a sorted list) doesn't pay for itself till you do a number of searches, and associative memory hashes are frequently better if you simply wish to find exact matches again. Even the lowly bubble sort has the not-insignificant benefit of finding the first value in O(n) time which may be the behavior you need: lazy evaluation can be the exact right way to go if you are instructed to sort, as you await more info as to what the appropriate technique might be. I think humor is only funny when it's based on truthiness.
- dekhn 11y agoThis is an out-of-core problem. What matters when sorting a billion numbers is wallclock runtime from the start of the sort to the end of materialization (see http://sortbenchmark.org/ http://sortbenchmark.org/) or iteration. And it means, almost always, materializing or iterating the entire result set. it's not clear to me any haskell programs have won any real awards in sorting modest amounts of data, since you have to visit all the data and compare nlogn times.
- GFK_of_xmaspast 11y ago> Sorting (other than to print a sorted list) doesn't pay for itself till you do a number of searches Or until you absolutely need to iterate thru a collection in sorted order. If you need a priority queue, use a priority queue, if you need a sorted container, use a sorted container.
- dekhn 11y agoYes, they are being sarcastic. The list has to be fully materialized and iterated over. Further, the Haskell version probably doesn't have a concept of doing work in memory-sized batches with spill-to-disk, so the runtime would likely be much higher. Of course, I don't know enough Haskell so it's entirely possible they somehow figured this how to iterate over the input data in sorted order efficiently without materializing it.
- deleted 11y ago[deleted]
- Mikeb85 11y agoYou mean you can define a sorted list in nano-seconds. The actual calculations (ie. obtaining every result) take much longer...
- deleted 11y ago[deleted]
- ACow_Adonis 11y agoNo offence, but that's absurd. If anyone said their database can do things almost instantly because they can write a view which is defined super quick vs materialising or running an actual query they'd be, justifiably and hopefully, laughed out of the room. But that's pretty much what you've done/contributed. Of course lazy evaluation is faster if it's so lazy it doesn't actually evaluate anything/does something completely different to the original problem. Now evaluate it and come back with a wall time...
- nl 11y agoIt's not absurd, it's funny. But you already knew that - you just hadn't evaluated it yet.
- nly 11y agoThe complexity of fully iterating over a lazily-sorted range is more than 'somewhat slower'. At a guess I'd say it's O(n^2) rather than O(n log n).
- im3w1l 11y agoFinding sorted(array)[k] is possible in linear (even worst case!) time. Using that n times would as you note take n^2 time. But we could employ a trick. Once we have been asked for log n elements, and have thus already spent n log n time, we could then sort the array.
- imh 11y agoIt should stay n log n. A lazy quicksort can get the min element of a list super fast by only working on the partitions relevant to finding the min. As it requires more elements of the list, it can finish sorting the other partitions. It's the exact same algo as usual.
- adrianN 11y agoIt depends on the implementation. If you stuff your list in a (lazily constructed) heap, you can get the next element in O(log n) amortized.
- mcnamaratw 11y agoHaha, In that case I'm going to lazily start using Haskell immediately. There's no learning curve at all!