News for hackers. Stuff that matters.
Re:Sorting a Billion Numbers with Julia by brashrat on Monday March 21, 2016 @07:05PM (#11332922)
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.

Re:Sorting a Billion Numbers with Julia by ACow_Adonis on Monday March 21, 2016 @09:51PM (#11333855)
No 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...

Re:Sorting a Billion Numbers with Julia by nl on Monday March 21, 2016 @10:40PM (#11334065)
It's not absurd, it's funny.

But you already knew that - you just hadn't evaluated it yet.

Re:Sorting a Billion Numbers with Julia by Mikeb85 on Monday March 21, 2016 @07:11PM (#11332956)
You mean you can define a sorted list in nano-seconds. The actual calculations (ie. obtaining every result) take much longer...
Re:Sorting a Billion Numbers with Julia by mcnamaratw on Tuesday March 22, 2016 @05:24AM (#11335304)
Haha, In that case I'm going to lazily start using Haskell immediately. There's no learning curve at all!
Re:Sorting a Billion Numbers with Julia by nly on Monday March 21, 2016 @11:40PM (#11334277)
The 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).
Re:Sorting a Billion Numbers with Julia by im3w1l on Tuesday March 22, 2016 @02:39AM (#11334785)
Finding 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.
Re:Sorting a Billion Numbers with Julia by imh on Tuesday March 22, 2016 @02:51AM (#11334811)
It 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.
Re:Sorting a Billion Numbers with Julia by adrianN on Tuesday March 22, 2016 @04:41AM (#11335150)
It 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.
Re:Sorting a Billion Numbers with Julia by tanlermin on Monday March 21, 2016 @07:09PM (#11332943)
Are you being sarcastic?
Re:Sorting a Billion Numbers with Julia by brashrat on Monday March 21, 2016 @07:18PM (#11332999)
I 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.

Re:Sorting a Billion Numbers with Julia by dekhn on Monday March 21, 2016 @07:26PM (#11333061)
This 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/) 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.

Re:Sorting a Billion Numbers with Julia by GFK_of_xmaspast on Tuesday March 22, 2016 @10:12AM (#11336699)
> 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.

Re:Sorting a Billion Numbers with Julia by dekhn on Monday March 21, 2016 @07:19PM (#11333012)
Yes, 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.