I’m preparing Sortlab, a project to facilitate comparison of data sorting algorithms.
So far I’ve thought that Sortlab should offer the following features:
A choice of series to be ordered:
a. different lengths
b. different key types
c. varying degrees of pre-sortedness
d. optional seeds, for reproducibility
e. with/out non-key data (“content”)
Accurate processing time measurement
Data logging (designs, input, results, timestamps / processing times)
…
What other features, if any, do forum users think it should offer?
I'm wondering about 1e. How will the length of the record affect the result? Are you thinking about wide enough records so that the computer's caching behavior dominates the asymptotic order of growth?
My initial plan was to leave implementing algorithms to users, and concentrate on the infrastructure to compare any set of algorithms. But on second thought it seems more realistic for me to provide at least a few examples.
In my experience sorting a sequence of simple data elements (e.g. numbers) asks for somewhat different code (details) from sorting a sequence where each element is a data structure consisting of a key and “content” (or a key-value pair). It doesn’t matter though how much content goes with each key.
For Sortlab I’m trying to build a function (constructor) that will report another function (counting comparator). The latter will be a two way comparator, taking two input values and reporting either true or false, and it will produce one desired side-effect: increase a counter.
BTW “statistic” is an upvar in the latter block, and so its name can be changed for every use case. Is there a way the block itself can know what the upvar is actually called? (such that, in this case, the upvar’s user-defined name can be part of what the block reports)
I think the bug is that the COUNTER input is declared to be of type Predicate (I think you meant Reporter but that's not the key problem), so there's a ring in the block where that input goes, but when you drag a variable into a ringed slot, the ring disappears, on the theory that the variable contains the desired value, so you don't want a reporter that reports the variable. But this time you do, so you have to ringify TALLY after inserting it in the slot.
OK, thx! ( … for the trouble - changing the data type or employing a ring didn’t help, alas)
Here's another question: for Sortlab I'm also trying to implement non-comparison sorting. For example I made a kind of bucket sort algorithm (or, technically, it may be pigeon hole sort?), which when applied on a shuffled list of integers within a limited range, needs much more run time than I expected (non-comparison sorts are supposed to be really fast in specific cases like this, but in reality Snap!'s standard sort is much much faster than my block):
Is it because it traverses the original data item-by-item, so without employing a higher order function? I measured that the FOR EACH loop is the one that uses most of the run time by far. Is there a HOF that I could use? Did I overlook something (else)?
WARP does speed it up execution somewhat: true.
I’m not sure what “Live code” does - my system actually refuses to execute when “Live code” is engaged.
Even so, the bucket / pigeonhole sort is way slower than Snap!’s standard sort, and I still assume that’s because no HOF (working on an entire list) was applied.
Maybe I'm missing something, but HOFs aren't magic; you'd have to use a HOF instead of the FOR EACH, not inside it or before it. I don't offhand know how to do that without losing the whole virtue of bucket sort, namely looking at each value only once. So bucket sort does best if there are fewer buckets than data values, and you don't care about order within a bucket. My standard example is that you want to do a bulk snail mailing to all Berkeley students. The postal service requires that you bundle all the letters by zip code in order to get bulk rates. There are, I think, about 30,000 Berkeley students, and they pretty much all live in zip codes 947xx, so you could have 100 buckets. (Fewer, if you wanted to be really careful about which individual zip codes are residential, but that would hair up computing which bucket holds each address, so probably not worth it.) You could have one Other bucket for addresses outside 947, and sort those with some other algorithm; it doesn't matter which, because I'd be surprised if there are 1000 of them.
Also, for small input data, the virtue of a compiled sort (which for us means running in JS rather than in Snap! ) outweigh the asymptotic speed of an algorithm. I tried it with 100,000 input values (and just one run instead of 10; I'm not sure how much 10 trials with the same input data helps smooth over happenstance). Alas, the primitive sort still beat you by a factor of 1000. I don't have the courage to try it with 10,000,000 values, which would take forever, but in theory it should slow down the primitive sort more than it slows you down.
It occurred to me that if somehow BUCKET LIST (ha ha, by the way) were linked rather than an array, that would way slow down the REPLACE ITEM. But I checked, and it isn't.
I sorted 40,000 (fictitious) Berkeley student records using bucket sort with HOFs, reaching about 2/3 of the speed of Snap! sort (and perhaps it can be made even faster?).
I devised a “trick” enabling the use of an HOF (MAP) for a single pass through the list of data to be sorted - it’s slightly reminiscent of bead sort, I guess (but applying only one “bead” for each record):
The above code creates one “bucket list” for each record, with only a single bucket “filled”, the other buckets are empty lists. After all of the bucket lists have been created, FLATTEN OF () wraps up the filled buckets and discards the rest.
I discovered a few incorrect assumptions on my side:
My original "bucket sort" was, indeed, more of a pigeon hole sort: the number of buckets, or pigeon holes, was in the same order of magnitude as the size of the data to be sorted. This caused a lot of extra processing time. Instead I should have less used but larger buckets. (Thx @bh)
I wasn't aware of Snap!'s (recently added?) [sorted] OF () native function, or if I did at some point notice it I must have assumed it was about as fast as the library's SORT () ORDERING WITH (), whereas in reality it's so much faster! (Thx @dardoro).
The algorithm I devised for applying HOF's in a single pass of the data (my previous post, #14) is quite creative - even if I say so myself - but also unnecessary .
Anyway, with the new native [sorted] OF () function, sorting in Snap! has become (even more) blazingly fast, at least for simple (ordinal) data. I wonder how it can be used to sort more complicated items, and if there are any special cases left that can be sorted even faster (using [sorted] OF () where applicable within any alternative algorithm) - I'm going to look into that over the next weeks or so ... "don't hold your breath" (@bh: sorry about the trademark violation )
The [sorted] OF () function is as yet undocumented for users (I think).
This is what I found, so far:
It will sort numbers and strings, text before numbers, low values before high.
It will sort various other data types such as Booleans, reporters and commands - I haven’t investigated (yet) whether there are any data types it doesn’t sort, or how various data types are sorted.
It will sort lists by item 1; insofar as this is inconclusive, item 2 will be used, etc.
It’s very much faster than the library’s SORT () ORDERING WITH (()<()) … unless the data are long strings (for really really long strings it’s actually slower).
I propose the List utilities libary’s SORT () ORDERING WITH () function (and its copy in APL primitives, and the implementation-wise identical SORT () BY () from the FDA library) be replaced by something like:
Help text:
I tried this new sort function for non-standard sorting on our earlier fictitious student snail-mailing:
List utilities library's SORT () ORDERING WITH () function (17 seconds on one of my systems)
A "prepsort" block I made earlier, calculating the key function values only once instead of with every comparison. It builds on the same library function doing the actual sorting (almost 2 seconds).
My new () SORTED BY KEY: () STABLE? () function, with stable? = false (1.3 seconds). It builds on [sorted] OF () doing the actual sorting.
The same function, stable = true (1.1 seconds).
The biggest win has been, and still is, calculating the key function once. Using [sorted] OF () instead of the library’s SORT () ORDERING WITH () makes a difference, too - actually the key calculation is dominant over the sort. The runtime difference between stable vs. non-stable sort, to the advantage of the stable version, surprised me: the stable version has an extra step of adding indices between the keys and the data - my explanation is that after “meeting” the (unique) indices the sort algorithm won’t have to look any further into the data to complete the sorting.
So we're no longer talking about bucket sort? Because in a non-comparison sort the key of each record will be computed only once anyway.
Because special cases such as bucket sorting are the reason you can't just use the system sort function and be done with it. That's the right thing to do if the number of records is of the same order of growth as the number of possible key values, but if there's an imbalance you have to look in Knuth volume 3 to figure out which algorithm to use.
Operating system sort programs are super complicated. In order to be as fast as possible, they have to take into account the processor's cache geometry (or the virtual memory geometry if there are way more records than fit in memory). And then you'd like to know how ordered the data are before sorting. You can't really find out precisely without doing the sorting, but if you have billions of things to sort it might be worthwhile to pick 100 consecutive records at a random point in the data and measure the orderedness of that sample. But that's a total guess; I know nothing about statistics. (And proud of it! :~) ) The width of a record vs. the width of a key -- which is another way of saying "the [lg of the] number of possible key values."
Yeah, that surprised me, too, although the difference isn't big enough for me to have a Theory about it, without more examples. I'm not sure I believe your theory, though, because it's not good enough for the program not having to look further; it has to know that it doesn't have to look further.
PS Your "prepsort" thing really would like to know what the key function is; if it's something like ITEM 3 OF, it's not clear that computing it is faster than finding the already-computed value in some data structure.
With the Variable menu’s “new” function Snap!’s default sort option has become so extremely fast, that other (non-JS) algorithms don’t stand a fighting chance in trying to improve on its performance, even in special cases. See the example below.
Too much of a good thing?
It’s great to have so much (sorting) power at hand, enabling applications to run faster or even become feasible at all. On the other hand, sorting is a fundamental concept in computer science, and in comparison with [sorted] OF (), any other algorithm, even if theoretically superior, is a slug ... reducing teaching of sorting algorithms to a purely theoretical exercise.
And so ... ?
This is not a plea to remove this feature, or make it slower on purpose, but rather to investigate how alternative (sorting) algorithms could be supported with faster basic functions, or otherwise. And perhaps the Snap! team are already working in that.
Now for my example, a selection of only the 100 lowest values from a shuffled list of numbers 1 .. 10,000:
(30 ms) (compiled!), with 10 or 11 as cutoff value.
(262 ms) a home-made recursive selection sort, using as selection tool, and keeping non-selected data for further processing through and .
(34 ms) a fairly optimized tournament sort, building on both and .
(273 ms) List utilities library’s .
(3733 ms) a home-made merge sort (no underlying HOFs).
As measured on an iPad Pro-2 (iOS, Safari) … in other environments, results may be somewhat different.
Discussion
The difference between (1) and (5) illustrates how much faster the Snap! 9 sort service is in comparison with the older library version; in some environments (e.g. Windows PC), the difference may be even larger, while in rare cases (e.g. very large strings) the library version is actually faster.
An efficient general-purpose algorithm (6) without any underlying HOFs is even one order of magnitude slower than the library version (5).
I would have expected KEEP (2) to be much faster than a full sort, since it’s a single-pass algorithm, whereas a general-purpose sort algorithm such as (1) would need at least 15 passes (2 log 40,000). Is it because of the callback function that (2) is relatively slow? Perhaps Snap! could eventually offer a faster (and probably less versatile) second version of KEEP? Like: (and, by the way, its mirroring ) - these are just examples of course.
Even with a really small selection, specialized algorithms for picking a top-n selection (3, 4) will fail to outperform a full sort, which is rather odd IMO. Selection sort (3) will perform better of course if the selection is smaller, and (much) worse if it is larger; tournament sort (4) runtime is pretty much the same for many selection sizes.
My stable sort implementation has the user-specified sort key as item 1, and a unique index (representing the position of the record in the original dataset) as item 2. So after considering index 2 all records are guaranteed to be totally sorted, and I suppose Snap! 9's [sorted] OF () is aware of that.
It’s up to the user to decide. EDIT: May be I'm going to build a block that will select a "fairly optimal" sorting strategy for any user request.
)
)
Live coding... ~50% speed-up
.
)
function Snap!’s default sort option has become so extremely fast, that other (non-JS) algorithms don’t stand a fighting chance in trying to improve on its performance, even in special cases. See the example below.
(compiled!), with 10 or 11 as cutoff value.
as selection tool, and keeping non-selected data for further processing through 
and 
.
.
(and, by the way, its mirroring 
) - these are just examples of course.