on goto
in [General Programming]
|
From: Dave Harris on 9 May 2010 11:34 nathancbaker(a)gmail.com (Nathan) wrote (abridged): > > � while ( data[xInd][yInd][zInd] != value && result != 0) > > � { > > � � � if {++zInd == data[xInd][yInd].size()) { > > � � � � � zInd = 0; > > � � � � � if (++yInd == data[xInd].size()) { > > � � � � � � � yInd = 0; > > � � � � � � � if (++xInd == data.size()) > > � � � � � � � � � result = 0; > > � � � � � } > > � � � } > > � ... > > > > Isn't <something>.size() a method or function call? We'd also want > to eliminate that needless activity from the loop by defining "zMax = > data[xInd][yInd].size()", and etc., before the loop. That would introduce another bug. We're not told that all the arrays are the same size, so for example data[0][0].size() might be different to data[0][0].size(). We could cache the result of size(), but we'd then have to update it when the corresponding index changed. That's easy enough in the original nested-loop code, but gets quite complicated in the single-loop version. (I was going to post some example code, but it was frankly too long and ugly.) This thread has been cross-posted to a lot of groups, and some people seem to be commenting without knowing C++ or knowing what an expression like data[xInd][yInd].size() probably means. The data structure might be declared like: typedef std::vector<int> z_vec; typedef std::vector<z_vec> y_vec; typedef std::vector<y_vec> x_vec; x_vec data; The memory is unlikely to be contiguous. -- Dave Harris, Nottingham, UK.
From: Daniel T. on 9 May 2010 12:31 Nick <3-nospam(a)temporary-address.org.uk> wrote: > "Daniel T." <daniel_t(a)earthlink.net> writes: > > Nick <3-nospam(a)temporary-address.org.uk> wrote: > > > "Daniel T." <daniel_t(a)earthlink.net> writes: > > > > Seebs <usenet-nospam(a)seebs.net> wrote: > > > > > On 2010-05-08, Richard Heathfield <rjh(a)see.sig.invalid> wrote: > > > > > > Seebs wrote: > > > > > > > On 2010-05-02, Richard Heathfield <rjh(a)see.sig.invalid> wrote: > > > > > > > > > > > > > > Because, in some cases, the checks against a[i] make it > > > > > > > harder to follow the code. > > > > > > > > > > > In my experience, it is generally easier to follow the code > > > > > > if it has a clear structure. > > > > > > > > > > I would agree that it is *GENERALLY* easier. > > > > > > > > > > But in some cases it's not. > > > > > > > > > > The vanilla loop idiom ("for (i = 0; i < N; ++i)") has a HUGE > > > > > weight of idiomatic clarity -- it does not require noticable > > > > > attention to model it, and that clarity is lost as soon as you > > > > > change the loop condition. > > > > > > > > > > In short: > > > > > for (i = 0; i < N; ++i) > > > > > if (foo(i)) > > > > > return i; > > > > > return -1; > > > > > > > > > > is nearly always much easier for a programmer to grok in fullness > > > > > than > > > > > for (i = 0; i < N && !foo(i); ++i) > > > > > ; > > > > > if (i != N) > > > > > return i; > > > > > else > > > > > return -1; > > > > > > > > While both of the above are much worse than: > > > > > > > > int i = 0; > > > > while (i < N && !foo(i)) > > > > ++i; > > > > return i; > > > > > > > > The above is a standard idiom in C++. > > > > > > That one doesn't distinguish between "found" and "not found". > > > > Of course it does, and it does so more efficiently. For the other > > examples "if (i != N)" is checked and then later "if (result != -1)" > > must be checked. With the example I presented only one "if" is > > necessary. > > Am I being particularly dumb here (it's been known). Are you saying > that you elsewhere in the code you use i!=N as the check? In which > case, I suppose so, but it's a pain to use if 'N' isn't easily > calculable or available later (say it's not actually i<N but a test > against a sentinal). In this particular case 'N' (as opposed to 'n') implies that it's a macro. In any case a specific range is being checked, and it would be very poor design to define the range solely within the function in question. Typically it is passed into the function, which means it is available to the caller. > > (Note here, I'm not arguing for single exit in every case, but it's > > clearly a better choice in *this* example. > > Only if you're prepared to check against N whenever you need to (or - as > I've said - I'm missing the blindingly obvious). Again, the calling code must do an 'if' check in any case, so the question is, why is the function *also* making the check? If by some odd stroke the calling code doesn't know the value of 'N' that can easily be fixed.
From: Daniel T. on 9 May 2010 12:44 brangdon(a)cix.co.uk (Dave Harris) wrote: > daniel_t(a)earthlink.net (Daniel T.) wrote (abridged): > > > > > I considered submitting a single loop solution as a joke. It > > > never crossed my mind someone would seriusly propose it! > > > > I seriously proposed it. I think it is the best solution for the > > job (not your code specifically of course, but the idea of a single > > loop traversing a single container.) > > 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. > > For example, you can't just initialise the iterator's members to 0,0,0 > because data.size() might be 0 and data[0][0][0] may not exist. So you > need a loop inside the iterator's constructor to find the first iterator > value that can be dereferenced, and another loop inside the iterator's > increment operator to find the next one. > > I think. If someone posted actual, correct code, I missed it. Did you try > implementing the iterator you suggested? Did it still have 3 loops > really? 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. People often advocate using nested vectors to implement multi-dimensional arrays, even when they are not ragged arrays, and the OP may have been expressing that sort of code. In a situation where ragged arrays are necessary, it is highly unlikely that they will be treated as a contiguous unit as the OP's code does. But in any case, no more can be said unless a real use-case is presented. All I'm saying is that the assumption that three loops are necessary to express an O(n) algorithm is inappropriate.
From: Nick on 9 May 2010 13:30 "Daniel T." <daniel_t(a)earthlink.net> writes: > Nick <3-nospam(a)temporary-address.org.uk> wrote: >> Only if you're prepared to check against N whenever you need to (or - as >> I've said - I'm missing the blindingly obvious). > > Again, the calling code must do an 'if' check in any case, so the > question is, why is the function *also* making the check? If by some odd > stroke the calling code doesn't know the value of 'N' that can easily be > fixed. But the function is only *also* making the check because we've eliminated the early return. With the early return there's no need for the second check. Taking Richard H's joke that I missed last time, here we go round the loop again. -- Online waterways route planner | http://canalplan.eu Plan trips, see photos, check facilities | http://canalplan.org.uk
From: Daniel T. on 9 May 2010 14:25
Nick <3-nospam(a)temporary-address.org.uk> wrote: > "Daniel T." <daniel_t(a)earthlink.net> writes: > > Nick <3-nospam(a)temporary-address.org.uk> wrote: > > > > > Only if you're prepared to check against N whenever you need to > > > (or - as I've said - I'm missing the blindingly obvious). > > > > Again, the calling code must do an 'if' check in any case, so the > > question is, why is the function *also* making the check? If by some > > odd stroke the calling code doesn't know the value of 'N' that can > > easily be fixed. > > But the function is only *also* making the check because we've > eliminated the early return. With the early return there's no need for > the second check. All I'm saying is that you can remove the early return *and* the extra 'if' check, if you aren't dogmatic about the not-found flag being -1. > Taking Richard H's joke that I missed last time, here we go round the > loop again. Not at all. If for some reason the function *must* return -1 for a not-found flag, then an early return is the correct choice; however, I'm questioning that assumption. I'm not going back around the loop, I'm moving up a level of abstraction. |