Oops - sorry, I thought I'd included their defs. I didn't keep the
scratch script,
but, IIRC,
a =: 1000?1000000 NB. could have used ?. for consistency, of course
b =: ?~1000000 NB. ditto
I think I _did_ show
sb =: /:~ b NB. or now I've seen it in stdlib, sort b !
The later modification, a =: a, 1000000 + a ,
clearly doubled the size of a, and ensured that there was
something to do for the "union" verb.
Cheers,
Mike
On 26/10/2018 09:01, R.E. Boss wrote:
@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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
