«

(Daniel T.) wrote (abridged):
> > 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?
>
> Am I adding extra invariants? I don't know what the invariants are,
> and I have no reason to believe that the code presented solved any
> problem at all.
>
> That's part of the point I'm trying to make here. We have been
> handed an incomplete solution to a nonexistent problem and you are
> asking me if I could write code that "solved the same problem..."
> Here you go:
>
> int main() { }
>
> My example above has the benefit of actually being able to compile
> and run. You can't do that with the original example.

The original code was:

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;
}

If you are truly saying you don't understand what problem this code is
trying to solve, to the point where you claim "int main() { }" is solving
the same problem, then I have trouble believing you are debating in good
faith. How can your code comprehension skills be so poor?

If it helps, I'll add some code.

#include <vector>

using namespace std;
typedef int Value_t;
typedef vector<Value_t> z_vec;
typedef vector<z_vec> y_vec;
typedef vector<y_vec> x_vec;

struct MyClass {
x_vec data;

void test();
Value_t *findValue( const Value_t& value);
};

int main() {
MyClass().test();
}

void MyClass::test() {
findValue( 0 );
}

Putting this in front of the original code is enough to make it compile.
Any competent C++ programmer could have come up with it. I'll let you
write some code to initialise MyClass::data from stdin yourself. If you
are truly incapable of doing that, then I have to question whether your
opinions are worth any weight at all. (I don't need to see the code. I
just want you to stop being obtuse, when you clearly know better.)

There are other ways to define data etc so that the original code
compiles. It shouldn't be necessary to assume more about the problem than
what the original code gave us, which was basically operator[] and size()
as used. That was enough for the original code. Alternative solutions
ought to work with any reasonable definitions, including this one.

You shouldn't assume that the data are contiguous, or that someone else
will write a convenient magic iterator for you.

-- Dave Harris, Nottingham, UK.

On 2010-05-10, Daniel T. <> wrote:
> Why shouldn't I
> assume that the data are contiguous?

Because there's nothing saying they are, and making an assumption without
any support beyond "this would make my code simpler" seems counterproductive.

> In what context is a short-circuit
> linear search appropriate through a 3-D ragged arrayed container? Just
> because that's the way you want it so that you can stand on your soapbox
> and say, "see I told you so"?

Okay, here's a nice concrete case from code I've actually written once
upon a time, or something much like it.

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?

-s
--
Copyright 2010, all wrongs reversed. Peter Seebach / usenet-
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!

In article <daniel_t-BE382C.19303110052010@70-3-168-
216.pools.spcsdns.net>, says...
>
> Seebs <usenet-> wrote:
> > On 2010-05-10, Daniel T. <> 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.
>
> > > In what context is a short-circuit linear search appropriate through
> > > a 3-D ragged arrayed container? Just because that's the way you want
> > > it so that you can stand on your soapbox and say, "see I told you
> > > so"?
> >
> > Okay, here's a nice concrete case from code I've actually written once
> > upon a time, or something much like it.
> >
> > 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.
>
> for each level
> is there a foo?
>
> I ask again, what is your goal in continuing this thread? What is it you
> are trying to get me to admit to that I haven't already admitted?

Are you really unable to conceive of a data structure with more than one
dimention?

I suggest that a web search for the terms "octree" and "quadtree" may
prove interesting to you.

See, for instance:
http://en.wikipedia.org/wiki/Octree
http://en.wikipedia.org/wiki/Quadtree

I would be very keen to see a data structure that can model weather on
the surface of the earth and which does not consist of many levels
(besides spherical coordinates, we have elevation, temperature,
pressure, humidity, wind direction, wind velocity, etc.)
See, for instance, NCAR:
http://ngwww.ucar.edu/

"Daniel T." <> writes:
> Seebs <usenet-> wrote:
>> On 2010-05-10, Daniel T. <> 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.

Then why are you assuming anything?

>> > In what context is a short-circuit linear search appropriate through
>> > a 3-D ragged arrayed container? Just because that's the way you want
>> > it so that you can stand on your soapbox and say, "see I told you
>> > so"?
>>
>> Okay, here's a nice concrete case from code I've actually written once
>> upon a time, or something much like it.
>>
>> 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's a MOB?

> for each level
> is there a foo?

And how do you ask whether there's a foo on a given level?

[...]

--
Keith Thompson (The_Other_Keith) kst- <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

On May 10, 2010 20:03, in comp.lang.c, kst- wrote:

> "Daniel T." <> writes:
[snip]
>> for each level
>> is there a foo?
>
> And how do you ask whether there's a foo on a given level?

...

struct fooType *thisFoo = fooRoot;

...

while (thisFoo != NULL && thisFoo->level != target_level)
thisFoo = thisFoo->nextFoo;

if (thisFoo == NULL)
return NO_FOO_ON_LEVEL;
else
return FOO_FOUND_ON_LEVEL;



HTH
--
Lew Pitcher
Master Codewright & JOAT-in-training | Registered Linux User #112576
Me: http://pitcher.digitalfreehold.ca/ | Just Linux: http://justlinux.ca/
---------- Slackware - Because I know what I'm doing. ------

On 2010-05-10, Daniel T. <> wrote:
> Seebs <usenet-> wrote:
>> On 2010-05-10, Daniel T. <> 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?

Not a purely theoretical question here; in the roguelike I did, this was
basically the case for a number of things, such as items. Each creature
had a list of items it was holding. There did not exist, anywhere, a master
list of items. Or a master list of creatures. Locality of reference FTW...
As long as you don't need to do a search like that.

> I ask again, what is your goal in continuing this thread? What is it you
> are trying to get me to admit to that I haven't already admitted?

You didn't ask me that, you asked someone else that.

I guess I'm just pointing out that all of the "simplifications" I've seen
have been simplifications which relied on massive and unsupported assumptions,
and more importantly, assumptions which are wrong often enough for it to be
a serious problem. There is no general expectation that multidimensional
data structures are contiguous in memory in C; it is much more common for
them to consist of numerous allocated regions which are non-contiguous.

-s
--
Copyright 2010, all wrongs reversed. Peter Seebach / usenet-
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!

On 2010-05-11, Keith Thompson <kst-> wrote:
> "Daniel T." <> writes:
>> Seebs <usenet-> wrote:
>>> 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's a MOB?

In many computer games, creatures are called "mobs" (short for mobiles,
because they can move). It's probably incorrect to turn it into block
caps, since the word did not originate as an initialism, but I could make
sense of it in context. (It's definitely incorrect to put an apostrophe
on the plural, though.)

-s
--
Copyright 2010, all wrongs reversed. Peter Seebach / usenet-
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!

Seebs <usenet-> writes:
> On 2010-05-11, Keith Thompson <kst-> wrote:
>> "Daniel T." <> writes:
>>> Seebs <usenet-> wrote:
>>>> 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's a MOB?
>
> In many computer games, creatures are called "mobs" (short for mobiles,
> because they can move).

Down staircases are not usually mobile, and I was searching for the
down staircase.

> It's probably incorrect to turn it into block
> caps, since the word did not originate as an initialism, but I could make
> sense of it in context. (It's definitely incorrect to put an apostrophe
> on the plural, though.)

I think the ggpp was just trying to blag that he was familiar
with the field in question, and therefore his view must carry
more weight about implementation issues. Is there a commonly-
named logical fallacy for misdirection through use of jargon?

Phil
--
I find the easiest thing to do is to k/f myself and just troll away
-- David Melville on r.a.s.f1

On 2010-05-11, Daniel T. <> wrote:
> Seebs <usenet-> wrote:
>> 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?

> Someone else is already beating you up on this one, so I'll just say
> this... "What if the situation is exactly such that the best solution is
> nested for loops and an early return?" To that I answer, then use nested
> for loops and an early return. What is your point?

My point is: In the case where that loop would have been written at all,
the multiple-exit variant would be by far the cleanest solution. Every
alternative provided has either been noticably more complex, or been
reliant on an obviously-different data structure than the original addressed.

I think in this case I'm pretty much in agreement with you on the issue;
the correct thing to do is make a decision in each case based on the
circumstances at hand.

My objection is to having people invent things ("you look through the list
of foos") which presume a wildly different data structure than had been
suggested.

> My observation is that people often get caught up working at much too
> low a level than they should, and depending on what problem is being
> solved, code like the nested for loop example we have been discussing is
> indicative of that sort of thinking.

That's a good point. I have certainly seen such loops which were indubitably
a result of bad planning.

I guess, offered as "this will necessarily work as a replacement", I find
most of the replacements unappealing. Offered as "this is enough prettier
that perhaps the data should be structured to suit it", many of them might
be a step forwards... Depending, of course, on the specific data.

-s
--
Copyright 2010, all wrongs reversed. Peter Seebach / usenet-
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!

On 2010-05-11, Richard Heathfield <> wrote:
> Seebs wrote:
>> 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?

> No, that's a terrible way to do it.

> You already have a list of foos, properly ordered for fast searching.

No, I don't.

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.

.... or don't.

> If you don't already have a list of foos, then you are excusing one flaw
> in your program by the existence of another flaw in your program. Two
> bugs don't make a sensible programming strategy.

I disagree. It is not at all obvious that "foo" is necessarily a type of
thing that ought to have a central list. When doing a model of a world,
it is quite often the case that there are many hundreds of types of objects
which might exist, and each location has a list of the objects it contains.
A single centrally sorted list of all the objects of each type would be
ludicrous. A single centrally sorted list of all the objects which exist
anywhere would be of extremely marginal utility. In particular, for the
case of, say, a roguelike game which includes multiple dungeons, searching
a given dungeon (using the nested loop) would be orders of magnitude faster
than searching a complete list of every object stored anywhere in the game.

In short:

It depends. There exist problem spaces for which a nested search really is
the right tool. There exist others for which it isn't. Dogmatically
asserting that every problem for which a nested loop is the best solution
exists only because of some other arbitrary flaw is pointless. 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.

-s
--
Copyright 2010, all wrongs reversed. Peter Seebach / usenet-
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!