From: Dave Harris on 10 May 2010 09:04 daniel_t(a)earthlink.net (Daniel T.) wrote (abridged): > > Yes. It led to simple code, but that was partly because all the > > complexity was hidden behind an iterator. > > [...] > I didn't post anymore than I did because there isn't enough context > to tell what the best solution is. Even though .size() is checked > at each level, there may still be an invariant such that all the > sizes are the same. I would be interested in code that solved the same problem that the original code solved. Or are you agreeing that the original code was the best, for that problem? Can you only do better if you change the problem by adding extra invariants? -- Dave Harris, Nottingham, UK.
From: Nick Keighley on 10 May 2010 09:25 On 9 May, 04:53, Robert Redelmeier <red...(a)ev1.net.invalid> wrote: > In alt.lang.asm [FUp set] Sjouke Burry <burrynulnulf...(a)ppllaanneett.nnll> wrote in part: [do modern Fortrans allow recursion?] > > If recursion does not exist, I will have to ditch quite > > a couple of fortran programs. There is only 1 hitch, you > > have to write a 3 line dummy routine, to do the calling, > > so a calls b , b calls a. fortran MS 5.1 and later. > > Also Fortran77 for Riscos (arc 320 computer) > > For what problems do you find recursion to be the fastest > [CPU runtime] solution method? maybe none? Maybe there are other reasons for using recursion.
From: Nathan on 10 May 2010 10:28 On May 10, 9:04 am, brang...(a)cix.co.uk (Dave Harris) wrote: > nathancba...(a)gmail.com (Nathan Baker) wrote (abridged): > > > > Yes. It led to simple code, but that was partly because all the > > > complexity was hidden behind an iterator. Nathan Baker's version > > > exposes some of that complexity, and I think illustrates how hard > > > it is to get it right. > > > Perhaps the words "simple" and "complexity" have different meanings > > to different people because of their different training and the goals > > they've been conditioned to target?? > > > Juha's code uses 3 loop constructs, 4 conditionals, and 2 exit > > points. > > > Mine uses 1 loop construct, 2 conditionals, and 1 exit point. > > But your code was broken in the ways pointed out by other posters. In > particular, it accesses data[0][0][0] even if data[0].size() is zero, > which will give a bounds error or a crash. It also failed to return a the > address where the item was found, and was incapable of searching for > value 0. It also did huge amounts of unnecessary work, in that the inner > loop tested all of the conditionals. (And by my count it uses a lot more > than 2 conditionals even as posted.) You need to fix all the bugs in your > code before we can even consider its complexity. > > When I try to write code myself that uses your approach, but correctly > handles all the cases the original code handles, I get a horrible mess. > Specifically, you need to be aware that data[0][0].size() may be > different to data[1][0].size() or data[0][1].size(), and that any of them > may be zero meaning that (eg) data[0][0][0] does not exist and must not > be accessed. Similarly for data[0].size() and data.size(), and data[0][0] > and data[0]. > > This seems to mean you need a loop to find the first accessible value > before you even look at data[xInd][yInd][zInd]. > Then let's just start with Juha's original code and see where some simple improvements can be made, shall we? Given, the original... ,--- Value_t* MyClass::findValue(const Value_t& value) { for(size_t xInd = 0; xInd < data.size(); ++xInd) for(size_t yInd = 0; yInd < data[xInd].size(); ++yInd) for(size_t zInd = 0; zInd < data[xInd][yInd].size(); + +zInd) { if(data[xInd][yInd][zInd] == value) return &data[xInd][yInd][zInd]; } return 0; } `--- First, we can remove the nested loops like so... ,--- Value_t* MyClass::findValue(const Value_t& value) { size_t xyzMax = data.size() + data[xInd].size() + data[xInd] [yInd].size(); for(size_t xInd = 0; xInd < xyzMax; ++xInd) { if(data[xInd] == value) return &data[xInd]; } return 0; } `--- Next, we remove the nested exit point by changing it into a signal to exit the loop... ,--- Value_t* MyClass::findValue(const Value_t& value) { size_t xyzMax = data.size() + data[xInd].size() + data[xInd] [yInd].size(); result = 0; for(size_t xInd = 0; xInd < xyzMax; ++xInd) { if(data[xInd] == value) result = &data[xInd]; xInd = xyzMax; } return result; } `--- Juha asked for an alternative that didn't make use of multiple exit points. This is one way to achieve that -- fold the inner loops (those indices are meaningless) and signal the end to the 'for' loop. So, 3 loop constructs are reduced to 1 4 conditionals are reduced to 2 2 exit points are reduced to 1 Simple, isn't it? Nathan.
From: Thomas J. Gritzan on 10 May 2010 11:16 Am 10.05.2010 16:28, schrieb Nathan: > On May 10, 9:04 am, brang...(a)cix.co.uk (Dave Harris) wrote: >> This seems to mean you need a loop to find the first accessible value >> before you even look at data[xInd][yInd][zInd]. >> > > Then let's just start with Juha's original code and see where some > simple improvements can be made, shall we? > > Given, the original... > > ,--- > Value_t* MyClass::findValue(const Value_t& value) > { > for(size_t xInd = 0; xInd < data.size(); ++xInd) > for(size_t yInd = 0; yInd < data[xInd].size(); ++yInd) > for(size_t zInd = 0; zInd < data[xInd][yInd].size(); + > +zInd) > { > if(data[xInd][yInd][zInd] == value) > return &data[xInd][yInd][zInd]; > } > > return 0; > } > `--- This code iterates over a 3D matrix, so it uses 3 indices. > First, we can remove the nested loops like so... > > ,--- > Value_t* MyClass::findValue(const Value_t& value) > { > size_t xyzMax = data.size() + data[xInd].size() + data[xInd] > [yInd].size(); > for(size_t xInd = 0; xInd < xyzMax; ++xInd) > { > if(data[xInd] == value) > return &data[xInd]; > } > > return 0; > } > `--- This code uses only 1 index operation to data. data[xInd] still has 2 dimensions and can't be compared to the scalar 'value'; the types don't match. Also, you don't go over x_size*y_size*z_size elements but only x_size+y_size+z_size elements. The code doesn't do the same as the other one. [...] > Juha asked for an alternative that didn't make use of multiple exit > points. This is one way to achieve that -- fold the inner loops > (those indices are meaningless) and signal the end to the 'for' loop. > > So, > > 3 loop constructs are reduced to 1 > 4 conditionals are reduced to 2 > 2 exit points are reduced to 1 > > Simple, isn't it? We can also remove all the loops and the function would even be more efficient: Value_t* MyClass::findValue(const Value_t& value) { return 0; // Single Exit point! } Much more simple, isn't it? -- Thomas
From: Nathan Baker on 10 May 2010 12:13
"Thomas J. Gritzan" <phygon_antispam(a)gmx.de> wrote in message news:hs981d$ot3$1(a)newsreader5.netcologne.de... > > This code uses only 1 index operation to data. data[xInd] still has 2 > dimensions and can't be compared to the scalar 'value'; the types don't > match. A computer's RAM has only one dimension. Let us consider the following 2-D array: x | 0 | 1 | 2 0 | a | b | c 1 | d | e | f 2 | g | h | i In RAM, it looks like this: (0,0) a (0,1) b (0,2) c (1,0) d (1,1) e (1,2) f (2,0) g (2,1) h (2,2) i ....which we can also index as... (0) a (1) b (2) c (3) d (4) e (5) f (6) g (7) h (8) i ....so, you can easily see that 'data[2][1]' and 'data[7]' reference the same value. Using one index, rather than three, decreases the complexity of our algo. Nathan. |