I had a look at using my earlier offerings, ix and u, which I'd
observed to be non-commutative in my note of around 25 October.
The best derivations I found were
ixcom =: ix #/@:|:@:(<./"3)@:((~. ,.~ #/.~)@:/:~&>)@:; ix~
ucom =: u #/@:|:@:(>./"3) @:((~.,.~#/.~)@:/:~ every )@:; u~
which display as pretty verbose if one applies "f. "
They produce the same sorted results as IS_reb and UN_reb, and
are probably a bit slower; "timer" just looks at elapsed time:
timer'#a (ixcom -: /:~@: IS_reb) a + 49999'
+-----+-+
|4.945|1|
+-----+-+
timer'#a (ucom -: /:~@: UN_reb) a + 49999'
+-----+-+
|5.339|1|
+-----+-+
No improvement so far.
So it occurred to me to see if there was anything relevant in Dyalog
APL's "dfns" workspace, a compendium of many interesting and often useful
examples of John Scholes' "dynamic functions" (hence "dfns"). Roger has
had a hand in later developments, I believe.
Indeed, there's a new (to me) function, "bags" which packages anumber
of "multiset" or "bag" operations, including union and intersection.
I'll list the whole thing below, but just show a few example J
verbs/adverbs
and leave the rest as an exercise!?
The key to the approach is called "progressive dyadic", which involves a
ranking a concatenation of both arrays, which perhaps goes some way to
explaining its pedestrian performance.
NB. Progressive dyadic - attributed to Bob Smith in Dyalog DFNS workspace
pd0 =: /:^:2 @ (i.~ ,&'')~
pd =: 1 : 0
:
((#x){. x pd0 x,y) u (#y){. x pd0 y,x
)
pde =: e. pd
pdi =: i. pd
mad =: [#~ -.@:pde
ubag =: [, mad~ NB. union
ixbag =: [#~ pde NB. intersection
e_bag =: pde NB. progressive membership
i_bag =: pdi NB. progessive index
Using Dyalog's example,
A =: 2 1 2 1 3 2 5
B =: 3 4 2 1 2 3
A ixbag B
2 1 2 3
A ubag B
2 1 2 1 3 2 5 4 3
A i_bag B
4 7 0 1 2 7
A e_bag B
1 1 1 0 1 0 0
... and as I warned, the time-performance is poor:
timer'#a (ixbag -: /:~@: IS_reb) a + 49999'
+------+-+
|13.202|1|
+------+-+
timer'#a (ubag -: /:~@: UN_reb) a + 49999'
+------+-+
|13.583|1|
+------+-+
I expect the performance can be improved a bit, but
probably not so much as to compete with the _reb verbs.
Here's an attempt at displaying the "bags" operator,
commented with J's NB.'s :
NB. ∇bags←{ ⍝ Multisets / bags.
NB. [1] pd_←{ ⍝ "progressive dyadic
..." (Bob Smith).
NB. [2] r←(⍴⍵)⍴⍋⍋(⍺,⍬)⍳⍵,⍺
NB. [3] l←(⍴⍺)⍴⍋⍋(⍺,⍬)⍳⍺,⍵
NB. [4] l ⍺⍺ r
NB. [5] }
NB. [6] pde←∊pd_ ⍝ progressive dyadic epsilon.
NB. [7] pdi←⍳pd_ ⍝ progressive dyadic iota.
NB. [8] mad←{(~⍺ pde ⍵)/⍺} ⍝ multiset asymmetric
difference.
NB. [9]
NB. [10] aa←⍺⍺ ⋄ fn←⍬⍴⎕CR'aa' ⍝ '~', '∪', etc.
NB. [11]
NB. [12] 0::⎕SIGNAL ⎕EN ⍝ signal any error to caller.
NB. [13]
NB. [14] 0=⎕NC'⍺':{ ⍝ monadic call.
NB. [15] '∪'≡fn:⍵,⍬ ⍝ unique (noop for vector).
NB. [16] ⎕SIGNAL 16 ⍝ unexpected operand:
nonce error.
NB. [17] }⍵
NB. [18]
NB. [19] '≡'≡fn:((⍴⍺)≡⍴⍵)>0∊⍺ pde ⍵ ⍝ match.
NB. [20] '≢'≡fn:((⍴⍺)≡⍴⍵)≤0∊⍺ pde ⍵ ⍝ natch.
NB. [21] '~'≡fn:⍺ mad ⍵ ⍝
without. ⍺~⍵
NB. [22] '∪'≡fn:⍺,⍵ mad ⍺ ⍝
union. ⍺,⍵~⍺
NB. [23] '∩'≡fn:((⍺ pde ⍵)/⍺) ⍝ intersection.
NB. [24] '∊'≡fn:⍺ pde ⍵ ⍝ progressive membership.
NB. [25] '⍳'≡fn:⍺ pdi ⍵ ⍝ progressive dyadic iota.
NB. [26] 3=⎕NC'⍺⍺':⎕SIGNAL 16 ⍝ unexpected operand:
nonce error.
NB. [27] '§'≡⍺⍺:(⍺ mad ⍵),⍵ mad ⍺ ⍝ multiset symmetric
difference (msd).
NB. [28] ⎕SIGNAL 16 ⍝ unexpected operand:
nonce error.
NB. [29] }
NB. ∇
Might be useful for developing J ideas,
Mike
On 30/10/2018 09:46, R.E. Boss wrote:
IMO we should interpret the intersection and the union of two (multi)sets (sets X with
X >:&# ~.X) in the same way as is done by the GCD and the LCM of two numbers.
So for two numbers N and M with (multi)sets of primefactors A and B, we should
have (N +. M) = */(A IS B) and (N *. M) = */ (A UN B), with IS=intersection and
UN = union of the (multi)sets A and B.
Obviously we require (A IS B) =&(/:~) B IS A and also (A UN B) =&(/:~) B UN A
for all (multi)sets A and B.
E.g.
1 2 3 3 3 IS 3 3 3 3 3 4 5 6
3 3 3
1 2 3 3 3 UN 3 3 3 3 3 4 5 6
1 2 3 3 3 3 3 4 5 6
What are elegant and efficient J-definitions for IS and UN?
I have constructed
UN_reb=: ([:(~.@{.#~ {. >.//.{:) |:@,&(({.,#)/.~))
and
IS_reb=: ([:(~.@{.#~ {. <.//.{:) ([|:@, ],~ 0,.~ -.~&:({."1),
-.&:({."1))&(({. , #)/.~))
1 2 3 3 3 UN_reb 3 3 3 3 3 4 5 6
1 2 3 3 3 3 3 4 5 6
1 2 3 3 3 IS_reb 3 3 3 3 3 4 5 6
3 3 3
1 2 3 3 3 UN_reb~ 3 3 3 3 3 4 5 6
3 3 3 3 3 4 5 6 1 2
1 2 3 3 3 IS_reb~ 3 3 3 3 3 4 5 6
3 3 3
a=: 1e7?.@#1e6
ts'a UN_reb a+499999'
0.76631908 4.6996013e8
#a UN_reb a+49999
12186812
ts'a IS_reb a+499999'
0.76073743 3.3554592e8
#a IS_reb a+49999
7813188
R.E. Boss
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
---
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
