Cartesian Products

Community Support
,
1

https://learninghub.kx.com/forums/topic/cartesian-products

Hello, I’m a professional furniture maker and hobbyist programmer. I’m looking to calculate some basic paths to victory analysis on a series of x games with n players, each placing 1-n in any given game, with the ultimate number of outcomes being n!^x. I’m evaluating the best tools to enumerate the outcomes and perform the desired calculations to determine the remaining winning outcomes for a given player’s series remainder for a given x > 1. I understand how large this number can be so I’m focused on only performing these calculations for {3<=n<=8} and x=2, tho larger values of x would be fantastic. I’ve created the dataset in sqlserver for n=8 and x=2 but am still fiddling with indexing as it’s vey slow at the moment. If there’s anyone with any pointers on how to perform cartesian operations efficiently in q I’d greatly appreciate it.

 

2

Hi jn001,

Welcome to the KX Community

How are you currently generating your permutations?

q)x:2 
q)n:8 
q)fac:{prd 1+til x} 
q)p:`long$fac[n] xexp x; / max permutations 
q)s:1+til p; / list of n permutations

I.e. determining the actual number of permutations is easy in q

q)fac[8] xexp 8 
6.9849642471415143e+036

However for each factor added, the list you will be creating will use a lot more ram so you could hit 'wsfull depending on your machine size.

In that case you might want to split up the calculations and iteratively calculate each before joining the results together (a kind of ‘map-reduce’ if you will.)

Notes:

  • 'fac' taken from the phrases.
  • cross may also be of interest to you, for example creating the list of players and games they can participate in:
q)x:2 
q)n:4 
q)flip `players`games!flip (1+til n) cross (1+til x) 
players games 
------------- 
1       1 
1       2 
2       1 
2       2 
3       1 
3       2 
4       1 
4       2
I hope this helps provoke some ideas and to kick of this thread

David

3

Hello David, thank you so much for your response. I generated the dataset in sql for sqlserver. It took quite a while for the 8! x 8! combinations. I guess what I wanted to really understand is the suitability of q over sql for generating a large dataset like this and subsequently querying it. What resources would you recommend for study?

4

Q excels in generating and querying large datasets due to it’s capability of performing efficient vector based operations; you’ll see more benefit with Q the larger your dataset becomes.

“Column Oriented SQL tables are organized as rows distributed across storage and operations apply to fields within a row. Q tables are column lists in contiguous storage and operations apply on entire columns.” - (Jeffry Borror, 0. Overview - Q for Mortals (kx.com))

In terms of resources, there are a lot of options. Here are a few ideas to get started:

Check out this blog for some more insight What Makes Time-Series Database kdb+ So Fast? | KX along with other material on code.kx.com, in particular whitepapers and the Community.

The sales brochure and blog also contain a lot of useful information around performance.

Hope you find this insightful