Thanks for the responses.
Raul, it looks like the expressions you posted are missing the exclusions
part of the problem which we can see if substitute the values from my
original example to replace ({.HCs):
$I.+./HCmask*/ .=+./"1(a.{~15 22 33 44)=/allHands
103776
Pascal's version looks like it is giving a result like we would expect:
$tst1=. allHands selhands (15 22{a.);33 44{a.
17296
]rcix=. (]{~[:5&?#) tst1
1515605 651644 2267264 157894 933164
a. i. rcix{allHands
15 22 29 36 41
15 22 26 37 47
4 11 15 22 50
15 18 22 32 43
15 22 26 38 43
I modified "selhands" to return the indexes into "allHands" rather than the
explicit results as this is more easily turned into a score.
selhands=: 4 : 0
'in ex' =. y
I. ((# in) = (ex +/@:e."1 ]) -~ in +/@:e."1 ]) x
)
I like the elegance of the expression; however, the performance does not
appear to be better:
ixs=. i.100 NB. Do only 100 cases
6!:2 'tst100=. (<allHands) selhands&.><"1 (<"1 ixs{,/inclIx{"1/HCs),.<"1
ixs{,/exclIx{"1/HCs'
49.7256
#,/inclIx{"1/HCs NB. How many altogether?
1624350
49.7256*100%~1624350 NB. Scale time up by total #%100 ->
estimate of total time
807718
0 60 60 #: 49.7256*100%~1624350 NB. Estimated total time in h m s
224 21 57.7836
Thanks again to both of you for looking at this.
The sizes of the arguments make it easy to max out the 64GB RAM I have on
my desktop machine and I have discovered that I can run no more than about
three processes in parallel on the version I proposed earlier but this may
be enough for a one-time invocation.
Cheers,
Devon
On Mon, Aug 9, 2021 at 11:14 AM 'Pascal Jasmin' via Programming <
[email protected]> wrote:
> is this 10x faster than your original? selhands uses arbitrary length
> include/exclude list where all of include, and any of exclude condition.
>
> c =. 5 comb 52
>
> selhands =: 4 : 0
>
> 'in ex' =. y
>
> (] #~ (# in) = (ex +/@:e."1 ]) -~ in +/@:e."1 ]) x
>
> )
>
> timex' c selhands 15 22 ; 33 44'
>
> 1.17982
>
>
>
>
>
> On Sunday, August 8, 2021, 04:42:30 p.m. EDT, Devon McCormick <
> [email protected]> wrote:
>
>
>
>
>
> Hi,
>
> I'm stuck on getting decent performance for the following problem.
> Say we have a list of all 5-card hands from a deck of 52 cards:
> load '~addons/stats/base/combinatorial.ijs'
> $allHands=. 5 comb 52
> 2598960 5
>
> We also have a list of all 4-card combinations:
> $HCs=. 4 comb 52
> 270725 4
>
> I want to find all hands possible using any two cards from a given row of
> *HCs
> *but excluding those with either of the other two cards from the same row.
>
> For example, for this randomly-chosen row of *HCs*, which hands include the
> first two but exclude the second two?
> (]{~[:?#) HCs
> 15 22 33 44
> (#,+/) include=. 2=+/"1 allHands e."1 ] *15 22*
> 2598960 19600
> (#,+/) exclude=. 0=+/"1 allHands e."1 ] *33 44*
> 2598960 480200
>
> So there are 17,296 hands we want:
> +/include*.exclude
> 17296
>
> Check five at random to verify that these look correct:
> ]rcix=. (]{~[:5&?#) I. include*.exclude
> 1002358 1165504 2176134 1960355 56685
> rcix{allHands
> 4 15 22 37 39
> 5 15 22 34 45
> 15 18 20 22 39
> 12 15 22 27 39
> 0 4 6 15 22
>
> These look good because all include (15,22) but exclude any of (33,44).
>
> However, this is only one possibility for this single row of *HCs* but we
> have six variations for this row based on choosing all possible pairs of
> indexes into the row of *HCs* to include,
> |:inclIx=. 2 comb 4
> 0 0 0 1 1 2
> 1 2 3 2 3 3
>
> And six corresponding pairs to exclude (indexes into the row of *HCs*):
> |:exclIx=. (i.4)-."1 ] 2 comb 4
> 2 1 1 0 0 0
> 3 3 2 3 2 1
>
> In the above example, we did the one of the six corresponding to *inclIx
> *of
> (0,1) and *exclIx *of (2,3). Is there a way to do all six sets for each
> row of *HCs* compared to each row of *allHands*?
>
> We might start by reducing the sizes of our arrays by making them character
> instead of integer:
> allHands=. allHands{a. [ HCs=. HCs{a.
>
> However, we quickly see that we run out of memory for the expression we
> would like to write:
> include=. 2=+/"1 allHands e."1 / inclIx{"1 / HCs
> |out of memory
> | include=.2=+/"1 allHands e."1/inclIx{"1/HCs
>
> A little arithmetic shows us the extent of the problem:
> (],*/) #&>(,/inclIx{"1/HCs);<allHands
> 1624350 2598960 4221620676000
> 10^.1624350*2598960
> 12.6255
>
> So we have a 4-trillion-element intermediate result which is a bit much.
>
> Our immediate thought might be to do this in pieces by selecting successive
> portions of the right-hand part (*HCs*) of this expression. We would like
> to work on integral pieces for neatness, so we look at the prime factors of
> the size of *HCs* and select the product of a couple of them to be the
> "chunk size":
> q:#HCs
> 5 5 7 7 13 17
> ixs=. (ctr*chsz)+i.chsz [ ctr=. 0 [ chsz=. */5 5
>
> [The expression for the next chunk would be
> ixs=. (ctr*chsz)+i.chsz [ ctr=. >:ctr
> and so on.]
>
> Timing how long one piece takes and scoring the results by simply adding up
> their indexes into *allHands*, we get this:
> 6!:2 'sel=. (2=+/"1 allHands e."1 / inclIx{"1 / ixs{HCs) *. 0=+/"1
> allHands e."1 / exclIx{"1 / ixs{HCs'
> 11.5105
> scores=. 0$~#HCs NB. Initialize scores vector
> 6!:2 'theseScores=. +/&>I.&.><"1 |:+./"1 ] 0 2 1|:sel'
> 0.687056
> 6!:2 'scores=. (theseScores) ixs}scores'
> 6.4e_6
> +/11.5105 0.687056 6.4e_6 NB. Total time per chunk
> 12.1976
> 12.1976*(#ixs)%~#HCs NB. Total estimated time
> 132088
> 0 60 60#:12.1976*(#ixs)%~#HCs NB. Estimated time: h m s
> 36 41 27.8104
>
> So we should be able to do it this way in about 36 hours. Can someone
> think of a faster method to accomplish this? The memory requirements seem
> modest enough that I should be able to run five to ten processes
> simultaneously on this to reduce the overall time but is there a way to
> speed up the basic selection?
>
> Thanks,
>
> Devon
>
>
> --
>
> Devon McCormick, CFA
>
> Quantitative Consultant
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
--
Devon McCormick, CFA
Quantitative Consultant
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
