cancel
Showing results for 
Search instead for 
Did you mean: 

sparse arrays

joelr1
New Contributor
Mime-Version: 1.0 (Apple Message framework v919.2)Subject: sparse arraysDate: Sun, 6 Apr 2008 00:04:15 +0100X-Mailer: Apple Mail (2.919.2)What is the most efficient wayto implement sparse arrays in q? Thanks, Joel--wagerlabs.com
8 REPLIES 8

Doni_Ocena
New Contributor
I'm interested in this as well, it would be great to find a definitiveapproach. I currently use dictionaries to implement sparse arrays.q)\w110896 67634176 0 0jq)foo:(0#0N)!0#0Nq)\w115264 67634176 0 0jq)foo[0]:100q)\w115296 67634176 0 0jq)foo[999999]:200q)\w115296 67634176 0 0jOn Apr 5, 7:04 pm, Joel Reymont wrote:> What is the most efficient way> to implement sparse arrays in q?>> Thanks, Joel>> --> wagerlabs.com

possible to make n-dimensional sparse arrays in q? interested in q'sperformance storing, accessing, manipulating, etc. when n largeOn Apr 5, 7:47 pm, Doni Ocena wrote:> I'm interested in this as well, it would be great to find a definitive> approach. I currently use dictionaries to implementsparsearrays.>> q)\w> 110896 67634176 0 0j> q)foo:(0#0N)!0#0N> q)\w> 115264 67634176 0 0j> q)foo[0]:100> q)\w> 115296 67634176 0 0j> q)foo[999999]:200> q)\w> 115296 67634176 0 0j>> On Apr 5, 7:04 pm, Joel Reymont wrote:>> > What is the most efficient way> > to implementsparsearrays in q?>> > Thanks, Joel>> > --> > wagerlabs.com

DuoCentillion
New Contributor
It would be great to see some implementation of the Sparse Array in Qor K. Is Q and K just not well suited for this type of application?I would think there would be some low level implementation that wouldbe possible?ThanksJoeOn Apr 5, 7:04 pm, Joel Reymont wrote:> What is the most efficient way> to implementsparsearrays in q?>> Thanks, Joel>> --> wagerlabs.com

for sparse array just use null when data is missing or a index map associated with an array (a dictionary of indices over values.

felix

Care to give an example a 100x100x100 array with 10,000 random datapoints defined within it?On May 28, 1:05�pm, "Felix LUNGU" wrote:> for sparse array just use null when data is missing or a index map> associated with an array (a dictionary of indices over values.> felix>> On Fri, May 23, 2008 at 11:46 PM, DuoCentillion > wrote:>>>> > It would be great to see some �implementation of the Sparse Array in Q> > or K. �Is Q and K just not well suited for this type of application?> > I would think there would be some low level implementation that would> > be possible?>> > Thanks> > Joe>> > On Apr 5, 7:04 pm, Joel Reymont wrote:> > > What is the most efficient way> > > to implementsparsearrays in q?>> > > � � � � Thanks, Joel>> > > --> > > wagerlabs.com

I believe Felix meant something like this:q)n:10000q)d:({3?100}each n#0)!n?1000fq)count d / may be < 10000 if collision occurs10000q)d85 38 0 | 898.396445 25 65| 187.243775 43 53| 604.562781 38 16| 833.710836 92 91| 755.5393..On Jul 23, 12:57 am, "k.os.tao" wrote:> Care to give an example a 100x100x100 array with 10,000 random data> points defined within it?>> On May 28, 1:05 pm, "Felix LUNGU" wrote:>> > for sparse array just use null when data is missing or a index map> > associated with an array (a dictionary of indices over values.> > felix>> > On Fri, May 23, 2008 at 11:46 PM, DuoCentillion > > wrote:>> > > It would be great to see some implementation of the Sparse Array in Q> > > or K. Is Q and K just not well suited for this type of application?> > > I would think there would be some low level implementation that would> > > be possible?>> > > Thanks> > > Joe>> > > On Apr 5, 7:04 pm, Joel Reymont wrote:> > > > What is the most efficient way> > > > to implementsparsearrays in q?>> > > > Thanks, Joel>> > > > --> > > > wagerlabs.com



I made a mistake: "count d" always return 10000. The correct way to
detect collision is "count distinct key d".

To have exactly 10000 distinct points, this works better:
q)v:{[B;L;N]mod[;B](L-1)div[;B]\N} / Base, Length, Numbers
q)n:10000
q)d:(flip v[100;3](0-n)?1000000)!n?1000f
q)count distinct key d
10000

I also experimented with tables:
q)t:(flip`x`y`z!v[100;3](0-n)?1000000)!([]val:n?1000f)
q)5#t
x y z | val
--------| --------
86 20 79| 226.4462
51 63 95| 735.3732
46 70 42| 903.7595
80 13 39| 58.31545
17 53 88| 944.2269

It seems that for insertion and access, tables are faster than
dictionaries:
q)\t i:0;do[2000;(i+:1;d[1,1,i]:1.5)]
4149
q)\t i:0;do[2000;(i+:1;t[1,1,i]:1.5)]
409
q)\t i:0;do[2000;(i+:1;d[1,1,i])]
2062
q)\t i:0;do[2000;(i+:1;t[1,1,i])]
258

But I can't figure out the syntax to delete specific keys from
dictionaries and tables where the keys are not atomic:
q)d _ (1 1 1)
'type
q)t _ (1 1 1)
'type
q)\t delete from `t where x=1,y=1,z<10000 / this works though...
0

Any suggestions on deletion? Are there other reasons to prefer
dictionaries over tables?

Swee Heng

> It seems that for insertion and access, tables are faster than> dictionaries:> q)\t i:0;do[2000;(i+:1;d[1,1,i]:1.5)]> 4149> q)\t i:0;do[2000;(i+:1;t[1,1,i]:1.5)]> 409> q)\t i:0;do[2000;(i+:1;d[1,1,i])]> 2062> q)\t i:0;do[2000;(i+:1;t[1,1,i])]> 258your table columns are vectors - thus fastwhile you dictionary has a nested key - that is slow> But I can't figure out the syntax to delete specific keys from> dictionaries and tables where the keys are not atomic:> q)d _ (1 1 1)> 'typeq)enlist[1 1 1]_dyou need the enlist as without it would be cutd _ only works for atoms on the right hand side, the general form isx_d - similar to x#d> q)t _ (1 1 1)> 'typeq)([]x:enlist 1;y:1;z:1)_tyou have to have the proper type of key you want to drop> Any suggestions on deletion? Are there other reasons to prefer> dictionaries over tables?Well the table you have here is a keyed table aka a dictionary...Regards, Attila> On Jul 23, 4:49 am, Swee Heng wrote:>> I believe Felix meant something like this:>> q)n:10000>> q)d:({3?100}each n#0)!n?1000f>> q)count d / may be < 10000 if collision occurs>> 10000>> q)d>> 85 38 0 | 898.3964>> 45 25 65| 187.2437>> 75 43 53| 604.5627>> 81 38 16| 833.7108>> 36 92 91| 755.5393>> ..>>>> On Jul 23, 12:57 am, "k.os.tao" wrote:>>>> > Care to give an example a 100x100x100 array with 10,000 random data>> > points defined within it?>>>> > On May 28, 1:05 pm, "Felix LUNGU" wrote:>>>> > > for sparse array just use null when data is missing or a index map>> > > associated with an array (a dictionary of indices over values.>> > > felix>>>> > > On Fri, May 23, 2008 at 11:46 PM, DuoCentillion >> > > wrote:>>>> > > > It would be great to see some implementation of the Sparse Array in Q>> > > > or K. Is Q and K just not well suited for this type of application?>> > > > I would think there would be some low level implementation that would>> > > > be possible?>>>> > > > Thanks>> > > > Joe>>>> > > > On Apr 5, 7:04 pm, Joel Reymont wrote:>> > > > > What is the most efficient way>> > > > > to implementsparsearrays in q?>>>> > > > > Thanks, Joel>>>> > > > > -->> > > > > wagerlabs.com> >>