> This is efficient. I think the problems may come on scaling up. The > example given requires about 200,000 iterations through the main loop with > a maximum stack size of 120. In my experience these are the main > parameters affecting things. Please note that my ignorance is probably > the major factor in writing efficient programs. For Project Euler #216 I > will shortly have a separate query about preventing integers from being > promoted.
http://www.jsoftware.com/jwiki/Essays/Knight's_Tour The Knight's Tour is probably an example of the situation you described. ktour uses depth first search and looks very much like the queens_dfs verb discussed yesterday. ktour 7 goes through 137459 iterations with a maximum stack size of 87, taking a little over 3 seconds. ktour 8 takes about 470 seconds. The problem with ktour is not "scaling up". The problem is that the search trimming is too simple-minded (trim if no next move). ----- Original Message ----- From: John Randall <[EMAIL PROTECTED]> Date: Thursday, November 20, 2008 15:54 Subject: Re: [Jprogramming] Project Euler Problem 216 To: Programming forum <[email protected]> > Roger Hui wrote: > >> I agree with the general point. Project Euler has a number > of big > >> depth-first searches which I do not know how to program > >> efficiently in J. > > > > Is the following "efficient" according to your criteria? > > <dfs_queens deleted> > > This is efficient. I think the problems may come on > scaling up. The > example given requires about 200,000 iterations through the main > loop with > a maximum stack size of 120. In my experience these are > the main > parameters affecting things. Please note that my ignorance > is probably > the major factor in writing efficient programs. For > Project Euler #216 I > will shortly have a separate query about preventing integers > from being > promoted. > > I can write the stack-oriented program illustrated, but I find > some of it > surprising. I always make my stacks go the other way, with > pushes and > pops at the end of the array. My rationale is that push > then can be > implemented by append in place, and for pop there is no curtail > in place, > but if I do them at the beginning, the stack gets copied every > time. Is > this true? ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
