@Mike: what were your a and b which you used for performance?
R.E. Boss -----Oorspronkelijk bericht----- Van: Programming <[email protected]> Namens 'Mike Day' via Programming Verzonden: donderdag 25 oktober 2018 19:56 Aan: [email protected] Onderwerp: [Jprogramming] Set Intersection - was Re: Common factors 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
