Following up on this - the J approach is quite slow still. I was hoping avx
would help. It does by 15%, but more would be needed. By the way, thank you
for all involved in the avx. Very exciting
Ideally I'd like to run an algorithm like this on millions of transactions.
Seems to putter out around in the tens of thousands. I used a different
algorithm in kdb/sql to first filter to the credits and then look for
matching transactions. In production data, there are 44,000 credit
candidates, so I'd need to rework the J algorithm to have a fair comparison.
In any event, some timing for those interested
Original version is 3.54 seconds to crunch 20,000 transactions (avx Beta-3:
commercial/2017-04-10T18:03:23) and 3.7 seconds (non-avx j805) -- only 5%
improvement
applycredits2 gets rid of the boxing:
NB. j805
(6!:2) 'applycredits2 gen 2e4'
1.90125
NB. j806 - 15% improvement
(6!:2) 'applycredits2 gen 2e5'
1.61232
NB. J805
(6!:2) 'applycredits2 gen 3e4'
4.8036
NB. j806 - 17.3% improvement
( 6 !: 2 ) 'applycredits2 gen 3e4'
3.96862
gen=: 3 : 0
N=: y
keys=:?. (N#100)
qtychoices =: i: 10
qtys=: qtychoices {~ ?. (N# (# qtychoices))
seqs=: i. N
)
'CANCEL CREDIT OK' =: i.3
applycredits2 =: 3 : 0
NB. goals=.(<'goal')
creditids=.0
goals=:''
for_i. (i. # seqs) do.
key=.i{keys
seq=.i{seqs
qty=.i{qtys
nextcredit =.| {. qtys #~ ((key=keys)*(seqs>seq)*(qtys<0))
if. nextcredit = qty do.
NB. goals=.goals,<'cancelled'
goals=.goals,CANCEL
creditids =. creditids, seqs #~ ((key=keys)*(seqs>seq)*(qtys<0))
elseif. creditids e.~ seq do.
NB. goals=.goals,<'credit'
goals=.goals,CREDIT
elseif. do.
NB. goals=.goals,<'ok'
goals=.goals,OK
end.
end.
goals
)
Here is applycredits3 which tests removal of conditionals
'CANCEL CREDIT OK' =: i.3
applycredits3 =: 3 : 0
creditids=.0
goals=:''
for_i. (i. # seqs) do.
key=.i{keys
seq=.i{seqs
qty=.i{qtys
nextcredit =.| {. qtys #~ ((key=keys)*(seqs>seq)*(qtys<0))
iscancel =. nextcredit = qty
iscredit=. creditids e.~ seq
goals =. goals,({. I. (iscancel,iscredit,1))
if. iscancel do. creditids =. creditids, seqs #~
((key=keys)*(seqs>seq)*(qtys<0)) end.
end.
goals
)
NB. j805 - no speedup from version 2
(6!:2) 'applycredits3 gen 3e4'
4.8621
NB. j805 - no speedup from version 2
(6!:2) 'applycredits3 gen 3e4'
4.8621
NB. j806 - no real speedup from version 2
(6!:2) 'applycredits3 gen 3e4'
4.03061
On Wed, Apr 12, 2017 at 12:35 PM, Joe Bogner <[email protected]> wrote:
> I have a problem I'm trying to solve in different languages. I have a
> solution in SQL and also in kdb which largely resembles the SQL solution.
> I'm curious what a J solution would look like. More specifically, I'm
> interested in picking the brains of others here to see if this type of
> problem can be solved without looping (some form of scan?).
>
> EDIT: Initially I wrote this up thinking the J solution would difficult,
> but it was actually fairly straightforward -- about 15 minutes, but still
> would like to see if there are alternatives. If nothing else, maybe an
> interesting problem to share.
>
> Example data:
>
> A store has a transaction log with a sequence for each transaction. The
> transaction log records a key for a unique customer/item combination. The
> transaction log records how many units were purchased or returned.
>
> Goal:
> Attempt to match up related transactions and cancel out instances when the
> customer/item combination is returned at the same quantity as a previous
> transaction
>
> Examples:
>
> Joe buys 1 blue pen, which is defective, then returns the 1 defective blue
> pen, then buys another blue pen. EXPECTED: cancel out first two
> transactions and leave the the last one for 1 pen
>
> Bob buys 2 red pens in two separate transactions. He then buys 3 more. He
> returns the first two purchases as two separate return transactions.
> EXPECTED: cancel out all transactions except the one for qty 3
>
> Jane buys 5 purple pens and subsequently returns two of them. She buys two
> more. EXPECTED: No transactions match exactly, so nothing is cancelled out
>
>
> Data:
>
> data=: 0 : 0
> seq key qty
> 1 1 1
> 2 1 _1
> 3 1 1
> 4 2 1
> 5 2 1
> 6 2 3
> 7 2 _1
> 8 2 _1
> 9 3 5
> 10 3 _2
> 11 3 2
> )
> tbl =: ,. ' ' cut every cutLF data
> 'seqs keys qtys' =: |: ". every }. tbl
>
>
> Goal:
>
> goals =: 0 : 0
>
> goal
>
> cancelled
>
> credit
>
> ok
>
> cancelled
>
> cancelled
>
> ok
>
> credit
>
> credit
>
> ok
>
> ok
>
> ok
>
> )
>
>
>
>
> tbl,.(cutLF goals)
>
> +---+---+---+---------+
>
> |seq|key|qty|goal |
>
> +---+---+---+---------+
>
> |1 |1 |1 |cancelled|
>
> +---+---+---+---------+
>
> |2 |1 |_1 |credit |
>
> +---+---+---+---------+
>
> |3 |1 |1 |ok |
>
> +---+---+---+---------+
>
> |4 |2 |1 |cancelled|
>
> +---+---+---+---------+
>
> |5 |2 |1 |cancelled|
>
> +---+---+---+---------+
>
> |6 |2 |3 |ok |
>
> +---+---+---+---------+
>
> |7 |2 |_1 |credit |
>
> +---+---+---+---------+
>
> |8 |2 |_1 |credit |
>
> +---+---+---+---------+
>
> |9 |3 |5 |ok |
>
> +---+---+---+---------+
>
> |10 |3 |_2 |ok |
>
> +---+---+---+---------+
>
> |11 |3 |2 |ok |
>
> +---+---+---+---------+
>
>
>
> One approach:
>
> applycredits =: 3 : 0
>
> goals=.(<'goal')
>
> creditids=.0
>
> for_i. (i. # seqs) do.
>
> key=.i{keys
>
> seq=.i{seqs
>
> qty=.i{qtys
>
> nextcredit =.| {. qtys #~ ((key=keys)*(seqs>seq)*(qtys<0))
>
> if. nextcredit = qty do.
>
> goals=.goals,<'cancelled'
>
> creditids =. creditids, seqs #~ ((key=keys)*(seqs>seq)*(qtys<0))
>
> elseif. creditids e.~ seq do.
>
> goals=.goals,<'credit'
>
> elseif. do.
>
> goals=.goals,<'ok'
>
> end.
>
> end.
>
> goals
>
> )
>
> tbl ,. ( applycredits 0 )
>
>
> +---+---+---+---------+
>
> |seq|key|qty|goal |
>
> +---+---+---+---------+
>
> |1 |1 |1 |cancelled|
>
> +---+---+---+---------+
>
> |2 |1 |_1 |credit |
>
> +---+---+---+---------+
>
> |3 |1 |1 |ok |
>
> +---+---+---+---------+
>
> |4 |2 |1 |cancelled|
>
> +---+---+---+---------+
>
> |5 |2 |1 |cancelled|
>
> +---+---+---+---------+
>
> |6 |2 |3 |ok |
>
> +---+---+---+---------+
>
> |7 |2 |_1 |credit |
>
> +---+---+---+---------+
>
> |8 |2 |_1 |credit |
>
> +---+---+---+---------+
>
> |9 |3 |5 |ok |
>
> +---+---+---+---------+
>
> |10 |3 |_2 |ok |
>
> +---+---+---+---------+
>
> |11 |3 |2 |ok |
>
> +---+---+---+---------+
>
>
>
> (cutLF goals) -: ( applycredits 0 )
>
> 1
>
>
> thanks for any input
>
>
>
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
