@xpqz I've been planning to write a blog post about 2020's phase 2, but I simply don't have the time. Would you be interested in writing a guest blog post? I'd send you all the best (imo) solutions (which you are free to tweak, like this), and then you can write as much (or little) as you want about each one.
Some interesting stuff there. I wrote up a long thing on the Balance the Scales problem -- I see that Horowitz and Sahni's alg is highlighted. Fast, but not guaranteed to find a perfect solution.
@xpqz Feel free to include what you wrote. The style is completely up to you. If you want to briefly talk about all the problems, and then go into depth about a single one, then that's perfectly fine too.
Doing something where ≠ is exactly what I need, but unfortunately I am not working in 18.0 yet. Took a look at aplwiki.com/wiki/Nub_Sieve#APL_models at some ways to implement it in older versions.
Hit a syntax error with the train expressions in 17.1 due to the atop operator changes, and decided to just rewrite using a simple "@" approach. There are nice ways to implement it using ⌽ and = as well, but you need to start handling more edge cases.
I'm guessing the UniqueMask function in there was only for education purposes, the performance on it is terrible. Comparing the other functions mentioned in there vs the @ approach:
@JoshD Nice! How simple. Bracket indexing is fast, and I think that is simply what @ is doing under the covers in this case. Also, Marshall's v18 implementation of ≠ will beat the @ or bracket index version in other cases. Certainly for a matrix.
Though it looks like for simple vectors maybe a little optimization was left on the shop floor.
The reason ≠sa is so fast (25 characters per nanosecond) is that there's a special case for sorted arguments.
AtUnique is applying some even more special methods: both ∪ and ⍳ will be done with lookups on bit tables stored in vector registers. I probably didn't apply that method to ≠. It's not exactly trivial to write and because it can't be branchless the performance is less predictable. It will be slower for short vectors and some medium-length ones, so it's probably only valid to always use it on vectors over 512 elements or so.
Also ⍳ is doing a reverse lookup so it can build a table on ∪x instead of the much longer x.
@PaulMansour Yeah I only tested my case of simple vectors, will shift over to v18 ≠ when I can, but good to note that
@Marshall I guess that means the optimizations won't happen if you pull in data (say from a file or DB) that is already sorted (E.G. if you have an order by in your query)
In the old days, we would sort a matrix and do a shift and compare to flag the first occurrence of each item, and then sort it back. If the array was already sorted, you obviously did not have to sort/resort.
Given:
firstOccuranceSortedMatrix←{ f←∨/⍵≠¯1⊖⍵ f[⍳×⍴f]←1 f }
@PaulMansour Well yeah, the trick is not writing the code but writing the code that knows to call it. I probably used a pretty similar method, which might have differences with different shapes, or architectures.
