I think the intuition here runs something like this: 1) longer code means more work
2) more work means slower implementation But performance depends not only on the code, but on the data, and nub will in some cases significantly reduce the amount of data. So this winds up being one of those issues where details of the surrounding context can have a big influence. That said, the "APL way" (or perhaps the "J way") might be to run nub on the inputs to the system, avoiding the need to repeat that work for all elements. That said, in old versions of J, nub had a catastrophically bad implementation for large datasets (for example: 1e8 elements, each the result of the sha1sum algorithm). [This problem could be avoided by replacing the nub algorithm with: sort the sequence and eliminate elements which match their immediate predecessor.] Then again, for small datasets none of this matters, and something short, simple and sweet tends to be the best approach. FYI, -- Raul On Thu, Oct 25, 2018 at 1:56 PM 'Mike Day' via Programming <[email protected]> wrote: > > I seem to have raised a hare in my reply to Skip's original post on 23/10. > > I defined a convenient one-liner for intersection, > ix =: ([ -. -.) NB. set intersection > as it was sufficient to the discussion - I wanted to reinforce the idea > that > it was better to take the gcd of the list. > > However, two or three questions arise: > a) what is an efficient method for finding set intersection, > b) should A |∩| B <==> B |∩ |A ? > c) should the nub (~.) be returned? > > I forget whether all APLs have intersection, |∩ | > My installation of Dyalog APL certainly does. It is not commutative, > and does not return the nub: > (hopefully, the APL primitive's graphic should appear as an inverted u) > 1 2 3 3 3 ∩ 3 3 3 3 3 4 5 6 > 3 3 3 > 3 3 3 3 3 4 5 6 ∩ 1 2 3 3 3 > 3 3 3 3 3 > > (Is it curious that the inverse (!) APL primitive, union, is also non- > commutative? : > 1 2 3 3 3 ∪ 3 3 3 3 3 4 5 6 > 1 2 3 3 3 4 5 6 > 1 2 3 3 3 ∪⍨ 3 3 3 3 3 4 5 6 NB. with commute operator > 3 3 3 3 3 4 5 6 1 2 > 3 3 3 3 3 4 5 6 ∪ 1 2 3 3 3 > 3 3 3 3 3 4 5 6 1 2 > ) > > "My" ix behaves with similar results to APL's ∩ : > 1 2 3 3 3 ix 3 3 3 3 3 4 5 6 > 3 3 3 > 3 3 3 3 3 4 5 6 ix 1 2 3 3 3 > 3 3 3 3 3 > > as does the other candidate for intersection, based on e. > which I'm calling here "ixe" > ixe =: [#~ e. > 1 2 3 3 3 ixe 3 3 3 3 3 4 5 6 > 3 3 3 > 3 3 3 3 3 4 5 6 ixe 1 2 3 3 3 > 3 3 3 3 3 > > If performance is an issue, I had thought ixe was somewhat faster > and used less space, but it seems to depend on the relative > sizes of the arrays: > > ts =: 6!:2 , 7!:2@] > ts'# a ix b' > 0.0118795 17536 > ts'# a ix~ b' > 0.0638942 1.67785e7 > ts'# a ixe b' > 0.0230684 4.1975e6 > ts'# a ixe~ b' > 0.0296806 1.05805e6 > > The ratios in both time and space-usage between the verb and its > commutation are much larger for ix than for ixe . > > We might expect ixe to be faster if the larger array is sorted: > sb =: /:~ b > ts'# a ix sb' > 0.00943728 17536 > ts'# a ix~ sb' > 0.0587149 1.67785e7 > ts'# a ixe sb' > 0.0243626 4.1975e6 > ts'# a ixe~ sb' > 0.0286817 1.05805e6 > > but if anything, ix improves more than ixe with sorting. > > Having raised the behaviour of APL's union, ∪, here are > a couple of J emulations, one using -. , the other with e. > > u =: ( [, -.~) NB. model APL's union > 1 2 3 3 3 u 3 3 3 3 3 4 5 6 > 1 2 3 3 3 4 5 6 > 1 2 3 3 3 u~ 3 3 3 3 3 4 5 6 > 3 3 3 3 3 4 5 6 1 2 > > and > ue =: [, ]#~-.@e.~ > 1 2 3 3 3 ue 3 3 3 3 3 4 5 6 > 1 2 3 3 3 4 5 6 > 1 2 3 3 3 ue~ 3 3 3 3 3 4 5 6 > 3 3 3 3 3 4 5 6 1 2 > > Here are a few ts tests on a slight modification of those larger arrays: > a =: a, 1000000 + a NB. append 1000 elements not in b > ts'# a u b' > 0.0645302 1.67784e7 > ts'# a ue b' > 0.0710777 1.67784e7 > ts'# a u~ b' > 0.0296056 8.39808e6 > ts'# a ue~ b' > 0.0420709 8.38995e6 > > So - are there better one-liners out there? And do these verbs produce > useful results? > > Cheers, > > Mike > > On 23/10/2018 16:44, Skip Cave wrote: > > So a new set of test data: > > > > h=.4 5$ 1 5 3 4 5 3 5 4 5 6 5 3 7 5 8 3 8 5 1 5 > > > > h > > > > 1 5 3 4 5 > > > > 3 5 4 5 6 > > > > 5 3 7 5 8 > > > > 3 8 5 1 5 > > > > > > ix / h > > > > 5 3 5 > > > > ~. ix / h > > > > 5 3 > > > > > > How to combine it all into one function f ? > > > > f =. ~. ix / > > > > f h > > > > |domain error: f > > > > Skip Cave > > Cave Consulting LLC > > > > > > On Tue, Oct 23, 2018 at 9:59 AM Jimmy Gauvin <[email protected]> wrote: > > > >> In the same vein : > >> > >> ~. ix/ g > >> > >> On Tue, Oct 23, 2018 at 10:41 AM Roger Hui <[email protected]> > >> wrote: > >> > >>>> ix&.>/ <"_1 g where ix is Mike's intersection verb. > >>> > >>> > >>> > >> > > > > --- > This email has been checked for viruses by Avast antivirus software. > https://www.avast.com/antivirus > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
