Traverse 2D List of Integers

Community Support
1

Hello,

Here’s a problem that’s been bugging me for the last couple of days. Assume you have two equally sized lists of bids and asks which you would like to traverse sequentially for flips.

q)bids:24079 24074 24088 24092 24081 24092 24092 24092 24082 24092;q)asks:24112 24154 24115 24119 24049 24119 24119 24119 24149 24119;

We first start by setting references:

q)bidRef:first bidsq)askRef:first asks

Then we want to know if and when the bid/ask flips. So we create a dummy function which keeps track of the counter of the sequence and stores it:

q)counter:0;q)flippedIndices:();q)f:{[bid;ask] if[(bid>askRef) or (ask<bidRef); askRef::ask; bidRef::bid; flippedIndices,:counter;]; counter+:1;};q)f'[bids;asks];q)flip `bids`asks! (bids;asks)@\:0, flippedIndicesbids asks -----------24079 2411224081 2404924092 24119

?

Now, what would be the optimal way of doing this in a vectorial manner or using adverbs? The performance is acceptable (about 500ms for 500000 items), however I believe there is a proper ‘q-like’ solution.

Thanks,

Zak

This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you are not the named addressee you must not disseminate, distribute or copy this e-mail. Please notify us on regulatory@b2c2.net immediately if you have received this e-mail by mistake and delete this e-mail from your system. If you are not the intended recipient you are notified that disclosing, copying, distributing or taking any action in reliance on the contents of this information is strictly prohibited.

2

hi Zak,


deltas and signum come to mind:

flipbidsasks!(bids;asks)@:where not 0=deltas signum bids-asks

took 39ms for 500.000 items.

best,

Will

3

Hi Zak,

Would this work? 

q)( bids;asks) where differ signum bids - asks

bids  asks 

24079 24112

24081 24049

24092 24119

Or have I over-simplified this?

Regards,

Paul

4

Hi Paul,

Thanks for helping out. Looks like that won’t work. Actually every time one of the condition is met in the ‘or’ section, we reset the reference prices to the current bid/ask pair and then move on to the next bid/ask pair. So there is some state setting which signum/differ don’t account for…

Thanks,

Zak

5

Thanks Will, please check additional information above ^

6

I’m not sure if this will be any faster, but this is a more usual way of writing your method and it avoids the use of global variables. Global variables are usually avoided unless they are contained within a well defined namespace to avoid any conflicts with variables in different functions sharing the same names.

It performs a recursion passing in an list of the bidref,askref and a boolean for flipped and performs the same logic as yours above. Using scan will output the value of this list for each iteration from which we can grab the last column containing the booleans for flipped and then use ‘where’ to get the indices where this occurs. Finally we can append a 0 and index into each bids and asks list to create the table

f:{0,where last flip {$[(y>x 1)|z<x 0;(y;z;1b);x[0 1],0b]}\[(first x;first y;0b);x;y]}flip bidsasks! (bids;asks)@\:f[bids;asks]

Mark

7

Hi Mark,

I like your solution. Returning the previous state makes sense. Time-wise it takes the same as the original solution. However space wise, I am seeing up to 50x more memory-usage with your solution, which I guess makes sense.

Zak

8

I tried combining the approaches of Paul and Mark which saved a bit of time/space:

n:500000

bids:n?30000

asks:n?30000

bidRef:first bids

askRef:first asks


counter:0;

flippedIndices:();

f:{[bid;ask]

if[(bid>askRef) or (ask<bidRef);

askRef::ask;

bidRef::bid;

flippedIndices,:counter;

];

counter+:1;

};

\ts f’[bids;asks];ref:flip bidsasks! (bids;asks)@:0, flippedIndices;


f:{0,where last flip {$[(y>x 1)|z<x 0;(y;z;1b);x[0 1],0b]}[(first x;first y;0b);x;y]}

\ts r3:flip bidsasks! (bids;asks)@:f[bids;asks]


/ –> combined:

\ts r4:flipbidsasks!flip k 0,where differ{$[(x[0]>y 1)|y[0]>x 1;y;x]}[k:flip(bids;asks)]

ref~r3

ref~r4

Output:

964 16778416

952 47097248

792 30817520

1b

1b

With what input did you get 50x memory?