> It's clear that f1 could be made faster in C by modifying ~:'s code, Indeed. Since the data d is small range, a small-range algorithm can be quite a bit faster. Even a full-range hashing algorithm can be faster.
~:d 0.0393 small range 0.0134 hashing 0.0208 On Thu, Jun 12, 2014 at 6:15 PM, Marshall Lochbaum <[email protected]> wrote: > This solution is quite elegant--for those who didn't read the link, the > verb is > > f3 =. 2 > (i.~ (] - {) /:@/:) > > However, it's about as fast as f2, that is, a bit slow. I'll have to > stick with f1. > > It seems I had forgotten the blazing speed of ~: . It's clear that f1 > could be made faster in C by modifying ~:'s code, but that algorithm is > a bit too involved to write in J. I don't think any other approach will > dethrone f1, although that's an easy thing to be wrong about... > > Marshall > > On Thu, Jun 12, 2014 at 10:26:12AM -0700, Roger Hui wrote: > > See http://www.jsoftware.com/jwiki/Essays/Progressive%20Index-Of. > Choose > > items with occurrence counts <: 2 . > > > > > > On Thu, Jun 12, 2014 at 10:17 AM, Marshall Lochbaum < > [email protected]> > > wrote: > > > > > I came across this problem and was wondering if anyone could come up > > > with a solution that is both elegant and fast: > > > > > > Given a list of positive integers, return a mask (or index list) which > > > selects the first two of each unique value in the list. > > > > > > Of course ~: is the solution if you only want the first value. A fast > > > but ugly solution using ~: is > > > > > > f1 =. (] +. ~:@:(*-.)) ~: > > > > > > which relies on the fact that the list is always positive. A more > > > general solution using key, which returns an unordered list of indices, > > > is > > > > > > f2 =. (2&{.)^:(2<#)(<@)/.(;@:) i.@# > > > > > > which isn't exactly pretty, but at least allows you to change the > number > > > of values you want. It's also much slower than f1: > > > > > > d =. 99 , 100 + 1e7?.@$10000 > > > (I.@:f1 -: /:~@:f2) d > > > 1 > > > 6!:2 'f1 d' > > > 0.273576 > > > 6!:2 'f2 d' > > > 1.08829 > > > > > > Any other ideas? > > > > > > Marshall > > > ---------------------------------------------------------------------- > > > For information about J forums see http://www.jsoftware.com/forums.htm > > > > > ---------------------------------------------------------------------- > > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
