[Jprogramming] K-sets - bitmap representation of sets. WAS: Partitions

[Erling Hellenäs]

Mike's trick on the last line might be what's needed. /Erling

On 2017-11-13 16:31, Erling Hellenäs wrote:
> Hi all!
>
> A new combbit with the limit lifted. Unfortunately somewhat slower.
>
>    x=:12
>    y=:24
>    ts'x combbit y'
> 0.213853 2.34326e8
>    ts'x combbitOld y'
> 0.108748 1.33655e8
>
> combbit=: 4 : 0
> or=.23 b.
> lshift=.33 b.
> lrot=. 32 b.
> shift=. 2 ((_2 lrot 2 #: [) or _1 lshift ])/\ ]
> n=.<:##:_1 (32 b.) 1
> l=.>.y%n
> p=.y->:i.>:d=.y-x
> k=.<"_1(<.p%n)|."0 1((l-1)$0),"1 0 [2 ^&.x: n#:p
> z=.(d$<(l,0)$0),<(l,1)$0
> for. i.x do. z=. k (or)&.>  ,.&.>/\. ([:shift 0,])&.> z end.
> >,.&.>/((-l){.-(n|y),(<.y%n)#n) ([:<[{."1[:#:])"0 1 >,.&.>/z
> )
>
> Cheers,
>
> Erling Hellenäs
>
>
> Den 2017-11-13 kl. 11:37, skrev Raul Miller:
>> Hmm... nice.
>>
>> combbit pulls out way ahead by working with a more compact and fixed
>> width representation, which makes sense. You give up being able to do
>> things like 3 combbit 100, but that might not be relevant in some
>> contexts.
>>
>> That said, I'd probably put those -: test cases in asserts rather than
>> running them as readable output. I'd also be tempted to make a few
>> other changes. (Most of which I've not included here, for
>> comparability purposes.)
>>
>> Also, of course, when I run this I get different times. But timing
>> differences of up to 30% are typical and anything less than a factor
>> of 2 isn't really interesting.
>>
>>     x=:5
>>     y=:10
>>     1000 ts 'x comb y'
>> 2.7068e_5 50944
>>     1000 ts'x combbool y'
>> 2.3684e_5 22528
>>     1000 ts'x combbit y'
>> 1.8143e_5 21376
>>     1000 ts'x combbitub y'
>> 3.1611e_5 13824
>>     1000 ts'x CombBool y'
>> 2.1586e_5 14976
>>     1000 ts'x CombBit y'
>> 1.3287e_5 15232
>>     1000 ts'x bitcomb y'
>> 1.8703e_5 50688
>>     1000 ts'x combboolT y'
>> 2.1642e_5 15744
>>
>>     x=:12
>>     y=:24
>>     ts 'x comb y'
>> 0.705435 9.02647e8
>>     ts'x combbool y'
>> 0.240168 2.82336e8
>>     ts'x combbit y'
>> 0.124814 1.33655e8
>>     ts'x combbitub y'
>> 0.123766 1.17444e8
>>     ts'x CombBool y'
>> 0.234092 2.33133e8
>>     ts'x CombBit y'
>> 0.121827 1.33654e8
>>     ts'x bitcomb y'
>> 1.30437 1.34218e9
>>     ts'x combboolT y'
>> 0.216018 2.33135e8
>>
>>     x=:55
>>     y=:60
>>     ts 'x comb y'
>> 48.7158 1.40301e10
>>     ts'x combbool y'
>> 5.9218 2.29064e9
>>     ts'x combbit y'
>> 0.829234 6.75567e8
>>     ts'x combbitub y'
>> 0.6971 6.71092e8
>>     ts'x CombBool y'
>> 5.56716 1.71798e9
>>     ts'x CombBit y'
>> 0.765956 6.75566e8
>>     NB.ts'x bitcomb y' -limit error
>>     ts'x combboolT y'
>> 5.67477 1.71798e9
>>
>> Thanks,
>>
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm