Solved

# pop \$AoA[x]<[y]

Posted on 2003-12-09
339 Views
Hello

I have an array of arrays
ARRAY(0X1f...)ARRAY(0x...)ARRAY(0X...)...

I am trying to remove the ARRAY with the lowest value in the subarray[n]
my (\$tmp,\$i)= (0,0);
for (0 .. @AoA-1) {
if ( \$AoA [\$i][0] < \$tmp) {
\$tmp = \$AoA[\$i][0]ñ
\$i = \$_;
}
}
\$set[\$i]=undef;
but this last line will undef that element and will still be there in the array with the value undef, but I want to remove it all togeather and reduce the array as if it did not have it.

thanks
0
Question by:samj
• 5
• 4
• 3
• +1

LVL 20

Expert Comment

ID: 9908289
In general, when you hear mention of "removing an element of an array", you need to use the 'splice' operator -- unless the element to be removed is the first member of the array, where you'd use 'shift', or the last element of the array, where you'd use 'pop'.
0

LVL 1

Expert Comment

ID: 9908429
here is some code that does the trick, plus a sample 2d array. It uses a sort operator if you don't mind sorting each row of the two dimensional array.
-------------------------------
@AoA = (
[6,5,4],
[3,2,1],
[9,8,7]);

&printAoA("before sort");#this function is just to print out what we have so far

my (\$lowball,\$lowindex);
\$lowball = 1000000;
for \$i (0..\$#AoA) {
@{ \$AoA[\$i] } = sort @{\$AoA[\$i]};#sort rows of 2d array so that lowest always comes first.

if (\$AoA[\$i][0] < \$lowball){#find the first element of each array that is the lowest and keep track of it's index and value.
\$lowball = \$AoA[\$i][0];
\$lowindex =\$i;
};
}
&printAoA("after sort");
print "lowball:\$lowball,lowindex:\$lowindex\n";

@AoA = (@AoA[0..\$lowindex-1],@AoA[\$lowindex+1..\$#AoA]);#take a slice of the array, dropping the row with the lowest first value.#here is the slice operation that jmcg was talking about. This is the key trick*****

&printAoA("after sliced");

sub printAoA{
print "\$_[0]:\n";
for \$i ( 0 .. \$#AoA ) {
print "[ @{\$AoA[\$i]} ],\n";
}
print "\n";
}
----------------------------------------
0

LVL 3

Expert Comment

ID: 9908953
One more note...
You should initialize \$tmp to \$AoA[0][0].  If everthing is > 0, you will end up with \$i = 0 instead of the array with the smallest first value...

Change:
my (\$tmp,\$i)= (0,0);
to
my (\$tmp,\$i)=(\$AoA[0][0],0);
0

Author Comment

ID: 9909042
I feel like I did not explain my problem correctly,
I must not sort the inside array but use it's current first value and delete that array if it has the lowest value compairing to the first value in the rest of the sub arrays.
so
@AoA = (
[6,5,4],
[3,2,1],
[9,8,7]);
the middle array has its first value 3 so that is the subarray I need to delete without sorting it since it also could be [3,9,9] which would be the same thing for my purpose (it's first value is still 3) so delete this.

thanks again
0

LVL 1

Expert Comment

ID: 9909297
Ok, then I was making this much harder than it had to be.
I found your error, you were using \$i instead of \$_ in the inner loop. (threw me for a loop for a while)

---------------------

my (\$tmp,\$i)= (\$AoA[0][0],0);
for (0 .. \$#AoA) {
if ( \$AoA[\$_][0] < \$tmp) {
\$tmp = \$AoA[\$_][0];
\$i = \$_;
}
}
@AoA = (@AoA[0..\$i-1],@AoA[\$i+1..\$#AoA]);

-----------------------
0

LVL 20

Expert Comment

ID: 9909299
There's a difference between 'slice' and 'splice' and it is the latter that I was recommending.

Now that you've explained a bit more about what you were doing, I think I can see how I'd write it:

my ( \$lowindex, \$lowval ) = ( 0, \$AoA[0][0]);
for (1 .. \$#AoA) {
if ( \$AoA [\$_][0] < \$lowval) {
(\$lowindex, \$lowval) = (\$_, \$AoA[\$_][0]);
\$i = \$_;
}
}

# now remove the selected element

splice( @AoA, \$lowindex, 1);

This is fairly close to what you started with, but there are a couple of things to note:
When attempting to find a minimum or maximum, just take the first element as a starting point. Choosing some arbitrary value like 0 or 1000000 as a starting point will eventually be overthrown somewhere far down the road by a data set where that arbitrary value is unexpectedly larger or smaller than all of the data and you won't find the real maximum or minimum. I initialized with the index 0 values, then started the loop at 1.

In your loop, you were indexing with \$i where I believe you meant \$_.

0

LVL 20

Expert Comment

ID: 9909306
Oops. There's no longer any need for that line

\$i = \$_;
0

Author Comment

ID: 9915318
I am trying to evaluate the comments above and get the fastest code

#!/perl -w
use strict;
use warnings;
use Benchmark qw (:all);

my @AoA = (
[6,5,4],
[3,2,1],
[9,8,7]
);
cmpthese(2, {
'a' => 'del1 ( @AoA )',
'b' => 'del2 ( @AoA )',
'c' => 'del3 ( @AoA )',
});

#by josephfluckiger
sub del1 {
my @AoA = @_;
my (\$lowball, \$lowindex) = ( 1000000, 0 );
for my \$i (0..\$#AoA) {
if (\$AoA[\$i][0] < \$lowball){
\$lowball = \$AoA[\$i][0];
\$lowindex =\$i;
};
}
@AoA = (@AoA[0..\$lowindex-1],@AoA[\$lowindex+1..\$#AoA]);
return @AoA;
}

#by josephfluckiger
sub del2 {
my @AoA = @_;
my (\$tmp,\$i)= (\$AoA[0][0],0);
for (0 .. \$#AoA) {
line 36      if ( \$AoA[\$_][0] < \$tmp) {
\$tmp = \$AoA[\$_][0];
\$i = \$_;
}
}
@AoA = (@AoA[0..\$i-1],@AoA[\$i+1..\$#AoA]);
return @AoA;
}

#by jmcg
sub del3 {
my @AoA = @_;
my ( \$lowindex, \$lowval ) = ( 0, \$AoA[0][0]);
for (1 .. \$#AoA) {
if ( \$AoA [\$_][0] < \$lowval) {
(\$lowindex, \$lowval) = (\$_, \$AoA[\$_][0]);
}
}
splice( @AoA, \$lowindex, 1);
return @AoA;
}

Use of uninitialized value in numeric lt (<) at file line 36
0

LVL 20

Expert Comment

ID: 9915573
A. you should pass your array by reference. Otherwise the marshalling of the lists will be a large component of the time it takes for each iteration.

B. in order to do the comparison, you'll want to reinitialize the input array between tests, since the action of the routine reduces the array on each iteration.
0

Author Comment

ID: 9916514
[Qoute] A. you should pass your array by reference. Otherwise the marshalling of the lists will be a large component of the time it takes for each iteration.
e.g.
cmpthese(2, {
'a' => 'del1 ( \@AoA )',
'b' => 'del2 ( \@AoA )',
'c' => 'del3 ( \@AoA )',
});
then inside each sub do
my @AoA = @{\$_};

[Qoute]
B. in order to do the comparison, you'll want to reinitialize the input array between tests, since the action of the routine reduces the array on each iteration.
being only the second time to use Benchmark, how do you do this step?

thank you
0

LVL 20

Expert Comment

ID: 9917893
For the passing you have it right.

Inside the sub, I suppose you'd do:

my @AoA = @{\$_[0]};

But here we come to a hole in my knowledge of Perl. Under certain circumstances, loop variables and arguments passed to subroutines are _aliases_, so changing their value changes the original variable in the calling scope. But by doing the assignment like this in the subroutine, you are forcing a copy and the modified array is then eventually returned as the result. Passing a reference into a subroutine also gives a way to modify a variable in the calling scope, but you then have to continue to use it as a reference (although you can make a copy of a reference and still have it point to the original data) in the subroutine. So I'm not sure what the fastest method is for what you're trying to do. (I'm hoping to learn from your experiment!)

You've already used Benchmark more than I have. I'm afraid I don't know what provisions it has for reinstating the context of each expression that it repetitively calls. It would not surprise me in the end to learn that all three of these approaches have essentially identical performance. Or at least, that it's too hard to construct a test that shows much of a difference given how much has to be set up for each iteration.

0

LVL 3

Accepted Solution

terageek earned 50 total points
ID: 9923060
From your original post, it seemed that you actually wanted to remove an array from the original array of arrays.  To do that, you should pass the array by reference, but then don't copy it.  Just refer to the array by reference.  For speed, you should avoid all of the array copies that you can...

sub del {
my (\$AoA_ptr) = \$_[0];
reutrn unless (@\$AoA);     # Error check if AoA is empty, or we will crash on the splice.
my (\$index, \$lowval) = (0,\$AoA_ptr->[0][0]);
for (1 .. \$#{\$AoA_ptr}) {
if (\$AoA_ptr->[\$_][0] < \$lowval) {
(\$index, \$lowval) = (\$_, \$AoA_ptr->[\$_][0]);
}
}
splice (@\$AoA_ptr, \$index, 1);
return \$AoA_ptr;              # Should't need this really since the passed-in array was modified.
}

There will be a problem in benchmarking this since it will modify your orginal AoA each time, so after 3 itterations, AoA will be empty.

If you intend to continuously delete values from AoA, you might consider sorting AoA, then just popping the top element off each time...

sort {\$a[0] <=> \$b[0]} @AoA;
while (@AoA) {
...
unshift @AoA;
...
}

If you need to constanly add and delete elements from @AoA, you can write a sub to insert elements in order using splice, or just re-sort the array at every insertion if they are infrequent.
0

Author Comment

ID: 9934549
all what I had to do to solve this problem was
@tmp = sort { \$a->[0] <=> \$b->[0]} @tmp;
shift @tmp;

0

LVL 1

Expert Comment

ID: 9935438
2 lines of code for my 22 lines of code, not bad :)

0

## Featured Post

### Suggested Solutions

On Microsoft Windows, if  when you click or type the name of a .pl file, you get an error "is not recognized as an internal or external command, operable program or batch file", then this means you do not have the .pl file extension associated with …
A year or so back I was asked to have a play with MongoDB; within half an hour I had downloaded (http://www.mongodb.org/downloads),  installed and started the daemon, and had a console window open. After an hour or two of playing at the command …
Explain concepts important to validation of email addresses with regular expressions. Applies to most languages/tools that uses regular expressions. Consider email address RFCs: Look at HTML5 form input element (with type=email) regex pattern: T…
This video shows how to remove a single email address from the Outlook 2010 Auto Suggestion memory. NOTE: For Outlook 2016 and 2013 perform the exact same steps. Open a new email: Click the New email button in Outlook. Start typing the address: …