Solved

pop $AoA[x]<[y]

Posted on 2003-12-09
14
339 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
 

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
Why You Should Analyze Threat Actor TTPs

After years of analyzing threat actor behavior, it’s become clear that at any given time there are specific tactics, techniques, and procedures (TTPs) that are particularly prevalent. By analyzing and understanding these TTPs, you can dramatically enhance your security program.

 

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 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

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

IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

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: …

757 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

Need Help in Real-Time?

Connect with top rated Experts

27 Experts available now in Live!

Get 1:1 Help Now