on goto
in [General Programming]
|
From: Richard on 11 May 2010 08:48 Seebs <usenet-nospam(a)seebs.net> writes: > On 2010-05-10, Daniel T. <daniel_t(a)earthlink.net> wrote: >> Seebs <usenet-nospam(a)seebs.net> wrote: >>> On 2010-05-10, Daniel T. <daniel_t(a)earthlink.net> wrote: >>> > Why shouldn't I assume that the data are contiguous? > >>> Because there's nothing saying they are... > >> There is nothing saying anything at all. > > Good reason not to start adding unsupported assumptions, then. > > You should not assume that they are contiguous, or that they aren't; > you should write code that will work either way unless you have information > saying otherwise. > >>> I'm working on a roguelike game. I have a dungeon, which consists of >>> levels, and the levels are not necessarily all the same size. Each >>> level is itself a 2D grid of points. It is quite conceivable to want >>> to ask the question "is there any point in the dungeon which contains >>> a foo". At this point, the obvious thing to do is >>> for each level >>> for each row >>> for each column >>> is there a foo? > >> I disagree. The obvious thing is to go through your list of MOB's and >> see if any of them are foos. Your list of MOB's will likely be a 1D >> vector or linked list. At most you have a list of MOB's per level and >> even there, each level will be encapsulated. Essentially a recursive >> algorithm. > > What if "foo" isn't a "MOB"? What if "foo" is a kind of a thing of which > there is no master list, just a list associated with each location? Then you add it if there would be a benefit obviously. Sheesh. Look, you screwed up. Get over it and move along. Your solution was naive and inefficient, to put it kindly.
From: Richard Bos on 11 May 2010 10:06 Richard <rgrdev_(a)gmail.com> wrote: > Seebs <usenet-nospam(a)seebs.net> writes: > > > I'm working on a roguelike game. I have a dungeon, which consists of levels, > > and the levels are not necessarily all the same size. Each level is itself > > a 2D grid of points. It is quite conceivable to want to ask the question > > "is there any point in the dungeon which contains a foo". At this point, > > the obvious thing to do is > > for each level > > for each row > > for each column > > is there a foo? > > If you were a complete idiot maybe. More sensible is to have a structure > representing each game object as there are almost certainly less of them > than squares on the grid. You have a list of all altars in the dungeon? Why, for goodness' sake? The only thing important about them is that location L,R,C contains an altar, which is something which should be noted at the location (just as if there were a staircase, or a trap). Almost all of the uses of an altar depend only on there being something in L,R,C and that something being an altar. The only time you want to know where the next altar is, is when the player asks for one using the far-travel command; at that point, your time is bounded by keyboard interaction, so searching every location on the current level is perfectly acceptable. Richard
From: Richard Bos on 11 May 2010 10:14 "Nathan Baker" <nathancbaker(a)gmail.com> wrote: > The CPU experiences a nightmare while executing HLL code. Perhaps there is > an instructive way for us to demonstrate this fact? <http://xkcd.com/371/> Richard
From: Seebs on 11 May 2010 13:36 On 2010-05-11, Richard Heathfield <rjh(a)see.sig.invalid> wrote: > Seebs wrote: >> Having read posts by Mr. Nilges, why do you persist in using English, when >> it is clearly a language which supports apallingly bad writing? > Najlepszy punkt. Moja obrony jest fakt, ?e opr�cz prawdopodobnie C, nie > wiem r�wnie? do?? wszelkich innych wersjach j?zykowych skutecznego > porozumiewania si? w nich. Moje polskie, na przyk?ad, jest po prostu > odmian?. > [Tr: Excellent point. My defence is that, apart from perhaps C, I don't > know any other languages well enough to communicate effectively in them. > My Polish, for example, is simply ghastly.] Heh. > My apologies for the non-ASCII characters in my first paragraph, above. No worries, they were deeply justified. > The underlying source of that problem, as far as I can make out, is what > I have seen described as the "pigeon-hole" approach to programming - the > idea that a programmer's task is simply to put the right numbers in the > right places at the right time, and that nothing else matters. Such a > programming style used to be commonplace (see the story of Mel in TJF > for a somewhat more positive slant on "pigeon-hole" programming). But, > in my view, structure and abstraction provide real and lasting benefits > for large, maintained programs. Good point. > Yes, it's a line, not a binary - to talk about "structured" vs > "unstructured" code is to imagine a polarity that doesn't really exist > in the real world. But I have found that leaning heavily towards the > "structured" end of the line yields real benefits in clarity and > therefore maintainability. Yes. I'm just not entirely convinced that "structured" implies "single exit". I think it might be better understood as implying "using structures according to their design". Several scripting languages are built with structures which, very much intentionally, rely on multiple exits and other control features to provide terseness. Consider the Ruby idiom for looping through a file: file.each do |line| next if line.match(/^#/) # do stuff here last if some_condition end There's no way to write this loop using a SEME model that's anywhere near as legible or clear. The natural idiom of the language is built around looping-over-a-whole-set, with the assumption that if you want to stop earlier, it will. > Sometimes it makes sense to stick to style rules even when departing > from them would do no particular harm and might even do a little good; > sticking to a known-good strategy means spending more time thinking > about the problem domain and wasting less time on thinking about how to > code it. (I know you won't draw the erroneous conclusion that I am > advocating spending /no/ time on thinking about coding.) That can be viable; it reminds me of Feynman's decision to always have chocolate ice cream for dessert because it was never bad and it meant he didn't have to spend time on the decision. I tend to stick to style rules in cases where I think they might be marginally worse, but as soon as the cost becomes prohibitive, the style rule goes. Especially, I might add, if there's a conflict between style rules -- that makes it easier to justify following a secondary rule. -s -- Copyright 2010, all wrongs reversed. Peter Seebach / usenet-nospam(a)seebs.net http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
From: Seebs on 11 May 2010 13:44
On 2010-05-11, Richard Heathfield <rjh(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. >> Why are you running a binary search on this specific array to see whether >> an integer is found in it? You already have a list of integers, properly >> ordered for fast searching; just run through that list and then find out >> which array the integer you want is contained in. > That's precisely why I'm running a *binary* search on this specific > array. Maybe it's my fault, but I'm not seeing your point here. I > originally advocated searching a properly sorted data structure instead > of a brute force search, and you seem to be asking me why I'm doing that > instead of... doing that. My point is that there are many examples of data types for which it would make no sense at all to have a single master list of all objects of that data type. Integers might be one. Objects in a roguelike game are likely another; there's no obvious reason to have a master list of them, because they are all more reasonably associated with some specific container. > Let's think about that, shall we? The original 3-nested loop was looking > for a particular object in, presumably, 3-D space. Let us be kind and > assume that the search was already localised to a particular dungeon. So > presumably we're looking at a 3D version of Rogue, where objects might > be on a shelf, or dangling from the ceiling, or perhaps currently in flight. I was thinking "on any of multiple dungeon levels". > Let us assume further that our location co-ordinates have a granularity > of one foot. We imagine a dungeon 10' tall, with floor dimensions 20' > times 30'. That's 6,000 cells to search. Searching every cell until we > find (or fail to find) the object involves an average search of 3,000 > cells. When the object isn't present, we have to search the whole space > - 6,000 cells. Yes. > We're looking for a treasure chest. We could have a list of objects and > their locations. We could index that list in various ways, one of which > is by object, dungeon, and location within the dungeon. For the brute > force search to be more efficient, log2(number of treasure chests) would > have to exceed 3,000. You wouldn't be able to chuck a brick without > hitting at least a million chests. If searching is hugely common, maybe. If searching is rare, though, the cost of *maintaining* three sorted lists of treasure chests, and three sorted lists of every other object type in the game, plus three sorted lists of each of many categories of objects in the game, MASSIVELY overwhelms the cost of the brute-force search. And in reality, that's the case -- it is extremely common to want to look at "the objects in this specific location", and extremely rare to want to ask questions like "are there any objects of type X". The reasonable thing to do is write the search for objects of type X in a way that is probably slow but certainly simple and requires little maintenance, rather than developing and maintaining a huge number of variously sorted lists. In short: The proposal to create a sorted list is an extremely premature optimization. Unless we have concrete evidence that the brute-force search is hurting execution time, there's not (yet) any reason to avoid it. > I think you have yet to demonstrate a problem space where a nested > search really is the right tool. That is not to say that no such problem > space exists, however, and I am prepared to grant that it /does/ exist. > But, in solving that problem, I would still stick to my style rule, > because I find it easier to read SESE code than I do to read SEME code. If time and resources allowed, I'd love to test that. It would be very interesting to come up with a large pool of things all of which are comparably-well-written versions of SESE and SEME implementations of the same loops. My naive exppectation would be that, human cognition having a great deal of common ground, there would be many cases in which the SEME version would *in fact* be more readable. Meaning that, say, if we had you and a large number of other people who have the same views and preferences read all these loops and tested for common mistakes in reading loops, we'd find that there were many fewer errors with the SEME versions than the SESE versions. The only data point I have (and it's not large enough to justify a firm conclusion) supports this -- we had multiple people misread a SESE loop which no one misread when it was SEME. >> Dogmatically >> asserting that every problem for which a nested loop is the best solution >> exists only because of some other arbitrary flaw is pointless. > I don't recall making any dogmatic assertions about nested loops, and I > certainly don't recall using the word "every" in such a context. Are you > sure you're not trying to extend my position? Hmm. Not entirely. >> We might >> as well point out that English is absolutely the clearest and most expressive >> language, because anyone who wants to say something which is not most clearly >> expressed in English is clearly saying something stupid. > Actually, well-written C is much clearer than well-written English. I > would accept that it is not always quite so expressive, though. :-) Heh. -s -- Copyright 2010, all wrongs reversed. Peter Seebach / usenet-nospam(a)seebs.net http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated! |