Sorting with CPU-intensive keys

This is about a function perhaps no one has been waiting for … but who knows when it will come handy? (if you think it’s useful, please post!)

When you have data you want sorted, Programming tools SANDBOX script pic 8 from Snap!'s List utilities library is usually the function of choice. Under the hood is a (probably quicksort-based) JavaScript primitive. Sorting is blazing fast if the reporter within the ring (= the lambda function by which the data is ordered, let's call it the "key function") is really simple, such as Programming tools SANDBOX script pic 9 or Programming tools SANDBOX script pic 5.

But if the key function is more complicated, its evaluation may become a serious factor; and since keys will be recalculated at each comparison of data within the sorting process, its time consumption is of a higher order than just linear: O(n.log(n)), to be precise. E.g. when a well-shuffled list of 10 elements is sorted, its key function is evaluated some 40 to 50 times. With 100 elements, the key function will be evaluated over a thousand times. A list of 2,000 elements needs a little over 40 thousand evaluations on average, meaning every single key will be recalculated 20 times! This inefficiency becomes noticeable, or even troublesome, with a large list to be sorted, and a key function that takes substantial time to calculate.

It's relatively easily solved: calculate the keys once before sorting the data, sort the data by key, and you may remove the keys after the sorting. But why do it yourself if you can ask a library function to do it for you?

Now here's where the newly developed PREPSORT function comes in:

It works with a list of indices that’s linked to a list of keys, and these are sorted together. Probably the script can be simplified such that the list of indices can be done without, but I haven’t yet figured out an acceptable general solution for that (taking into account that the data to be sorted may be anything, including elements of varying format).

It is used almost like the existing library function, except that the second slot is for the bare key function, whereas the third slot determines whether the keys will he sorted from Hi(gh) to Lo(w), or the other way around (in the existing library’s SORT these components are integrated into one comparison lambda function).

So here’s an example of calling PREPSORT vs. the library SORT:
Programming tools SANDBOX script pic 11 vs.

I’m looking forward to comments!

The PREPSORT block is available at:
Programming tools

looks quite good, i felt like it should still allow a predicate for the sorting, but i can't think of any good use case for that.

nice,but i have to tell you,we(atleast i)rarely use sort

Speak for yourself. I sort things all the time. For one thing, a lot of algorithms that take 𝜽(n²) time if programmed in the most obvious way can be done in 𝜽(n lg n) time if you start by sorting the data.

Yes, this is a nice idea. Sorting the indices instead of directly sorting the data is a very APLish idea. :~)

What do you have against composition of functions? Oh, I guess you mean all those LETs as a form of documentation. That's reasonable. Okay.

Well guessed! It is quite feasible to cram all of the logic into a single megablock - actually I made one, but discarded it: unreadable.

A stepwise approach is also advantageous for debugging and maintenance. Composition is mostly for showing off, really.

Look into the PIPE block. It gives you the sequential computation without the need for extra variables. I guess maybe that won't make you so happy because you don't have the names, but you can attach one-line comments to PIPE's inputs explaining what each one does.

Thanks for the suggestion. But no, I’d rather write self-explaining code than ad comments. And I don’t see what the advantage of sequential computation would be.

Eh? Sequential computation is what you're doing with all those SET blocks one after another.

I meant composition (my mistake).
But I didn’t use SET, I used (my own implementation of) LET.

Right, sorry.