B
Bruce Cook
Keith said:
Ouch !
That would be particularly fun with libraries
Bruce
Ouch !
That would be particularly fun with libraries
Bruce
B
bartc
Bruce Cook said:
Some things are better with 0-based, and some with 1-based.
It doesn't have to be a choice; you can just allow both **.
However, if you have to choose one form, 0-based might be better, but only
because you can use 1-based indexing by allocating an extra element and
ignoring element 0. It's more difficult the other way around.
(** the design of some languages seems to demand that one base is the
default or 'natural' base for indexing, even when both (or any) base is
possible.)
M
Michael Foukarakis
Although I am reluctant to use 'equally apt' or 'more apt', I'd say
Erlang or Haskell are very good at expressing algorithms in a neat
fashion. Other high level languages such as Ruby or Python spring to
mind as well. I think an advantage of C over those is that it's
adequately readable (at least when we're not trying to write an IOCCC
entry..) even as it's significantly "closer" to manipulating the
machine.
On topic, the book is actually very comprehensive, very concise, and
deals with some quite interesting data structures. I liked it.
G
gwowen
On a not-entirely-unrelated-note, I acquired a copy of Sedgwick's
"Algorithms In C" at the weekend (3 pounds in the Wooden Canal Boat
Society Charity Shop == result). He covers lists, arrays and various
balanced trees. Is there anything in Barnes that's not in Sedgwick?
J
jacob navia
gwowen a écrit :
I will tell you in a few weeks. I bought Sedgewick in Amazon but
it was sold out. I had to wait several weeks until they shipped it and
it is still not here yet.
jacob
I will tell you in a few weeks. I bought Sedgewick in Amazon but
it was sold out. I had to wait several weeks until they shipped it and
it is still not here yet.
jacob
N
Nick
gwowen said:
Despite what you see in my sig, it's not mine! Mine's just "Algorithms"
- they're in either Pascal or a pascal-like pseudo code. I actually
prefer to implement myself from pseudo code than have them given to me.
F
Flash Gordon
bartc said:
Not all of the world is i x86.
Now try on a DSP or some other embedded processor. Not everything can do
that trick.
It might be a function call. If you build your software for 0 based
arrays you build it in to the calculation, if it is 1 based you can't do
that and if it is a function doing the calculation it might not be
possible for the compiler to optimise away.
I was referring to the problems you can have in the implementation for a
specific architecture.
On some of the ones I've used you can't.
You might be surprised at the complexity of problem which is solved
using small processors, or at least processors which don't have such
fancy addressing modes.
If the language uses one-based arrays you can't convert it to zero based!
As I said earlier, in a language which allows I'll use whatever fits
best. However, there are good reasons for using zero-base in the
language when performance is critical.
B
bartc
Flash Gordon said:
I didn't fully understand the gcc code, but it seemed to find a way of doing
with just two extra offsets instead of the four one might expect. If this is
just clever logic then it can be applied to whatever address calculations
are needed for any processor.
On the DSP, do you have an example part-number? It might be interesting to
find out just what it is capable of.
With up to 4 function calls the relative cost of any offset operations falls
even further.
Then they might also have trouble with some ordinary array and struct
accesses.
OK, I would have expected a compiled language targeted at basic hardware to
have a choice of array lower bounds.
Then it would be no different from many other decisions programmers have to
make regarding the efficiency of their code: dynamic arrays are slower than
static (flat) ones; 32-bit elements can be slower than 16-bit elements; and
a lower bound of 1 can be slower than one of 0, in some cases.
F
Flash Gordon
bartc said:
If the array is not a static array then you can't use the fixed offset
trick without doing extra arithmetic at run time.
I spent a lot of time programming the TMS320C25 both in assembler and C
some years back, and the TMS320C80, both of which are Texas Instruments
DSPs. I've actually been out of the embedded world for a while though.
On some processors a call is cheap but address arithmetic is expensive.
One is careful about what you use where.
I don't know of any where zero doesn't work well, but one does not
always work well.
I've got no objection to a language allowing each array to be based
differently, or even allowing other things such as an enumerated types
an array index, it gives you the choice. I've got no major objection to
using one as a base either, I just don't think it would have been the
right choice for C.
R
Richard Bos
jacob navia said:
It's perfectly obvious if you are slightly familiar with set theory, and
completely opaque otherwise. That's what's wrong with all operator
overloading, in fact: it allows you to create code of arbitrary
impenetrableness that looks like it _should_ be obvious, but does
unpredictably complicated things behind the scenes.
Richard
R
Rui Maciel
Stefan said:
You may be right that error checking should be performed. Nonetheless, what's
important in the real world source code (validate everything) isn't necessarily
what's important in a technical or academic publication (illustrate concepts and
convey ideas).
When an author starts to include each and every validation test in a code
snippet example then the example code becomes verbose. As a consequence, the
reader's attention will also be on minor and even irrelevant details and it will
be a bit more difficult to get the gist of what the author tried to communicate
through the example code, all of this while filling page after page of
untestable code. After all, who is going to happily waste their precious time
transcribing pages after pages of source code examples? So, to put it in other
words, if you explicitly include validations in your examples then getting to
the point becomes a little bit less efficient. And needlessly so.
There are authors who understood perfectly the need for succinct source code
examples and also placed a great value on the need to perform validations
thoroughly. One such author was Richard Stevens. In his series of books he
made a point in providing source code examples which were straight to the point
and unencumbered by those long, tedious series of sanity tests, which are pretty
much irrelevant for the topic being discussed. As a result, his explanations
are clear, straight to the point and very easy to understand. Yet, all
validations were kept in the code. The thing is, he achieved that by writing
wrappers for the system calls he used in the examples, which he included in
custom-tailored header files, in effect sweeping the cruft under the rug.
The problem with that approach is that, although it's a blessing for those who
are patiently reading the book from start to finish, not missing a beat, it
represents a small source of problems for those who use the book more as a
reference instead of a casual read. The code snippets don't compile, the
functions being used don't actually exist and some headers are nowhere to be
found. Although that problem can be easily surpassed by RTFB, it still poses as
a problem to clueless newbies.
So, if an author omits a series of irrelevant validations from a book's source
code snippets then that is not a problem, much less a demonstration of how to
write sloppy code. It is, in fact, a great way to both help the reader
understand what the book is actually about and preserve the book's usefulness as
a reference work. It's far better than both diluting your example in a sea of
if() blocks and relying on clever tricks such as wrappers. Therefore the author
should be commended by omitting the tests, instead of being criticized.
And on a side note, testing the return of a malloc() call is terribly basic
stuff, in the sense that if you fail to understand the need for that, even when
missing from the examples, then probably you should be reading a book on basic C
programming before delving into that one.
Rui Maciel
S
Stefan Ram
Rui Maciel said:
Yes, but for C programming memory management is not an
irrelevant detail.
If the author would have wanted to focus on how to do
it /without manual memory management/ he could have chosen
a language with a garbage collector, like Java, or - if it
had to be C-like - a C-like language with a garbage collector,
like C with the Boehm collector. But he had chosen to use C.
Taking the possibility of a 0 result of malloc into account
is not what I deem to be a »sanity« test ...
... nor irrelevant for C programing.
And then the author /does not even discuss/ this problem.
It would not have been such a bad book, if he would have first
explained how to do proper memory management in C and then why
he will not use this in the rest of the book. But he did not
mention this. Which gives the impression that he might not even be
aware of it.
I agree that the author of "Advance Data Structures" should
have read a book on basic C programming.
S
Stefan Ram
superpollo said:
I don't know - maybe someone else can answer this question?
(All I know is that according to ISO/IEC 9899:1999 (E) 7.20.3.3p3
malloc might return a null pointer.)
G
gwowen
Must every didactic book assume that the reader must be educated on
the basics? One might as well complain that "Algorithms in C" doesn't
tell me what a compiler is, or how to plug my computer. It would
surely have sufficed for the introduction to say "Of course, every
call to malloc() should be checked. These checks have been elided for
the sake of clarity."?
ObTroll: Of course, if malloc() threw an exception, we could abstract
all these sanity checks elsewhere
J
jacob navia
Stefan Ram a écrit :
Yes it is. If malloc fails, the program crashes. So what?
That's a correct behavior for a sample program!
You can use C as an implementation language without discussing C
memory management, C treatment of errors, C errno function,
C file handling, etc.
Why do you think that a crash is a bad behavior there?
The author is showing how to implement abstract data structures
not bullet proof C code!
What do you know?
And why is so important that he knows C?
When I buy a book about advanced data structures I am NOT ineterested
in C but in data structures!
And besides, nobody cares. What you fail to understand is that
the subject of the book is NOT "Correct C programming" but
implementation of advanced data structures!
You haven't read the book, you do not understand the subject, and the
only thing you are able to do is to repeat your pedantic detail
wisdom again and again.
Those programs are designed for giving you an understanding of what is
going on when implementing advanced data structures; You are supposed to
ADAPT them to your needs, add the error checking and all the other
stuff.
For instance when usning keyed trees, the author simplifies keys
comparisons, assumes all data is passed by pointers only, and many other
things.
Even with those drastic simplifications the programs are hard to follow.
If he would have integrated all the necessary things the programs would
be MUCH bigger and the subject matter would be lost in a maze of
details that would make much more difficult to understand what is
going on.
To teach something it is better to make an abstraction that is simple
for the student to grasp and not present every irrelevant detail!
Yes it is. If malloc fails, the program crashes. So what?
That's a correct behavior for a sample program!
You can use C as an implementation language without discussing C
memory management, C treatment of errors, C errno function,
C file handling, etc.
Why do you think that a crash is a bad behavior there?
The author is showing how to implement abstract data structures
not bullet proof C code!
What do you know?
And why is so important that he knows C?
When I buy a book about advanced data structures I am NOT ineterested
in C but in data structures!
And besides, nobody cares. What you fail to understand is that
the subject of the book is NOT "Correct C programming" but
implementation of advanced data structures!
You haven't read the book, you do not understand the subject, and the
only thing you are able to do is to repeat your pedantic detail
wisdom again and again.
Those programs are designed for giving you an understanding of what is
going on when implementing advanced data structures; You are supposed to
ADAPT them to your needs, add the error checking and all the other
stuff.
For instance when usning keyed trees, the author simplifies keys
comparisons, assumes all data is passed by pointers only, and many other
things.
Even with those drastic simplifications the programs are hard to follow.
If he would have integrated all the necessary things the programs would
be MUCH bigger and the subject matter would be lost in a maze of
details that would make much more difficult to understand what is
going on.
To teach something it is better to make an abstraction that is simple
for the student to grasp and not present every irrelevant detail!
S
Stefan Ram
gwowen said:
In C, memory management is an integral part of the algorithm,
and it is hard. Just ignoring it and then implementing a list
or a tree is trivial (beginner's programming style).
What you suggest sounds to me as if someone would suggest to
implement a factorial as:
int factorial( int arg ){ return arg * factorial( arg - 1 ); }
and then, when someone mentions that »arg« might be 0, someone
else would defend this function by arguing that this check was
elided for the "sake of clarity". But it just is wrong.
B
Ben Bacarisse
superpollo said:
No. malloc can return NULL even is such cases. Some systems don't do
this by default, but even then the behaviour can often be changed by
mechanisms outside of your C implementation.
L
lacos
malloc() does return a null pointer on GNU/Linux.
http://groups.google.com/group/comp.lang.c/msg/b6b1aff01a34738d?dmode=source
(Message-ID: <wzGFrnpa6nP$@ludens>)
Cheers,
lacos
G
gwowen
So you say. I don't think its part of the algorithm at all, I think
its part of the implementation. I disagree, but I respect that you
differ. However, you have not convinced me. If I want to read about
the complexities of error handling in low memory situations I will buy
"C Error Handling Unleashed". If I want to read about data
structures, and worry about error handling later, I'll buy a book on
data structures. Personally I don't need to be reminded to check
malloc() in didactic examples, unless the thing being taught is error
handling...
Alternatively, if the lack of error handling upsets you so much,
pretend every malloc call is replaced by:
void *xmalloc(size_t sz){
void *ret = malloc(sz);
if(ret) return ret;
fprintf(stderr,"Out of memory"\n");
fflush(NULL);
abort();
}
Any more complicated error handling than that is likely to be so
dependent on application domain and platform that it would not be
relevant to a general purpose algorithm book. I'd be interested to
see you suggest what the error handling should look like in such a
general-purpose book.
S
Stefan Ram
gwowen said:
Yes, this question is exactly what the author of such
a book should discuss! In the case of the book given,
he missed to do this.
When implementing data structures in C, the implementation
needs to have a documented policy towards run-time errors.
Authors of such implementations need to be aware of the
different options. This is not beginner's material. This is
hard. Beginner's material is implementing data structures
and ignoring this question.