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
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 <joe…> wrote:> What is the most efficient way> to implement sparse arrays in q?>> Thanks, Joel>> –> wagerlabs.com</joe…>
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 <ableofhighhe…> 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 <joe…> wrote:>> > What is the most efficient way> > to implementsparsearrays in q?>> > Thanks, Joel>> > –> > wagerlabs.com</joe…></ableofhighhe…>
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 <joe…> wrote:> What is the most efficient way> to implementsparsearrays in q?>> Thanks, Joel>> –> wagerlabs.com</joe…>
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” <felix.lu…> 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 <duocentill…>> 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 <joe…> wrote:> > > What is the most efficient way> > > to implementsparsearrays in q?>> > > ? ? ? ? Thanks, Joel>> > > –> > > wagerlabs.com</joe…></duocentill…></felix.lu…>
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” <k.os…> 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” <felix.lu…> 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 <duocentill…>> > 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 <joe…> wrote:> > > > What is the most efficient way> > > > to implementsparsearrays in q?>> > > > Thanks, Joel>> > > > –> > > > wagerlabs.com</joe…></duocentill…></felix.lu…></k.os…>
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;Bdiv[;B]\N} / Base, Length, Numbers
q)n:10000
q)d:(flip v100;3?1000000)!n?1000f
q)count distinct key d
10000
I also experimented with tables:
q)t:(flipxy`z!v100;3?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 <thesweeh…> 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” <k.os…> 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” <felix.lu…> 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 <duocentill…>>> > > 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 <joe…> wrote:>> > > > > What is the most efficient way>> > > > > to implementsparsearrays in q?>>>> > > > > Thanks, Joel>>>> > > > > –>> > > > > wagerlabs.com> >></joe…></duocentill…></felix.lu…></k.os…></thesweeh…>