Recursion

[kokolo]

Hi all.

I know Perl is not the best choice for resursive function calls but I wanted
to write a quicksort in Perl.
I used Memoize module to help me do it but I still get errors like:
_____________________________________________________________________
Deep recursion on anonymous subroutine at QuickSort.pl line 40, <STDIN> line
1.
Deep recursion on subroutine "Memoize::_memoizer" at (eval 2) line 1,
<STDIN> line 1.
Deep recursion on subroutine "main::qs" at C:/Perl/lib/Memoize.pm line 269,
<STDIN> line 1.
________________________________________________________________________

This happens when the array to be sorted has more than 60k elements and only
when run under Windows.
And I'm not very happy with the speed either, I hoped it would be way
faster.

Any help? The code 's below.
Thx

----------------------------------------------------------------------------
----------------------------------------------------------------------------
-----------------
#!/usr/bin/perl -w

use strict;
use Memoize;

memoize ('qs');

my @array;
my $size;

print "Enter the number of elements to be sorted: \n";
chomp($size = <STDIN>);
foreach (1..$size) {push @array, int(rand(1000))}

my $start = time();
@array = &qs(@array);
my $finish = time();

#print "The sorted array is:\n @array \n";
print "The array of $size elements QuickSorted in ",$finish - $start,"
seconds \n";

sub qs {
my @array = @_;
my $pivot = $#array;
my @smaller_numbers;
my @larger_numbers;
my $i;

for ($i=0;$i<$pivot;$i++){

if ($array[$i] <= $array[$pivot]){

unshift @smaller_numbers, $array[$i]
}
else{
push @larger_numbers, $array[$i]
}
}

if ($#smaller_numbers > 0){@smaller_numbers = &qs(@smaller_numbers)}
if ($#larger_numbers > 0) {@larger_numbers = &qs(@larger_numbers)}

push @smaller_numbers,($array[$pivot],@larger_numbers);

return @smaller_numbers;
}

 

[Jürgen Exner]

I know Perl is not the best choice for resursive function calls

I am curious why. Mind to explain?

jue

 

[xhoster]

Hi all.

I know Perl is not the best choice for resursive function calls
Why?

but I
wanted to write a quicksort in Perl.
Why?

I used Memoize module to help me do it
Why!?

but I still get errors like:
_____________________________________________________________________
Deep recursion on anonymous subroutine at QuickSort.pl line 40, <STDIN>
line 1.
Deep recursion on subroutine "Memoize::_memoizer" at (eval 2) line 1,
<STDIN> line 1.
Deep recursion on subroutine "main::qs" at C:/Perl/lib/Memoize.pm line
269, <STDIN> line 1.
________________________________________________________________________

Those aren't errors, those are warnings. perldoc perldiag will tell
what it means, and perldoc warnings will tell you how to turn them off.

This happens when the array to be sorted has more than 60k elements and
only when run under Windows.
And I'm not very happy with the speed either, I hoped it would be way
faster.

Way faster than what? Why do you care how fast it is? Perl has a built
in sort. Use it if you care about speed.

#!/usr/bin/perl -w

use strict;
use Memoize;

memoize ('qs');

What possible good could come from this?


Xho

 

[kokolo]

Well, I asked for some help, not for a lecture :" Become a Perl expert and
only then ask a question"

Why?

----I'll correct myself: " I read there are certain problems with recursive
functions in Perl unless properly taken care of"

I don't think I took a good care.

Why?

-------Because I'm curious and I wanted to see how I'll do.

Why!?

-----Because I read it helps with recursive calls and thought I could make
use of it. It looks to me it's not needed here.

Those aren't errors, those are warnings. perldoc perldiag will tell
what it means, and perldoc warnings will tell you how to turn them off.

-----I don't want to turn them off, thank you for telling me how to use
perldiag, now I know where the warnings came from.

Way faster than what? Why do you care how fast it is? Perl has a built
in sort. Use it if you care about speed.

--- I wanted to compare it to other sorts I wrote to see how efficient it
is.

I care about making MY program better, even if there's a turbosort available

What possible good could come from this?


Xho

-- I can see now it's not needed either. Thank you, you improve my learning
curve

 

[kokolo]

Can you advise me how to do it?

kokolo

Try passing arrays and sub array by reference, not value.

BugBear

 

[David Squire]

kokolo wrote:

[top-posting corrected. Please don't do that]

Can you advise me how to do it?

See perldoc perlsub, and search for "Pass by Reference". See also
perldoc -q 'how can i pass'


DS

 

[Uri Guttman]

k> -----Because I read it helps with recursive calls and thought I could make
k> use of it. It looks to me it's not needed here.

sorting is NOT a recursive operation where the args are always the
same. memoize would help only on repeated calls with the same args but
quicksort will pass in different sets each time.
k> --- I wanted to compare it to other sorts I wrote to see how efficient it
k> is.

k> I care about making MY program better, even if there's a turbosort
k> available

use Sort::Maker. you ain't gonna write something faster unless you are
deep into sorting algorithms. and it uses perl's sort function
underneath as well. you are barking up the wrong tree to write a sort
directly in perl as perl's overhead will kill the sorting vs. the c
speed of the builtin sort.

and using a sort module MAKES your program better. if you are writing a
quicksort to learn how to do it that is another story but you don't seem
to be doing that. if you can't cleanly implement a sort from a published
algorithm why do you think you can do it better than a module or perl's
built in sort? do you even know about O(N) notation to compare sort
speeds (or other algorithms)? you might also want to read my paper on
perl sorting or the docs of sort::maker to learn more about sorting in
perl.

uri

 

[Paul Lalli]

Well, I asked for some help, not for a lecture :" Become a Perl expert and
only then ask a question"

For maximum help from this newsgroup, improve your attitude in three
ways:
1) Stop being under the impression that anyone here has an obligation
to help you, or to give you exactly what you ask for. We're all
volunteers. If you want point-by-point specific help, hire a
consultant.
2) Stop rebuking a "lecture". Lectures are good things. They teach
you. They instruct you. They make you a better programmer. If
someone offers to tell you why or how you're doing something wrong
(whether that 'something' has to do with Perl or with your methodology
or with your Usenet postings), thank them.
3) Get over yourself. No one *ever* said that asking a question is
bad, or that you need to be an expert before you ask questions.
Questions are encouraged and welcomed. Badly formed, poorly
thought-out questions, on the other hand, are justifiably ignored,
flamed, and/or lectured against. Take the advice your given, write
better questions, and you'll do fine.

You should start by reading the Posting Guidelines for this group.
They are posted here twice a week, and contain invaluable information
about how you can maximize the usefulness of this group.

Paul Lalli

 

[xhoster]

----I'll correct myself: " I read there are certain problems with
recursive functions in Perl unless properly taken care of"

Well, that is true of all languages (and I suppose of all topics, not
just recursion.)

-------Because I'm curious and I wanted to see how I'll do.

OK. But then you shouldn't be surprised if it is slow! That type
of thing is not what Perl was built for, which is why sorting is a Perl
primitive. It is something that is ubiquitous and cannot be well
implemented efficiently in pure Perl.

--- I wanted to compare it to other sorts I wrote to see how efficient it
is.

How did it do?

I care about making MY program better,

I thought your care was learn stuff, rather than get a better sort in and
of itself?

Anyway, figure out where the time is going. I like SmallProf for things
like that. It looks like you spend most of your time copying data around,
which is not surprising as every recursive level moves every element twice
(once going, into the subarrays, and once coming out, to put them back in
big array.)

Pass the subroutine an arrayref to the entire dataset, plus a left and
right pointer to the part that this particular invocation is concerned
with. Parition, pretty much like you would in C. Pass the same arrayref,
plus the new pointers, to your recursive call.

Xho

 

[kokolo]

I agree completely, I am a Perl beginner but not new to Usenet.
I just don't like arrogancy so I reacted.

 

[kokolo]

k> -----Because I read it helps with recursive calls and thought I could make
k> use of it. It looks to me it's not needed here.

sorting is NOT a recursive operation where the args are always the
same. memoize would help only on repeated calls with the same args but
quicksort will pass in different sets each time.

Got that with memoize.

k> --- I wanted to compare it to other sorts I wrote to see how efficient it
k> is.

k> I care about making MY program better, even if there's a turbosort
k> available

use Sort::Maker. you ain't gonna write something faster unless you are
deep into sorting algorithms. and it uses perl's sort function
underneath as well. you are barking up the wrong tree to write a sort
directly in perl as perl's overhead will kill the sorting vs. the c
speed of the builtin sort.

I'm well aware of it, I was writing it just to see how to do it in Perl.

and using a sort module MAKES your program better. if you are writing a
quicksort to learn how to do it that is another story but you don't seem
to be doing that. if you can't cleanly implement a sort from a published
algorithm why do you think you can do it better than a module or perl's
built in sort? do you even know about O(N) notation to compare sort
speeds (or other algorithms)? you might also want to read my paper on
perl sorting or the docs of sort::maker to learn more about sorting in
perl.

uri

I didn't have a slightest intention (that would be really ignorant!) on
writing anything that would be faster than any C implemented
quiscksort, or Perl's bulitin mergesort, or Radix sort, or any of other
C-like languages implemented O(NlogN) sorts,
I just wanted to write a quicksort in Perl and compare it to e.g.
Shellsort. I was curious how to write these sorting algorithms in Perl
as I'm learning Perl and thought algorithms would be interesting exercises.
I'm only wondering why it's not as fast as I expected it to be.
Thx,
kokolohttp://jobs.perl.org

 

[kokolo]

Thx a lot.
At this very moment i know nothing about referencing in Perl so I'll have
to learn it.
I just don't know if I want to pass the entire set to subroutine as my
concept was to keep "pivot" while "sorting" left and right side
recursively.

kokolo

 

[kokolo]

I agree completely, I am a Perl beginner but not new to Usenet. ^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^^^^
I just don't like arrogancy so I reacted.

news:[email protected]...

[snip]

And you still haven't learnt not to top-post and to quote properly
instead...


Michele
--

I admit, I suck . Hope it's temporary

kokolo

 

[Uri Guttman]

k> I'm well aware of it, I was writing it just to see how to do it in Perl.

k> I didn't have a slightest intention (that would be really ignorant!) on
k> writing anything that would be faster than any C implemented
k> quiscksort, or Perl's bulitin mergesort, or Radix sort, or any of other
k> C-like languages implemented O(NlogN) sorts,

radix is O(N) in its optimal case.

and if you know the others are average or worst case O(N log N) why are
you experimenting with them? you should read a good book on sort
algorithms anyhow. even thinking that memoize could help in a sort is a
sign you need to understand them better.

k> I just wanted to write a quicksort in Perl and compare it to e.g.
k> Shellsort. I was curious how to write these sorting algorithms in
k> Perl as I'm learning Perl and thought algorithms would be
k> interesting exercises. I'm only wondering why it's not as fast as
k> I expected it to be.

then why didn't you say this was a learning/teaching experiment? you
would have saved a lot of annoyance from many posters and readers.

you didn't show any code nor explain that you wondered why your code is
not what you expected. do you know that for small input lists, the
overhead of a sort will usually outweigh the growth curve? you need to
use some serious sized input to show the growth curves and to then
compare different algorithms. and your coding skills may not be up to
doing recursive sorts (as that is obvious by your questions) so why not
learn perl with some easier things? sort algorthms are not going to use
many constucts that you need to learn such as regexes and hashes (though
the orcish manoever does use hashes). again, i suggest you read my sort
paper and sort::maker's docs just to learn some more about sorting. and
try a different way to learn perl, sorting is too limited in its
educational scope.

uri

 

[Sherm Pendley]

if you can't cleanly implement a sort from a published
algorithm why do you think you can do it better than a module or perl's
built in sort? do you even know about O(N) notation to compare sort
speeds (or other algorithms)? you might also want to read my paper on
perl sorting or the docs of sort::maker to learn more about sorting in
perl.

Another great resource if you're studying that sort of thing is O'Reilly's
"Mastering Algorithms With Perl".

sherm--

 

[kokolo]

k> I'm well aware of it, I was writing it just to see how to do it in Perl.

k> I didn't have a slightest intention (that would be really ignorant!) on
k> writing anything that would be faster than any C implemented
k> quiscksort, or Perl's bulitin mergesort, or Radix sort, or any of other
k> C-like languages implemented O(NlogN) sorts,

radix is O(N) in its optimal case.

and if you know the others are average or worst case O(N log N) why are
you experimenting with them? you should read a good book on sort
algorithms anyhow. even thinking that memoize could help in a sort is a
sign you need to understand them better.

k> I just wanted to write a quicksort in Perl and compare it to e.g.
k> Shellsort. I was curious how to write these sorting algorithms in
k> Perl as I'm learning Perl and thought algorithms would be
k> interesting exercises. I'm only wondering why it's not as fast as
k> I expected it to be.

then why didn't you say this was a learning/teaching experiment? you
would have saved a lot of annoyance from many posters and readers.

you didn't show any code nor explain that you wondered why your code is
not what you expected. do you know that for small input lists, the
overhead of a sort will usually outweigh the growth curve? you need to
use some serious sized input to show the growth curves and to then
compare different algorithms. and your coding skills may not be up to
doing recursive sorts (as that is obvious by your questions) so why not
learn perl with some easier things? sort algorthms are not going to use
many constucts that you need to learn such as regexes and hashes (though
the orcish manoever does use hashes). again, i suggest you read my sort
paper and sort::maker's docs just to learn some more about sorting. and
try a different way to learn perl, sorting is too limited in its
educational scope.

uri

I did show the code, please take a look at the first post in the thread.
I'm not thinking I'll learn a lot of Perl by writing sorting algorithms, but
I found it an interesting challenge. After reading what the algorithm does I
tried to implement it in my weak Perl. And I did it but it's not as many
times faster than e.g. ShellSort than I expected it to be. So I asked for an
advice as the code does the job.

thx,
kokolo

 

[usenet]

I admit, I suck . Hope it's temporary

You are learning (and that's a Good Thing). At least you didn't
top-post in your reply. Now it's time to move on to the next lession --
Snip For Brevity 101. Instead of quoting an ENTIRE post in your reply,
take the time to edit the quoted content so that you only quote what is
relevant to your reply (sometimes you really must quote the entire
post, especially when the post was very terse, but usually you can trim
it quite a bit).

You see, many of us have already read the post you are responding to -
so just remind us. If you bottom-post (as you should), but quote the
ENTIRE post that you are responding to, we must slog through that
familiar content to get to your own message. And, even if we haven't
read the other post, at least we don't want to slog through material
which is irrelevant to your reply (that just confuses your reply,
making your reply less effective).

For example, if you wished to respond to the substance of this
particular post, you might quote only this tiny bit of context:

DF>Now it's time to move on to the next lession--Snip For Brevity 101

And then let 'er rip.

 

[Paul Lalli]

At no point did the OP claim that anyone here was obligated to help him.
And his tongue-in-cheek remark about not needing a lecture does not constitute
the expectation that he'll get exactly what he asked for.

I did not detect any "tongue-in-cheek"ness in the above quoted
material...

He didn't. You'd have realised that if you'd taken the time to go beyond
his smiley-qualified remark and noticed that he not only understood, but
thanked for the "lecture".

So he did. You are correct.

He did. Can't you read?

Again, you're correct. I didn't bother to read the rest of the post.

This is advice that a *lot* of the regulars should take. Mostly the newer ones.
You included. This case is a perfect example. You read the first line in the OP's
response and you thought "this is the perfect opportunity for me to be an arrogant
ass". And you took it, as you always do. Instead of looking objectively at a post you
first look for holes you can shoot the OP down for. I have seen you do it many times.

Well, half-correct this time. I read the first line in the OP's
response and thought "this is yet another arrogant poster who thinks
people here should just give him an answer and shut up."

As for my "looking for holes", you may be correct about that too. I'll
have to evaluate the way I've been looking at posts in this newsgroup
for the past year. I don't think I started out being this better and
pessimistic about questions posted. Not sure when that happened.

The OP never claimed that anyone said asking a question was bad. You're now
making up crap just so you can spew more of your arrogance at someone who
is trying to learn? That's pathetic.

The lines of the OPs response that I read insinuated that people here
don't tolerate asking questions from "newbies". I stand by my response
on that one.

That was tongue-in-cheek.

Again, I didn't detect the tongue-in-cheek nature of the response.

He accepted and thanked for the lecture in the same post! Can't you
read?

Correct again.

Where in this thread did anyone say the OP's question was badly formed?
Or poorly thought-out?

No where. That was intended to be a generic comment.

Do you just have an "arrogant ass" template that you post every time you see
a beginner's post? It seems that way.

No, I generally make it up as I go.

The OP's post clearly stated his problem and provided working (although bad)
code. Didn't you even read the post you're so troubled by?

Nope. I did not. I f***ed up in this thread, and you have called me
on it, quite deservingly. I apologize to the OP, profusely. I was out
of line in my responses.

Bernard, thank you for having the guts to tell an ass when he's being
an ass. I appreciate it. Seriously.

Paul Lalli

 

[Paul Lalli]

I don't think I started out being this better and
pessimistic about questions posted.

Well there's an unfortunate typo if I ever saw one. "bitter", not
"better".

Paul Lalli

 

[xhoster]

Thx a lot.
At this very moment i know nothing about referencing in Perl so I'll
have to learn it.

I recommend perldoc perlreftut as a starting point.

I just don't know if I want to pass the entire set to subroutine as my
concept was to keep "pivot" while "sorting" left and right side
recursively.

Well, you have hit one of those famous tradeoffs. There is no doubt that
your paritioning method is simpler, less error prone, less subtle, etc.
than one of the traditional in-place pivot methods. But it is also slower
due to all the allocation and copying going on.

Xho