Prev: Perl - Get Two Decimals
Next: How to declare a variable???
From: xhoster on 30 Nov 2005 11:55
"Feyruz" <feyruzyalcin(a)hotmail.com> wrote:
> To: Perl Guru
> So you say that Perl also uses a recursive function to find the element
> with the maximum numerical value in an array ?
>
> I find this interesting. Because i was thinking that a recursive
> function would use up a lot of memory when it deals with large arrays
> if it is used for this kind of work.

If the recursion is done well (Like Anno's, unlike in your original post)
it will use a recursive call depth of only lg N. It does store a lot of
data on the recursion stack, but again if done well it only uses about N
space (1/2N + 1/4N + 1/8N ...), whereas yours uses N**2 space on the stack.
You could make it use lg N space by passing index ranges, rather than
copies of the actual array portions, around the recursive sub, but that
would require to have a 2nd wrapper to allow you to call it naturally.

>
> To: Lars Madsen
>
> You asked me why i wanted a recursive function. As i wrote in the
> beginning, it is for educational purposes.

While you can learn stuff using toy problems, I think educational purposes
are better served by learning not to do stupid things, rather than learning
how to do stupid things well. There are plenty of problems that actually
benefit from recursion, so there is no reason to force recursion onto
problems that don't benefit from it.

Xho

--
-------------------- http://NewsReader.Com/ --------------------
Usenet Newsgroup Service $9.95/Month 30GB
From: xhoster on 30 Nov 2005 11:59
"Feyruz" <feyruzyalcin(a)hotmail.com> wrote:
> Wait a second, each half takes also O(n) doesnt it? i mean , are you
> sure that it has any advantages?

Over what? Over your method? Certainly. While it makes twice as many
recursive calls as your method, it uses 460 times less memory (for N=10,
000).

Over not doing it recursively in the first place? No, no advantages.

Xho

--
-------------------- http://NewsReader.Com/ --------------------
Usenet Newsgroup Service $9.95/Month 30GB
From: Eden Cardim on 30 Nov 2005 12:26
> Do not take that wrong;
> it is not your code is broken but rather perl core's notion
> of maximum numerical value for mixed array content, or
> at least I think that is what is happening. It "appears"
> perl core sorts and places negative numbers before
> letters, for sorting order.

You're mistaken, the documentation for the built-in sort function says:
'If SUBNAME or BLOCK is omitted, "sort"s in standard string comparison
order.'
check perldoc perlfunc for more details

> Run these arrays for interesting results. Maybe you better
> know what causes differences in returns. I am guessing
> perl core has difficulties determining numerical value
> for some circumstances.

Wrong again, anno's max function compares two elements at a time in
numeric context. The problem is that the comparison will return the
right-most element if the values are equal, since 'z' is numerically
equivalent to 0, the value returned by max will depend on the position
of the elements in the $right and $left variables, $right will always
be returned when the values are equal. That means the code is broken,
and worse, I don't think it can be fixed because the code was meant to
be run on numbers.
Here are some tests for you to run:
> @Array = qw (-10 -9 -8 -7 -6 0 -5 -4 -3 -2 -1 Z Y X W);
If you sort this, you'll get W because it's the rightmost greater
element in numeric context.

> @Array = qw (Z Y X W -10 -9 -8 -7 -6 0 -5 -4 -3 -2 -1);
If you sort this, you'll get W because it's the rightmost greater
element in numeric context.

@Array = qw (-10 -9 -8 -7 -6 0 -5 -4 -3 -2 -1 W Y X Z);
Now you'll get Z
etc...

From: Purl Gurl on 30 Nov 2005 12:52
Eden Cardim wrote:

> You're mistaken
> Wrong again,

I am not interested in reading rudeness. Few readers are.

> That means the code is broken

This code written by Anno is not broken. Circumstances are
his code is receiving data not expected. Anno did not code
for the type of data I exemplified, nor is he expected to do so.

I have provided a reasonable "what if" situation which does not
reflect the quality of Anno's code; his code is very nice.

What I presented is to encourage discussion, not to provide
readers a chance to be rude.

Purl Gurl
From: Feyruz on 30 Nov 2005 13:09
people, whats going on here. I just wanted to discuss an algorithm
here, i did not want anyone to come here and be arrogant because he or
she has more experience in programming language than others. I think
some people like to fight over the internet.
Purl Gurl, why dont you also behave more civilized before calling
others rude?

Anyway, thanks Lars, Anno and Xhos for your comments on my "stupid?"
(according to Xhos) problem.
F.

First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5
Prev: Perl - Get Two Decimals
Next: How to declare a variable???