finding maximum

[Tad J McClellan]

["Followup-To:" header set to comp.lang.perl.misc.]

Actually this is not a homework, I am just curious.

Yeah right.

Anyways, here is my solution:

(a) in C:

int max(int a, int b)
{
if(a>b)
return a;
return b;
}

in Perl:

sub max
{
my $max = shift;
for(@_) {
$max=$_ if($_>$max)
}
$max;
}


(b) in C:

#define NUMMAX (10)
int max(int a[NUMMAX])
{
int max = -1;
for(int i=0; i < NUMMAX
if(a[i++]>max)
max = a[i-1];
return max;
}


In Perl: the solution for (a) still works.

Conclusion: Perl is more expressive as a simple function for two arguments
often generalizes to any list.

That is a load of hooey.

You are not comparing languages, you are comparing algorithms.

If you had used the high water mark algorithm in C's (a), then it would have
generalized just as well as the high water mark algorithm in Perl's (a) did.


#define NUMMAX (10)
int max(int a[NUMMAX])
{
int max = a[0];
for(int i = 1; i < NUMMAX; i++)
if(a > max)
max = a;
return max;
}

 

[Martin Ambuhl]

In C,
the conditional operator would be more idiomatic
for two numbers of any type.

#define max(A, B) ((B) > (A) ? B : (A))

Avoiding multiple evaluation is a problem with this. It needs to be a
bit longer.

 

[vippstar]

Avoiding multiple evaluation is a problem with this.  It needs to be a
bit longer.

You're saying that it can be written without evaluating the arguments
more than once? How?

 

[Keith Thompson]

You're saying that it can be written without evaluating the arguments
more than once? How?

At the cost of not being able to handle multiple types:

inline int max(int a, int b) { return a > b ? a : b; }

 

[Beej Jorgensen]

inline int max(int a, int b) { return a > b ? a : b; }

Would it be accurate to say that the former is guaranteed to be
"inline" (as it's baked in before compilation), while the latter might
not be?

-Beej

 

[user923005]

Would it be accurate to say that the former is guaranteed to be
"inline" (as it's baked in before compilation), while the latter might
not be?

I see no reason why the compiler would be unable to create a function
and call it, as long as it obeyed the 'as-if' rule. It is most likely
that a function-like macro will be inline because it is unlikely that
most compilers are smart enough to create a function, even when it
would clearly be advantageous to do so (for either speed reasons or to
avoid undefined behavior by introduction of a function call sequence
point).

Of course, it may cause the program to be [e.g. 100x] slower because
of spilling the cache when the macro is expanded throughout the code.

At any rate, max(x,y) over N items is O(N). This is the dominant
feature of the operation and niggling details pale in comparison.

IMO-YMMV

 

[vippstar]

Would it be accurate to say that the former is guaranteed to be
"inline" (as it's baked in before compilation), while the latter might
not be?

But the same is true even if 'inline' was missing. A compiler can do
whatever he wants to when it comes to optimization, as long as the
behavior of the program is the same.

 

[vippstar]

At the cost of not being able to handle multiple types:

    inline int max(int a, int b) { return a > b ? a : b; }

I had thought Martin Ambuhl meant that it's possible to write a macro
that does this.
IMO I'd prefer to use a macro for a portion of code to improve
readability, and I'd provide a function if the concept isn't straight-
forward, or I need to pass it somehow as a function pointer.

For example:

#define MAX(a, b) ((a) > (b) ? (a) : (b))
i = MAX(j, k);
/* ... */
#undef MAX

and

foo_t max = foo_max(p, q);
foo_t m_max = reduce(m, foo_max);

 

[Beej Jorgensen]

But the same is true even if 'inline' was missing. A compiler can do
whatever he wants to when it comes to optimization, as long as the
behavior of the program is the same.

So the spec says, basically, it's a suggestion to make code that runs as
fast as possible, with a footnote to the effect that the compiler might
"use inline substitution".

In my mind the verb "to inline" has a pretty specific meaning, but in
the case of C the keyword "inline" seems to be a rather more general
definition...?

But it looks like the preprocessor must inline the macro (even if I
could somehow think of a sane way for the compiler not to) since all the
macro substitution has to take place before the final translation.

-Beej

 

[Keith Thompson]

So the spec says, basically, it's a suggestion to make code that runs as
fast as possible, with a footnote to the effect that the compiler might
"use inline substitution".

In my mind the verb "to inline" has a pretty specific meaning, but in
the case of C the keyword "inline" seems to be a rather more general
definition...?

Yes, it's very similar to the standard's treatment of the "register"
keyword.

But it looks like the preprocessor must inline the macro (even if I
could somehow think of a sane way for the compiler not to) since all the
macro substitution has to take place before the final translation.

The standard defines several translation phases which occur in
sequence, with the output of each becoming the input of the next.
Macro expansion occurs during one of the earlier phases, and is
invisible to the later phase where code is generated.

But a compiler and do anything it likes as long as the final result is
equivalent. It's free to replace a macro definition with a function
definition, and a macro invocation with a call to that function, as
long as the program's behavior is the same as if it did
straightforward macro expansion. But I doubt that any actual
compilers do this; a compiler might generate an implicit function, but
it would probably do so based on the code pattern, regardless of
whether that pattern was the result of a macro expansion or not.

 

[Ted Zlatanov]

s> How would you find the maximum of
s> (a) two numbers
s> (b) a set of numbers
s> in idiomatic C? How would you do it in idiomatic Perl?
j> That's at best an O(N log N) solution. There's an O(N) solution which
j> is even simpler; sandeep presented the basic idea for that solution
j> (badly) in his second message on this thread.

What do you mean, O(N log N)? Sorting is O(1), it's an OS function!

j> In C, sorting is built into the standard library: qsort(). It may be
j> clumsier to use, perhaps, than Perl's sort, but it's still an easier
j> solution for a C program than embedding the perl interpreter.

You must be joking!

(I was, see the date

Ted

 

[James Kuyper]

j> Ted Zlatanov wrote: ....
j> That's at best an O(N log N) solution. There's an O(N) solution which
j> is even simpler; sandeep presented the basic idea for that solution
j> (badly) in his second message on this thread.

What do you mean, O(N log N)? Sorting is O(1), it's an OS function!

I hope that statement was a continuation of your joke.

j> In C, sorting is built into the standard library: qsort(). It may be
j> clumsier to use, perhaps, than Perl's sort, but it's still an easier
j> solution for a C program than embedding the perl interpreter.

You must be joking!

No. I do joke sometimes, but this wasn't an example.

(I was, see the date

My apologies; not every message posted on that date is a joke, it's
sometimes hard to tell which are which.