Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Advanced data structures

Reply
Thread Tools

Advanced data structures

 
 
Ben Bacarisse
Guest
Posts: n/a
 
      12-12-2009
James Dow Allen <(E-Mail Removed)> writes:

> On Dec 12, 4:03Â*pm, jacob navia <(E-Mail Removed)> eut ecrit:
>
>> [Check out Peter Brass's book. Source code on-line.]

>
> I looked at the source for tries (digital search trees) and was
> disappointed to see that he didn't use "traversor structures."
> I know Ben Pfaff uses such things, and it seems excellent idea.
> Do others use them? Can Brass' examples be recommended if he
> *doesn't* use them?


I'll pass on that for the moment (for one thing, I have not read the
book so there may be good reasons to keep the emphasis on other
aspects of the implementation -- it would not be fair to comment on
the basis of the code alone).

However, it seems a shame not to have had someone who knows C really
well read over the code first. There is, of course, cast malloc calls
(almost everyone does this so I suppose that fight is over) but there
is also sizeof(char) and (int)'\0'. In fact lots of expressions that
will promote to int are cast to int, often with extra parentheses.

We also have an idiosyncratic layout that is never consistent. Almost
every possible arrangement of spaces are used with parentheses ([] and
() alike) and operators, for example.

That last is just my being fussy, but there is also a fixed size stack
that can overflow in the trie delete code and comments like:

next_char += 1; /* move to next character */

I'd also prefer to see returns from malloc checked and a rather less
cavalier attitude to integer overflow. There are real cases
where un-trapped overflow leads to a negative hash table index and
where other assumptions about arithmetic leads to similar UB. I could
provoke a segmentation fault from the example code very easily.

If the book is other wise good, all of these are a real shame.
Someone could probably have corrected the code with only few days
work.

<snip>
--
Ben.
 
Reply With Quote
 
 
 
 
Ben Bacarisse
Guest
Posts: n/a
 
      12-12-2009
jacob navia <(E-Mail Removed)> writes:

> Stefan Ram a Ă©crit :
>> jacob navia <(E-Mail Removed)> writes:
>>> I find this book excellent. Everything is written in C, it

>>
>> It seems to allocate a stack entry
>>
>> st = (stack_t *) malloc( ...
>>
>> and then, in the next line
>>
>> st->base = ...
>>
>> it seems to use »st« without ever taking account for the
>> possibility that »st« might be 0?
>>
>> This might be fine when a program is used by the programmer
>> himself, who can cope with segment violations or other
>> strange runtime-behavior. But it might not be appropriate
>> when software is intended to be delievered as a product to a
>> customer who needs to depend on it.
>>

> He does that, as he explains in the text, because they are replaced
> in the next section by a heap implementation where he builds an
> intermediate layer (as I did for the list container) that allocates
> nodes from a linked list of blocks.


I don't see how that solves the problem for a malloc call. Also, if
the free list code is as in the online examples, it too suffers from
un-tested malloc returns so the problem is simply duplicated rather
then solved.

> The book is not a fool proof receipt book, it is a book about
> advanced data structures. The code is just to illustrate the text!


--
Ben.
 
Reply With Quote
 
 
 
 
Eric Sosman
Guest
Posts: n/a
 
      12-12-2009
On 12/12/2009 9:54 AM, Stefan Ram wrote:
> jacob navia<(E-Mail Removed)> writes:
>> What I mean with this sentence is that when reading code about an
>> algorithm, it is easier to read if the error handling code is not
>> shown.

>
> I have another definition of »algorithm«: An algorithm is
> the implementation of some feature using the means of a
> specific target language. [...]


You're free to use words in your own way ("Who's to be
master?" -- H.D.), but your definition of "algorithm" is at
variance with the accepted meaning. That's likely to create
confusion and raise barriers to communication, just as if
you made an appointment to meet someone at noon, using your
own private definition of "noon" as "when the Moon rises."

But back to "algorithm:" Under your definition, there's
one "algorithm" for finding the GCD of two numbers in C,
another for C++, another for Basic, another for Java, ...
As a competent programmer, it seems you must learn a new
"algorithm" for every programming language, perhaps even for
every framework. That seems an awfully heavy cognitive burden.

In fact, under your definition "Euclid's Algorithm" is
an empty fiction, and ought to be something like "Euclid's
Recipe" or "Euclid's Way Of Going About It." There is
clearly an implementation-independent Something about this
GCD-finding approach; what do you call that i-i S, since
you use "algorithm" for something else?

Please answer before "noon."

--
Eric Sosman
http://www.velocityreviews.com/forums/(E-Mail Removed)lid
 
Reply With Quote
 
Stefan Ram
Guest
Posts: n/a
 
      12-12-2009
Eric Sosman <(E-Mail Removed)> writes:
>>I have another definition of »algorithm«: An algorithm is
>>the implementation of some feature using the means of a
>>specific target language. [...]

>one "algorithm" for finding the GCD of two numbers in C,
>another for C++, another for Basic, another for Java, ...


The GCD requires the mod operation. So, when a language
does not have a mod operation, an implementation of the
mod operation becomes part of the implementation of the
GCD, otherwise it don't.

In Haskell, the GCD is very »straightforward«, as it's
fundamental assertions can be written »directly«:

http://en.literateprograms.org/Eucli...rithm_(Haskell)

But in Prolog, a »Tricky version« sometimes is needed:

http://en.literateprograms.org/Eucli...m_%28Prolog%29

, which is another means to calculate the GCD.

The language

http://en.wikipedia.org/wiki/Brain%66%75ck

has yet another set of elementary operations, so someone
who knows how to calculate the GCD using the elementary
operations of C might not be able to calculate it using
the elementary operations of this language »Brain...«.

If you have another definition of »algorithm« than I do,
feel free to post its wording.

 
Reply With Quote
 
jacob navia
Guest
Posts: n/a
 
      12-12-2009
Stefan Ram a Ă©crit :
>
> If you have another definition of »algorithm« than I do,
> feel free to post its wording.
>


www.dictionary.com:

alâ‹…goâ‹…rithm
–noun
A set of rules for solving a problem in a finite number of steps, as for
finding the greatest common divisor.

Origin:
1890–95; var. of algorism, by assoc. with Gk arithmós number. See
arithmetic

Note that no programming language (or language at all) is mentioned.
An algorithm is a set of rules to do something mathematically. The only
condition is that the number of steps should be finite.
 
Reply With Quote
 
jacob navia
Guest
Posts: n/a
 
      12-12-2009
Stefan Ram a écrit :
> jacob navia <(E-Mail Removed)> writes:
>> In my implementation of the heap I did test for NULL return,
>> and I issue the corresponding error. In a book about advanced
>> data structures that is just a distracting detail.

>
> I would not actually issue from a library function in the
> sense of a side-effect with access to external files or
> consoles or so, but just return 0.


I call the established error function for the container where the error
happens. Depending on the severity of the error, that function
(that the user of the library can replace with a function of
his/her own) the library exists, shows an error message or just returns.
If the library error function returns, then I just pass the error
to the calling function.

jacob
 
Reply With Quote
 
Stefan Ram
Guest
Posts: n/a
 
      12-12-2009
http://www.velocityreviews.com/forums/(E-Mail Removed)-berlin.de (Stefan Ram) writes:
>In Haskell, the GCD is very »straightforward«, as it's
>fundamental assertions can be written »directly«:


»it's« should be »its« instead.

>But in Prolog, a »Tricky version« sometimes is needed:


And the most obvious example: In a language, where the GCD
can be calculated with the operator »o«, the algorithm for
the GCD of x and y is just »x o y«.

 
Reply With Quote
 
Stefan Ram
Guest
Posts: n/a
 
      12-12-2009
jacob navia <(E-Mail Removed)> writes:
>alâgoârithm
>ânoun
>A set of rules for solving a problem in a finite number of steps, as for
>finding the greatest common divisor.
>Note that no programming language (or language at all) is mentioned.
>An algorithm is a set of rules to do something mathematically. The only
>condition is that the number of steps should be finite.


Those »steps« must assume that some »elementary operations«
are already given. Therefore, the steps depend on those
elementary operations.

You can not give any algorithm without this assumption
(of a given set of elementary operations) (just try it).

 
Reply With Quote
 
Phil Carmody
Guest
Posts: n/a
 
      12-12-2009
(E-Mail Removed)-berlin.de (Stefan Ram) writes:
> jacob navia <(E-Mail Removed)> writes:
>>alâgoârithm
>>ânoun
>>A set of rules for solving a problem in a finite number of steps, as for
>>finding the greatest common divisor.
>>Note that no programming language (or language at all) is mentioned.
>>An algorithm is a set of rules to do something mathematically. The only
>>condition is that the number of steps should be finite.

>
> Those »steps« must assume that some »elementary operations«
> are already given. Therefore, the steps depend on those
> elementary operations.
>
> You can not give any algorithm without this assumption
> (of a given set of elementary operations) (just try it).


Yes, but those steps do not need to assume that those
elementary operations are native to the language, merely
implementable in that language.

Phil
--
Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1
 
Reply With Quote
 
Stefan Ram
Guest
Posts: n/a
 
      12-12-2009
Phil Carmody <(E-Mail Removed)> writes:
>>Those »steps« must assume that some »elementary operations«
>>are already given. Therefore, the steps depend on those
>>elementary operations.

>Yes, but those steps do not need to assume that those
>elementary operations are native to the language, merely
>implementable in that language.


For a calculation to be actually executable in a language,
it is not sufficient for those operations to be merely
"implementable". They have to be /actually implemented/. Thus,
their implementation is a necessary part of the implementation
of the calculation.

In Haskell, the calculation the GCD of x and y just seems to be:

gcd x y

http://www.zvon.org/other/haskell/Ou...ude/gcd_f.html

. In C, it might be written instead:

int gcd( int a, int b )
{ int c; while( a ){ c = a; a = b % a; b = c; }return b; }

(...)

gcd( x, y )

. We see now that in C, where there is no elementary »gcd«
operation as in Haskell, we have to write its implementation
using a loop and other elementary operations (such as »%«).
Thus, this implementation becomes part of the code necessary
to perform the calculation in C.

Therefore, a loop with a remainder operation is a part of
the implementation in C, but not part of the implementation
in Haskell.

So there is not much common between those two
implementations to extract a »general course of action« to
calculate the GCD in an arbitrary language when we do not
know its set of elementary operations.

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: Advanced Python Programming Oxford Lectures [was: Re: *Advanced*Python book?] Michele Simionato Python 1 03-27-2010 06:10 AM
Help with Repeater control and advanced data manipulation Mike Cain ASP .Net 2 10-22-2006 09:31 AM
structures, structures and more structures (questions about nestedstructures) Alfonso Morra C Programming 11 09-24-2005 07:42 PM
ADVANCED data matching? HotRod ASP .Net 2 04-12-2005 01:13 PM
Type Casting IPv4 and IPv6 structures to Generic Structures tweak C Programming 14 06-11-2004 02:43 PM



Advertisments