Go Premium for a chance to win a PS4. Enter to Win

x
?
Solved

pop $AoA[x]<[y]

Posted on 2003-12-09
14
Medium Priority
?
385 Views
Last Modified: 2010-03-04
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
Comment
Question by:samj
  • 5
  • 4
  • 3
  • +1
14 Comments
 
LVL 20

Expert Comment

by:jmcg
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

by:josephfluckiger
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

by:terageek
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
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

Author Comment

by:samj
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

by:josephfluckiger
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

by:jmcg
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

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

 $i = $_;
0
 

Author Comment

by:samj
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

by:jmcg
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

by:samj
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

by:jmcg
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

by:
terageek earned 200 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

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

thanks for all the comments
0
 
LVL 1

Expert Comment

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

0

Featured Post

Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

I've just discovered very important differences between Windows an Unix formats in Perl,at least 5.xx.. MOST IMPORTANT: Use Unix file format while saving Your script. otherwise it will have ^M s or smth likely weird in the EOL, Then DO NOT use m…
Many time we need to work with multiple files all together. If its windows system then we can use some GUI based editor to accomplish our task. But what if you are on putty or have only CLI(Command Line Interface) as an option to  edit your files. I…
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…
Six Sigma Control Plans

886 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question