Hi all!
The general version of combbit improved. The comparison is with the
limited version.
x=:12
y=:24
ts'x combbit y'
0.125539 2.16831e8
ts'x combbitOld y'
0.107966 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.
if. l=1 do.
a=.((_1 lshift 1 {. ]))&.> z
else.
a=.((_1 lshift 0 { ]),[:shift ])&.> z
end.
b=.,.&.>/\. a
z=.k (or)&.> b
end.
z=.>,.&.>/ ([:<#:)"1 >,.&.>/z
z
)
I hit a strange feature:
a=:,:100000000?100000000
$a
1 100000000
ts'2 */\a'
1.03032 3.22123e9
$2 */\a
0 100000000
Even though 2 */\a gives an empty result, it takes a considerable time
to execute.
Cheers,
Erling Hellenäs
Den 2017-11-14 kl. 06:12, skrev Jose Mario Quintana:
I could not resist... :)
". noun define -. CRLF
CombBit=.
@:(,.&.>/)@:((-@:(5&({::)) {. -@:(4&({::) | 1&({::)) , <.@:(1&({:
:) % 4&({::)) # 4&({::)) <@:([ {."1 #:@:])"0 1 >@:(,.&.>/)@:(3&({:
:)))@:((<@:(2&({::) 23 b.&.> ,.&.>/\.@:((2 (((_2) 32 b. 2 #: [) 23
b. (_1) 33 b. ])/\ ])@:(0 , ])&.>)@:(3&({::))) 3} ])^:(0&({::)))@
:(<@:((1&({::) - 0&({::)) (([ $ <@:(0 $~ 0 ,~ ])) , <@:(0 $~ 1 ,~
])) 5&({::)) 3} ])@:(<@:(<"_1@:(<.@:(6&({::) % 4&({::)) |."0 1 (0
$~ 1 -~ 5&({::)) (,"1 0) 2 ^&.x: 4&({::) #: 6&({::))) 2} ])@:(<@:(
1&({::) - >:@:i.@:>:@:(1&({::) - 0&({::))) 6} ])@:(<@:(>.@:(1&({::
) % 4&({::))) 5} ])@:(<@:(63"_) 4} ])@:(,&(<;._1 ' K Z N L P')@:;)
)
A performance sample is,
stp 111
2 combbit 4
2 CombBit 4
)
┌───────────┬─────┬─────────────┬────────────┐
│Sentence │Space│Time │Space * Time│
├───────────┼─────┼─────────────┼────────────┤
│2 combbit 4│13056│3.45637285e_5│0.451264039 │
├───────────┼─────┼─────────────┼────────────┤
│2 CombBit 4│5888 │2.24359098e_5│0.132102637 │
└───────────┴─────┴─────────────┴────────────┘
stp 2
60 combbit 64
60 CombBit 64
)
┌─────────────┬─────────┬───────────┬────────────┐
│Sentence │Space │Time │Space * Time│
├─────────────┼─────────┼───────────┼────────────┤
│60 combbit 64│178304896│0.774408636│138080851 │
├─────────────┼─────────┼───────────┼────────────┤
│60 CombBit 64│178297088│0.751941586│134068995 │
└─────────────┴─────────┴───────────┴────────────┘
The verb CombBit was produced using the J Wicked Toolkit as follows (beware
of line-wrapping),
or=.23 b.
lshift=.33 b.
lrot=. 32 b.
shift=. 2 ((_2 lrot 2 #: [) or _1 lshift ])/\ ]
'X Y K Z N L P'=. 7 Fetch
CombBit=. [tv f.
'K Z N L P'local o ;
N ((<:##:_1 (32 b.) 1)"_) h NB. n=.<:##:_1 (32 b.) 1
L (>. o (Y % N)) h NB. l=.>.y%n
P (Y - >: o i. o >: o (Y - X)) h NB. y->:i.>:d=.y-x
K (<"_1 o (<. o (P % N) |."0 1 (0 $~ 1 -~ L) ,"1 0 (2 ^&.x: N #: P))) h
NB. <"_1(<.p%n)|."0 1((l-1)$0),"1 0 [2 ^&.x: n#:p
Z ((Y - X) (([ $ <@:(0 $~ 0 ,~ ])) , <@:(0 $~ 1 ,~ ])) L) h
NB. z=.((y-x)$<(l,0)$0),<(l,1)$0
(Z (K or&.> ,.&.>/\.@:(shift@:(0 , ])&.>)@:Z) h)^:X
NB. for. i.x do. z=. k (or)&.> ,.&.>/\. ([:shift 0,])&.> z end.
>@:(,.&.>/)@:(((-@:L){. -@:(N | Y) , (<.@:(Y % N))# N) (<@:([ {."1
#:@:])"0 1) >@:(,.&.>/)@:Z)
NB. >,.&.>/((-l){.-(n|y),(<.y%n)#n) ([:<[{."1[:#:])"0 1 >,.&.>/z
)
66 Wrap 'CombBit'
@:(,.&.>/)@:((-@:(5&({::)) {. -@:(4&({::) | 1&({::)) , <.@:(1&({:
:) % 4&({::)) # 4&({::)) <@:([ {."1 #:@:])"0 1 >@:(,.&.>/)@:(3&({:
:)))@:((<@:(2&({::) 23 b.&.> ,.&.>/\.@:((2 (((_2) 32 b. 2 #: [) 23
b. (_1) 33 b. ])/\ ])@:(0 , ])&.>)@:(3&({::))) 3} ])^:(0&({::)))@
:(<@:((1&({::) - 0&({::)) (([ $ <@:(0 $~ 0 ,~ ])) , <@:(0 $~ 1 ,~
])) 5&({::)) 3} ])@:(<@:(<"_1@:(<.@:(6&({::) % 4&({::)) |."0 1 (0
$~ 1 -~ 5&({::)) (,"1 0) 2 ^&.x: 4&({::) #: 6&({::))) 2} ])@:(<@:(
1&({::) - >:@:i.@:>:@:(1&({::) - 0&({::))) 6} ])@:(<@:(>.@:(1&({::
) % 4&({::))) 5} ])@:(<@:(63"_) 4} ])@:(,&(<;._1 ' K Z N L P')@:;)
It can certainly be simplified, but I will pass. :)
On Mon, Nov 13, 2017 at 10:31 AM, Erling Hellenäs <[email protected]>
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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
