Recursion

[Ted Zlatanov]

Most questions asked here are rejected immediately because they
don't conform to *every* *single* *fucking* *point* in the
guidelines, even if they are perfectly clear. The only ones left are
so simple, they can be answered with a perldoc reference.

I have to agree, I've been in c.l.p.misc on and off for a while, and I
find the reactions people have to most newbie posts too strong lately.
Sure, explain what they did wrong, but do it gently and in addition to
the answer. Everyone has an ego, and a new programmer is especially
vulnerable to criticism from people he may consider wiser.

Ted

 

[Richard Gration]

This is advice that a *lot* of the regulars should take. Mostly the
newer ones.

The usefulness of this group has become questionable at best. The likes
of you have made it so. Most questions asked here are rejected
immediately because they don't conform to *every* *single* *fucking*
*point* in the guidelines, even if they are perfectly clear. The only
ones left are so simple, they can be answered with a perldoc reference.
It's pathetic. In fact, I think I need to take a loooong break from this
place. I'll miss the *true* wisdom of Tad, Anno, Abigail, Randal and
some others, but this new bunch of regulars, who have no clue, but make
up for it in arrogance are ruining even their input for me.

This NG has been off my subscribe list for 6 months for *exactly* the
reasons so eloquently expressed by Bernard in this thread and in
particular the 2 quotes above. I drop in every month or so just to find
out if it has become worth reading again. Haha, the joke is still on me
(and anyone expecting help here :-( ).

In the end it was the bitterness and venom and ... well, just good old
fashioned nastiness that stopped me *being* *able* to read here. It really
did make me sad to see this once witty, friendly, tolerant and above all
*informative* NG brought so low.

To Bernard: Very well done for calling a spade a spade, and for having the
guts to. I tried but wasn't up to the task.

To the spades: Get some psychoanalysis and figure out what's eating you
before you die of cancer. No-one can possibly have that much hatred
reserved only for inexperienced usenauts/programmers ...

Rich

 

[kokolo]

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

I tried referencing like this:
........
my $l_ref=\@smaller_numbers;
my $r_ref=\@larger_numbers;

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

and it improved the peformance but it's still sorting 100000 elements in
abot 55 seconds.
Was that referencing ok?
I wonder how good QuickSort can be in Perl so it will show me how bad or
good my algorithm is.

kokolo

 

[Paul Lalli]

I tried referencing like this:
........
my $l_ref=\@smaller_numbers;
my $r_ref=\@larger_numbers;

This creates two references, one to each of your big arrays.

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

Each of these now dereferences those references, thus passing in the
entire arrays (copies of those arrays, actually!). This is not a
performance improvement.

and it improved the peformance but it's still sorting 100000 elements in
abot 55 seconds.
Was that referencing ok?

No, I don't think so. Unless I'm drastically misunderstanding your
code, you did not use the refereneces at all. Pass the references into
your subroutine, and then use those referenced arrays directly. Do not
dereference them, thereby copying the data back out of them again.
That's exactly what you're trying to avoid....

(Also, stop prepending the & on your subroutine calls. If you don't
know what that does, you don't want it)

sub qs {
my $array_ref = shift;
#do stuff to @$array_ref, or $array_ref->[0], etc.
#do not copy the elements out of @$array_ref;
#do not return @$array_ref. Just modify it in this subroutine.
}

$l_ref = \@smaller_numbers;
qs($l_ref);
# at this point, @smaller_numbers has whatever modifications
# you did to @$array_ref in the subroutine.

Paul Lalli

 

[Uri Guttman]

BE> The way you plug your work at every single even remotely relevant
BE> opportunity is as tacky as you are arrogant.

if the module fits, i promote it. even modules i don't write.

BE> A long overdue *plonk*.

be seeing ya!

uri

 

[kokolo]

sub qs {

my $array_ref = shift;
#do stuff to @$array_ref, or $array_ref->[0], etc.
#do not copy the elements out of @$array_ref;
#do not return @$array_ref. Just modify it in this subroutine.
}

$l_ref = \@smaller_numbers;
qs($l_ref);
# at this point, @smaller_numbers has whatever modifications
# you did to @$array_ref in the subroutine.

Paul Lalli

I tried like this and I didn't get it working. It seems to me, that changes
that took place in the recursive calls (marked with comments) happened only
within that particular calls.

kokolo

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

$array_ref = \@array;

$start = time();
qs($array_ref);
$finish = time();

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

sub qs {
my $sub_array_ref = shift;
my $pivot = $#$sub_array_ref;
my @smaller_numbers;
my @larger_numbers;

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

if ($sub_array_ref->[$i] <= $sub_array_ref->[$pivot]){

unshift @smaller_numbers, $sub_array_ref->[$i]
}
else {
push @larger_numbers, $sub_array_ref->[$i]
}
}

my $l_ref=\@smaller_numbers;
my $r_ref=\@larger_numbers;

if ($#$l_ref > 0){qs($l_ref)}; ## here, while it's in the subroutine it
looks ok, I put some check out printouts,
##but when it returns,
@smaller_numbers or @$l_ref are unchanged

if ($#$r_ref > 0){qs($r_ref)};

push @$l_ref,($sub_array_ref->[$pivot],@$r_ref);
}

 

[Paul Lalli]

sub qs {

my $array_ref = shift;
#do stuff to @$array_ref, or $array_ref->[0], etc.
#do not copy the elements out of @$array_ref;
#do not return @$array_ref. Just modify it in this subroutine.
}

$l_ref = \@smaller_numbers;
qs($l_ref);
# at this point, @smaller_numbers has whatever modifications
# you did to @$array_ref in the subroutine.

I tried like this

No you didn't. You did exactly what I told you not to do. You created
new arrays, and copied values from @$array_ref into them.

and I didn't get it working. It seems to me, that changes
that took place in the recursive calls (marked with comments) happened only
within that particular calls.

Because you didn't change the arrays you passed in. You created new
arrays that were valid only for the scope of that subroutine call.

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

$array_ref = \@array;

$start = time();
qs($array_ref);
$finish = time();

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

sub qs {
my $sub_array_ref = shift;
my $pivot = $#$sub_array_ref;
my @smaller_numbers;
my @larger_numbers;

Here you're declaring two brand new arrays.

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

if ($sub_array_ref->[$i] <= $sub_array_ref->[$pivot]){

unshift @smaller_numbers, $sub_array_ref->[$i]
Here...

}
else {
push @larger_numbers, $sub_array_ref->[$i]

.... and here, you're copying values from @$sub_array_ref into the two
brand new arrays.

}
}

my $l_ref=\@smaller_numbers;
my $r_ref=\@larger_numbers;

Here, you're taking references to the two new arrays.

if ($#$l_ref > 0){qs($l_ref)}; ## here, while it's in the subroutine it
looks ok, I put some check out printouts,
##but when it returns,
@smaller_numbers or @$l_ref are unchanged

Right. Because in the next iteration of the function, you did not use
@{$l_ref}. You used a brand new @smaller_numbers.

You need to change the *actual* array that is being referred to. Not
make copies.

Paul Lalli

 

[kokolo]

sub qs {
my $array_ref = shift;
#do stuff to @$array_ref, or $array_ref->[0], etc.
#do not copy the elements out of @$array_ref;
#do not return @$array_ref. Just modify it in this subroutine.
}

$l_ref = \@smaller_numbers;
qs($l_ref);
# at this point, @smaller_numbers has whatever modifications
# you did to @$array_ref in the subroutine.

I tried like this

No you didn't. You did exactly what I told you not to do. You created
new arrays, and copied values from @$array_ref into them.

But I don't know how to do it then. These two arrays (smaller, larger) are
formed within subroutine, only inthere it's decided if they exist or not.
If I understood you correctly, instead of creating new arrays I should
re-use array reference . Then push and unshift to create new sub_arrays
around the pivot are not possible? Beacuse I virtually discard the whole
array passed to the subroutine, I keep the pivot only and I create two new
arrays.
Let me ask this: I realize I misuse references but is it at all possible to
keep the concept as it is ( with the two arrays created in subroutine) and
still use references?

kokolo

 

[xhoster]

I tried referencing like this:
........
my $l_ref=\@smaller_numbers;
my $r_ref=\@larger_numbers;

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

This doesn't do anything at all. You are still doing just as much
allocating and copying and passing as you were before.

Was that referencing ok?

Well, there was nothing wrong with it per se, but it doesn't accomplish
anything. You would need to change the qs to take a reference, rather than
an array, and then pass the reference ($l_ref, not @$l_ref) into the sub
call. But that would only solve one quarter of the problem. You would
still be allocating @smaller_numbers and @larger_numbers and copying
everything into them. And you would still be taking the results of the
recursive call and copying them back into a big array to be returned, and
then copying it again in the return itself.

That said, your program does seem to be N**2, rather than NlogN, and I see
no reason that it should be. Even with all the badness built in, it should
still be NlogN, or maybe N(logN)**2, not N**2. I don't quite get it.

I wonder how good QuickSort can be in Perl so it will show me how bad or
good my algorithm is.

It can be at least 100 times faster. ("use sort '_quicksort';" give me
a built in sort that takes <1 second to sort 305780 numbers, versus 140
seconds for your sort). OK, so that may not qualify as being "in Perl",
because I'm sure much of it in C, but is available from Perl and still
uses the Perl variable access methods and such.

Xho

 

[Ted Zlatanov]

But I don't know how to do it then. These two arrays (smaller, larger) are
formed within subroutine, only inthere it's decided if they exist or not.
If I understood you correctly, instead of creating new arrays I should
re-use array reference . Then push and unshift to create new sub_arrays
around the pivot are not possible? Beacuse I virtually discard the whole
array passed to the subroutine, I keep the pivot only and I create two new
arrays.
Let me ask this: I realize I misuse references but is it at all possible to
keep the concept as it is ( with the two arrays created in subroutine) and
still use references?

No. If you create new arrays, you are not dealing with the original
data structure, so sorting those arrays won't sort the original.

Try doing this with numeric offsets:

qs(\@data, $start, $pivot, $end);

then in qs:

# untested example code
sub qs
{
my $data = shift @_;
my $start = shift @_; # start offset of range to be qsorted
my pivot = shift @_; # pivot offset of range to be qsorted
my $end = shift @_; # end offset of range to be qsorted
.... examples of usage follow ...
# get element 15 of $data
$data->[15];
....
# swap elements 12 and 22 of $data
($data->[12], $data->[22]) = ($data->[22], $data->[12]);
....
# sort a subrange from inside qs()
qs($data, $newstart, $newpivot, $newend);
....
}

I think the offsets are what you've been missing... If you just pass
a reference, you'll never know what part of it to sort, and if you
make a new array you're not sorting the original.

Ted

 

[kokolo]

That said, your program does seem to be N**2, rather than NlogN, and I see
no reason that it should be. Even with all the badness built in, it should
still be NlogN, or maybe N(logN)**2, not N**2. I don't quite get it.



It can be at least 100 times faster. ("use sort '_quicksort';" give me
a built in sort that takes <1 second to sort 305780 numbers, versus 140
seconds for your sort). OK, so that may not qualify as being "in Perl",
because I'm sure much of it in C, but is available from Perl and still
uses the Perl variable access methods and such.

I re-wrote so that the subroutine works with indexes of the original array.
100000 for 14 seconds, 305780 for 112. Very very bad.
I wonder how much it can be optimized and what are bottlenecks here:
_____________________________________________________________
print "Enter the number of elements to be sorted: \n";
chomp($size=<STDIN>);
foreach (1..$size) {push @array, int(rand(1000))}

$start=time();
qs(0,$#array);

#print "@array \n";
print "The array of $size elements Quicksorted in ",time()-$start," seconds.
\n";

sub qs{
my $left=shift;
my $right=shift;
my @smaller;
my @bigger;


for ($i=$left;$i<$right;$i++){

if ($array[$i] <= $array[$right]) {push @smaller,$array[$i]}
else {push @bigger,$array[$i]}
}

$pivot = $left + @smaller;
$array[$pivot] = $array[$right];


if ($pivot>$left){
$i=$pivot;
while (@smaller){$array[--$i]=pop @smaller};
if ($pivot-1>$left){qs($left,$pivot-1)}
}

if ($pivot<$right){
$i=$pivot;
while (@bigger){$array[++$i]=pop @bigger};
if ($pivot+1<$right){qs($pivot+1,$right)}
}

}
______________________________________________________________

kokolo

 

[kokolo]

Try doing this with numeric offsets:

qs(\@data, $start, $pivot, $end);

then in qs:

# untested example code
sub qs
{
my $data = shift @_;
my $start = shift @_; # start offset of range to be qsorted
my pivot = shift @_; # pivot offset of range to be qsorted
my $end = shift @_; # end offset of range to be qsorted
... examples of usage follow ...
# get element 15 of $data
$data->[15];
...
# swap elements 12 and 22 of $data
($data->[12], $data->[22]) = ($data->[22], $data->[12]);
...
# sort a subrange from inside qs()
qs($data, $newstart, $newpivot, $newend);
...
}

I think the offsets are what you've been missing... If you just pass
a reference, you'll never know what part of it to sort, and if you
make a new array you're not sorting the original.

Ted

I made it with sending $left and $right to the subroutine and sorting the
original array between these limits.You can take a look at the other post
for the code.
Is there still a need to send the array reference? Even in your example is
it a benefit if you work with the reference and not with the original array?

kokolo

 

[xhoster]

I made it with sending $left and $right to the subroutine and sorting the
original array between these limits.You can take a look at the other post
for the code.

Is there still a need to send the array reference?

That depends. Are you happy needing to create a separate sort routine
for every differently named array you want to sort?

Even in your example
is it a benefit if you work with the reference and not with the original
array?

Yes. Then you can tell the sort routine which array to sort.

Xho

 

[xhoster]

I re-wrote so that the subroutine works with indexes of the original
array. 100000 for 14 seconds, 305780 for 112. Very very bad.

It also gives the wrong answer!

I wonder how much it can be optimized and what are bottlenecks here:

Don't wonder, profile! Devel::SmallProf

sub qs{
my $left=shift;
my $right=shift;
my @smaller;
my @bigger;

for ($i=$left;$i<$right;$i++){

if ($array[$i] <= $array[$right]) {push @smaller,$array[$i]}
else {push @bigger,$array[$i]}
}

$pivot = $left + @smaller;
$array[$pivot] = $array[$right];

Your array now has two of whatever was in $array[$right], and none of
whatever was in $array[$pivot].

Xho

 

[kokolo]

It also gives the wrong answer!

I wonder how much it can be optimized and what are bottlenecks here:

Don't wonder, profile! Devel::SmallProf

sub qs{
my $left=shift;
my $right=shift;
my @smaller;
my @bigger;

for ($i=$left;$i<$right;$i++){

if ($array[$i] <= $array[$right]) {push @smaller,$array[$i]}
else {push @bigger,$array[$i]}
}

$pivot = $left + @smaller;
$array[$pivot] = $array[$right];

Your array now has two of whatever was in $array[$right], and none of
whatever was in $array[$pivot].

Xho

Damn, I can't get it. It is obviously wrong but it works 3-4 times out of 5
and it tricked me. It looked suspisious to me as there were too many
repeating numbers .
As for what you mentioned about $pivot, $array[$pivot] is saved either in
@smaller or @bigger.
I need to re-think it as I cannot figure out why it works if I extract

if ($pivot-1>$left){qs($left,$pivot-1)}
if ($pivot+1<$right){qs($pivot+1,$right)}

from the "if" statements and put them at the end of the sub.

kokolo

 

[anno4000]

It also gives the wrong answer!

I wonder how much it can be optimized and what are bottlenecks here:

Don't wonder, profile! Devel::SmallProf

sub qs{
my $left=shift;
my $right=shift;
my @smaller;
my @bigger;

for ($i=$left;$i<$right;$i++){

if ($array[$i] <= $array[$right]) {push @smaller,$array[$i]}
else {push @bigger,$array[$i]}
}

$pivot = $left + @smaller;
$array[$pivot] = $array[$right];

Your array now has two of whatever was in $array[$right], and none of
whatever was in $array[$pivot].

Xho

Damn, I can't get it. It is obviously wrong but it works 3-4 times out of 5
and it tricked me. It looked suspisious to me as there were too many
repeating numbers .
As for what you mentioned about $pivot, $array[$pivot] is saved either in
@smaller or @bigger.
I need to re-think it as I cannot figure out why it works if I extract

if ($pivot-1>$left){qs($left,$pivot-1)}
if ($pivot+1<$right){qs($pivot+1,$right)}

from the "if" statements and put them at the end of the sub.

I think most of all you need to understand what it means to manipulate
an array in place. You're still copying partial arrays all over the
place.

The key is to learn to swap elements of an array(ref). In Perl, the
idiom to swap the elements at $i and $k in an arrayref $l is

@$l[ $i, $k] = @$l[ $k, $i];

Instead of copying list elements back and forth, find a strategy
to move the elements into place by always swapping them with another.
Work on (parts of) the original list only, don't create "auxiliary"
arrays. Standard implementations of quicksort in other languages
also work like that.

Anno

 

[Ted Zlatanov]

I made it with sending $left and $right to the subroutine and
sorting the original array between these limits.You can take a look
at the other post for the code.

OK. I see you tried to make it work, but it's incorrect (as pointed
out by Xho and Anno). I won't add to their answers, except to point
out that perhaps Quick Sort is a little ambitious, and you should try
implementing a Bubble Sort first. QS will always be there, but if you
keep trying to solve a hard problem without progressing to that level
natureally, you may become too frustrated. BS is a good start,
especially since it involves swapping entries in an array just like
QS, except of course the algorithm is a lot simpler.

Is there still a need to send the array reference? Even in your
example is it a benefit if you work with the reference and not with
the original array?

If you have a choice, always write your functions so they can work
without awareness of the rest of your program. In the context of this
thread, write qs() so it gets all data from its parameters, including
the array it has to sort. This is the essence of reusable, modular
code (modules extend the idea, but it's still the driving force).

Ted

 

[kokolo]

I think most of all you need to understand what it means to manipulate
an array in place. You're still copying partial arrays all over the
place.

The key is to learn to swap elements of an array(ref). In Perl, the
idiom to swap the elements at $i and $k in an arrayref $l is

@$l[ $i, $k] = @$l[ $k, $i];

Instead of copying list elements back and forth, find a strategy
to move the elements into place by always swapping them with another.
Work on (parts of) the original list only, don't create "auxiliary"
arrays. Standard implementations of quicksort in other languages
also work like that.

Thanks a lot for the advice. So, creating temporary arrays by "push" and
then copying back is much slower
than direct swapping although there will be more loops and conditions?
I'll re-write it to work with in-place swapping and compare it. When I
wrote the first version, it looked very nice
and the faster it gets the uglier it is

kokolo

 

[kokolo]

OK. I see you tried to make it work, but it's incorrect (as pointed
out by Xho and Anno). I won't add to their answers, except to point
out that perhaps Quick Sort is a little ambitious, and you should try
implementing a Bubble Sort first. QS will always be there, but if you
keep trying to solve a hard problem without progressing to that level
natureally, you may become too frustrated. BS is a good start,
especially since it involves swapping entries in an array just like
QS, except of course the algorithm is a lot simpler.

Actually, I did write BS, Fast BS, BiBS,Fast BiBS, Insertion and Shell
sorts.
And by saying that I don't think I did anything special as it was just
exercising my weak Perl and all these algorithms are well known
and already written in all languages. I just wanted to do it by myself.
After that I wanted to write QS to see how much faster it is.
And it is way faster but not as much as I expected I believe mostly due to
my bad coding and approach.

But while improving it I'm learning what are bottlenecks in the program and
I realized by now
that unnecessary copying thus consuming too much memory is a major slowdown
although keeps the code nice and simple.
For instance, I'd like to know what is the slowest part of my code and how
it should be re-written.
Thanks for advices.

kokolo

 

[kokolo]

Instead of copying list elements back and forth, find a strategy
to move the elements into place by always swapping them with another.
Work on (parts of) the original list only, don't create "auxiliary"
arrays. Standard implementations of quicksort in other languages
also work like that.

Anno

I found an implementation without sub-arrays:
http://www.thescripts.com/forum/thread49795.html
changedit so it works and tried it for 99999 elements.
It did it in13 seconds while my code does it in 14.
How quick it can get at all?

kokolo