on goto
in [General Programming]
|
From: Juha Nieminen on 12 May 2010 08:45 In comp.lang.c++ Richard Heathfield <rjh(a)see.sig.invalid> wrote: > Hyperbole. An O(N^3) algorithm is sometimes necessary, but it is > probably worth spending at least some time trying to come up with a less > costly algorithm. Well, as someone correctly pointed out, the algorithm is actually not O(n^3) but O(n). There are n elements and the algorithm is going linearly through all of them searching for a specific one. That's O(n). It doesn't matter how the elements are arranged in memory. It doesn't make any difference whether the elements are in a one-dimensional or a three-dimensional array. It's still O(n). O(n^3) would be if for each element the algorithm would go through all the elements, and for that pass it would go through all the elements a third time. If you sorted the elements somehow such that you could use a binary search on each single dimension, the algorithm would be reduced from O(n) to O(log n) (and not from O(n^3) to O(log n), which would be way too much of a reduction; a binary search cannot reduce from O(n^3) to O(log n).).
From: Daniel T. on 12 May 2010 08:54 Richard Heathfield <rjh(a)see.sig.invalid> wrote: > pete wrote: > > > I find SEME to be less objectionable in functions > > which are small enough so that you can't look at one exit > > without noticing the all the rest of the exits. > > Yes, I'd agree that this is significantly less objectionable, provided > there's an obvious pattern that links all the returns. > > (Note that our original 3D loop example more or less falls into this > category.) Of course if the function is small, the likelihood of actually gaining efficiency through SEME is reduced (but when it's available, by all means use it.) On the other hand, technically I'm not an SESE kind of guy because like Seebs, I have no problem exiting early if there is a precondition violation. That said, when I write a function that returns something, the first thing I do is create a 'result' variable, then a "return result;", then I back up and put in the body of the function.
From: Juha Nieminen on 12 May 2010 08:56 In comp.lang.c++ Nathan Baker <nathancbaker(a)gmail.com> wrote: > > "Juha Nieminen" <nospam(a)thanks.invalid> wrote in message > news:4be50dcf$0$2544$7b1e8fa0(a)news.nbl.fi... >> In comp.lang.c++ io_x <a(a)b.c.invalid> wrote: >>> with assembly is possible to write recursions functions too >> >> That's like saying that C supports object-oriented programming. > > Of course it does! C certainly has support for data structures. See, that's another hilarious thing about obsessed C programmers: They don't even understand what "object-oriented programming" means or what does it mean for a language to support that. Think about it with a different example: While it's possible to handle arbitrary precision integers in C (for example by using a library like GMP), that doesn't mean the C programming language supports arbitrary precision integers. They are not part of the core language, or even its standard libraries, nor are they mentioned in any way or form in the official standard. Likewise the C language does not support object-oriented programming: It has no native support for classes with restricted compiler-enforced access rights, inheritance or dynamic binding / message dispatching. You can construct an environment which somewhat *simulates* this, but that doesn't mean the C language supports OOP any more than it supports eg. arbitrary precision integers. The main difference between a language which supports OOP directly and a language which does not is the amount of work the compiler does for the programmer.
From: Daniel T. on 12 May 2010 09:02 gwowen <gwowen(a)gmail.com> wrote: > On May 11, 6:44�pm, Seebs <usenet-nos...(a)seebs.net> wrote: > > On 2010-05-11, Richard Heathfield <r...(a)see.sig.invalid> wrote: > > > Seebs wrote: > > > > > You already have a list of foos, properly ordered for fast > > > > > searching. > > > > > > > > No, I don't. > > > > > > Then I suggest you get one. > > > > It's often completely unsuitable to the problem at hand. > > If your problem is not amenable to Richard H's potted solutions, the > fault lies with your problem, not Richard's solution. You should know > this by now. > > So if you have a disk-backed self-caching nested container storing a > 2million * 2million * 2million high resolution MRI scan image, > scrupiously reconstructed using Radon transforms. You're searching > for pixels of a certain shade (that indicate a possible tumor, say)... If you use the 3-D algorithm presented as an example in this thread to do the above, your an idiot. (Remember, the algorithm aborts when it finds *one* object that is the right value.) The fact is, it's quite hard (though maybe not impossible,) to find a justification for using the example provided, even if the example is good for justifying SEME. (Even Seebs example of a dungeon game doesn't work, because it is highly unlikely that such a game would contain a 3-D array that is ragged in each dimension.)
From: gwowen on 12 May 2010 09:45
On May 12, 2:02 pm, "Daniel T." <danie...(a)earthlink.net> wrote: > If you use the 3-D algorithm presented as an example in this thread to > do the above, your an idiot. (Remember, the algorithm aborts when it > finds *one* object that is the right value.) No, but your non-toy algorithm would resemble the original toy algorithm far more closer than it would resemble a toy sort-and-bisect search algorithm. The actual return criteria are more complex in the real life case, but the principal is the same. (If such a tumor hunting algorithm has secondary criteria based on a point and its neighbouring points, sorting-and-bisecting becomes even less useful). Alternatively, that behaviour might be *exactly* what you require, if the search algorithm is looking for *potential* bad pixels, which need to be shown to a consultant for expert assessment. After all, that's what std::find() in the C++ standard library does. coordinate_t find_next_potential_point(const coordinate_t& start = {0,0,0}) { size_t x,y,z; for(x=start.x;x<xdim;++x){ for(y=start.y;y<ydim;++y){ for(z=start.x;z<zdim;++z){ if(criteria_met(x,y,z)) return coordinate_t(x,y,z); } } } return somekindof_not_found_sentinel_or_throw_an_exception_or_container.end(); } > (Remember, the algorithm aborts when it finds *one* object that is the right value.) Which *might* be exactly what is wanted. Usage varies. One size does not fit all. Also, if you're going to say "your an idiot", you'll get a better response if you learn the difference between "you're" and "your". Oh, and the difference between "return" and "abort". |