Updating preallocated arrays works for fixed sized data, but J's boxed array implementation doesn't really fit that model.
Thanks, -- Raul On Mon, Mar 10, 2014 at 12:19 PM, Devon McCormick <[email protected]>wrote: > Raul - > > I don't know if it will help with your particular problem, but, in general, > a way to avoid the O(n^2) behavior of repeated concatenation is to > initialize a place-holder array of the right shape, then fill it in. > > For example, using Joe's "bld2" as an example of what to accomplish: > > bld3=: 3 : 0 > (<'.') bld3 y > : > (x) (i.y)}y$a: > ) > bld3 10 > +-+-+-+-+-+-+-+-+-+-+ > |.|.|.|.|.|.|.|.|.|.| > +-+-+-+-+-+-+-+-+-+-+ > 6!:2 'bld3 1e2' > 4.80314e_5 > 6!:2 'bld3 1e3' > 0.000126031 > 6!:2 'bld3 1e4' > 0.00218933 > 6!:2 'bld3 1e5' > 0.00901553 > 6!:2 'bld3 1e6' > 0.0967073 > > Of course, it's hard to do this if you don't know the final shape in > advance. It's possible to reach a compromise, complicating the code, by > pre-allocating blocks of boxes but I don't know how feasible this is for > you. > > > On Mon, Mar 10, 2014 at 11:22 AM, Raul Miller <[email protected]> > wrote: > > > Yes, exactly. > > > > I'm working on a project where I am parsing xml files and building up > boxed > > representations of the results. The final result will be on the order of > 30 > > million boxes long (and have approaching 100 distinct "columns" of > boxes). > > > > It's been more painful than I expected, in a variety of ways. I've found > > new and innovative ways of crashing J (and in my copious free time I'll > > need to spend some time isolating those issues). For now, it looks like > > I'll be needing to do my xml parsing in 32 bit j602 and then assemble the > > results in a 64 bit version of J. > > > > But since each xml file only contributes one box to each of the "columns" > > it contributes to, there isn't really any better way of building the > > intermediate results other than using , > > > > Hypothetically speaking, I might need to switch to a flat intermediate > > representation. I've done some drafts of code using flat representations > > and that's certainly doable (but a bit more complicated and at the time I > > was experimenting with them I did not see any benefit to the additional > > code complexity - timing was about the same). > > > > So instead, for now, I'm going to rely on "checkpointing" at various > orders > > of magnitude. With this much data I already have to deal with the fact > that > > the machines can fail for any of a variety of reasons, and computational > > limits and bugs in the interface to sax just get included on that list. > > > > You can't let reasons become excuses or you don't get stuff done. > > > > Thanks, > > > > -- > > Raul > > > > > > > > On Mon, Mar 10, 2014 at 7:33 AM, Joe Bogner <[email protected]> wrote: > > > > > Is this an example of what you're referring to? > > > > > > bld2=: 3 : 0 > > > (<'.') 4 : 'y , x' ^:y '' > > > ) > > > > > > ts 'l=:bld2 1e2' > > > 0.00177792 6400 > > > ts 'l=:bld2 1e3' > > > 0.0850437 20544 > > > ts 'l=:bld2 1e4' > > > 8.28457 217152 > > > > > > $ l > > > 10000 > > > > > > Looping explicitly is similar > > > > > > bld4 =: 3 : 0 > > > l=:'' > > > for. i. y do. l=:l,(<'.') end. > > > ) > > > > > > ts 'l=:bld4 1e4' > > > 5.41629 199104 > > > > > > > > > If so, I agree there needs to be a more efficient way > > > > > > On Mon, Mar 10, 2014 at 7:05 AM, Linda Alvord <[email protected] > > > > > wrote: > > > > > > > > Raul, Since I have a math background, I'm rather fond of x and y > > > and am > > > > not in any hurry to eliminate them. > > > > However, I like boxes and will ponder your ideas - at least > > > conceptually. > > > > > > > > Thanks for all your coaching! > > > > > > > > Linda > > > > > > > > > > > > -----Original Message----- > > > > From: [email protected] > > > > [mailto:[email protected]] On Behalf Of bill > > lam > > > > Sent: Monday, March 10, 2014 3:30 AM > > > > To: Programming forum > > > > Subject: Re: [Jprogramming] strategies for building long lists of > boxes > > > > > > > > we can build internal representation (3!:1 or 3) of the box array and > > > > convert it using 3!:2, not sure if this can improve time or space > > > > efficiency. > > > > > > > > On Mon, Mar 10, 2014 at 2:37 PM, Raul Miller <[email protected]> > > > wrote: > > > >> Since using , to build boxed arrays does not currently have any code > > to > > > >> support it, time is O(n^2). In other words: inefficient for long > lists > > > of > > > >> boxes. > > > >> > > > >> So let's say we wanted to build lists of 30000 boxes, how could we > do > > > that > > > >> efficiently? > > > >> > > > >> It seems to me that the right thing to do would be: pick a threshold > > > > (maybe > > > >> 1000 boxes) and when your list gets that long, append that > > intermediate > > > >> result to a result list and start a fresh instance of the working > > list. > > > >> Repeat until done (and don't forget to append the last intermediate > > list > > > > to > > > >> the result). > > > >> > > > >> Conceptually speaking, this is still O(n^2). But it should also be > > > orders > > > >> of magnitude faster (at the cost of some complexity) than use of > > > unadorned > > > >> comma. (And conceptually speaking one might be able to define some > > kind > > > of > > > >> "infinite" representation of this algorithm which has better than > > O(n^2) > > > >> performance. Maybe O(n log n)? > > > >> > > > >> Thanks, > > > >> > > > >> -- > > > >> Raul > > > >> > ---------------------------------------------------------------------- > > > >> For information about J forums see > > http://www.jsoftware.com/forums.htm > > > > > ---------------------------------------------------------------------- > > > > For information about J forums see > http://www.jsoftware.com/forums.htm > > > > > > > > > ---------------------------------------------------------------------- > > > > For information about J forums see > http://www.jsoftware.com/forums.htm > > > ---------------------------------------------------------------------- > > > For information about J forums see http://www.jsoftware.com/forums.htm > > > > > ---------------------------------------------------------------------- > > For information about J forums see http://www.jsoftware.com/forums.htm > > > > > > -- > Devon McCormick, CFA > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
