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
