Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked

recursive array search

by state-o-dis-array (Hermit)
on Oct 01, 2004 at 19:31 UTC ( #395716=perlquestion: print w/replies, xml ) Need Help??
state-o-dis-array has asked for the wisdom of the Perl Monks concerning the following question:

Greetings, I am seeking a more efficient method for searching through an array. I think that my problem will be best explained with some code. Here is what I am doing:
foreach $element(@array){ foreach $compare(@array){ if ($element == $compare){next} <see if $element and $compare meet requirements> } }
Each time the script runs, the array is rewritten to up to about 1000 times with the number of elements ranging from about 200-600. Each element of the array has the form "X12:345" I am comparing $element and $compare to find a match such that if $element = X12:345, I want to find $compare = X0:344 or $compare = X24:344. Any suggestions as to how I can make this more efficient would be greatly appreciated. Thanks.

Replies are listed 'Best First'.
Re: recursive array search
by Limbic~Region (Chancellor) on Oct 01, 2004 at 19:58 UTC
    You may well be able to reduce the n^2 loops down to 2n at the expense of some memory. I won't pretend to know the relationship between the keys you are looking for but it looks like the number following the X is a multiple of 12, and the number following the : is an integer counter. It might be as simple as the following pseudo code:
    • Loop over the array as for ( 0 .. $#array ) {...}
    • push the index into a hash as push @{ $lookup{ $array[$_] } }, $_;
    • Loop back over the array as for ( @array ) {...}
    • Transform each element into the possibilities you are looking for
    • Lookup the possibilities in the hash to see if the key exists

    Cheers - L~R

      Perfect! This is exactly the type of solution I was looking for. Thanks. To All - Problem solved, thanks for the input. Sorry about the confusion, but I wasn't looking for help with determining a successful match, rather I was concerned with how to reduce my search time by getting away from
      foreach $element(@array){ foreach $compare(@array){ } }
      FYI - my processing time was cut from 12 minutes to less than two with this suggestion! Much thanks!
Re: recursive array search
by Rhys (Pilgrim) on Oct 01, 2004 at 19:46 UTC
    So if I read this correctly, you're comparing each element in the array to every other element of the array (but not to itself). So the two foreach loops make sense (mostly). The if statement you used would probably be clearer like this (IMHO):

    next if ($element eq $compare);

    ...but that's just me. For the rest of your question, I think you're going to have to be clearer on what pairs of data match. I can tell you now that it's probably going to involve something along these lines:

    ($front, $back) = split /:/, $compare; if ( $compare =~ /:$back$/ ) { # do something }

    Also, if you use for loops instead of foreach loops, you could make sure that the inner loop always starts at the same index as the outer loop (plus one), which should cut your runtime roughly in half. (Unless the a<=>b comparison is not the same as the b<=>a comparison, in which case, keep the foreach loops.)

    More info, please?


    Update: Okay, I read the code some more, and it looks like the first part has a number, and when you compare, you're looking for a multiple of that number (including zero). That's simple modulo arithmetic. You can do this to catch the first part:

    $moduloc = () = $compare =~ /X(\d+):/; # Grab the divisor. $moduloe = () = $element =~ /X(\d+):/; # Grab the other one. next if ( not $modulo ); # otherwise zero always matches. if ( not ($moduloe)%($moduloc) ) { # Do something. }

    We say, 'if not (math)' because if the first part modulo the second part comes out even, the return will be zero. Hence 'not' to make the test true.

    Could still use some more information on what should and shouldn't match, though. I'm just guessing, here.

Re: recursive array search
by stvn (Monsignor) on Oct 01, 2004 at 19:56 UTC

    Okay, at first, I didnt think I understood your question, but I am going to take one more stab at it.

    Each element of the array has the form "X12:345" I am comparing $element and $compare to find a match such that if $element = X12:345, I want to find $compare = X0:344 or $compare = X24:344. Any suggestions as to how I can make this more efficient would be greatly appreciated.

    This is the part that got me to thinking, it seemed to me that you are searching the array to find similar elements to another element, and that those relationships are not arbitrary. So, if that is correct, than you could try this:

    my %elements = map { $_ => 1 } @array; foreach my $element (@array) { # now construct copies of each $element # based on the patterns you describe my $transformed_element = transform($element); # then let the hash find the transformation print "Success!" if exists $elements{$transformed_element}; }
    You can also store all your transformations in a hash, where the key is the name of the transformation, and the value is a subroutine reference (basically a dispatch table). Then you could loop through the dispatch table and compare each transformation. Here is some code to illustrate:
    my %elements = map { $_ => 1 } @array; foreach my $element (@array) { foreach my $tranformation (keys %transformations) { my $transformed_element = $transformations{$tranformation}->($ +element); if (exists $elements{$transformed_element}) { print "Found a $tranformation of $element"; } } }

    Once again, I may be totally off on what you are asking for, but I hope this helps.

Re: recursive array search
by tmoertel (Chaplain) on Oct 01, 2004 at 20:03 UTC
    You're not giving us enough information to help you much. (Please take a look at How (Not) To Ask A Question for pointers.)

    Can you tell us, specifically, what the criteria are by which you detect whether $compare is "interesting" w.r.t. $element? Depending on the nature of the criteria, certain approaches may be dramatically better than others.

    For example, if the criteria form a commutative relation over pairings of elements within @array, you can eliminate half of your tests by testing only the elements at positions i and j for array indices i<j:

    for (my $i = 0; $i < @array; $i++) { for (my $j = $i+1; $j < @array; $j++) { my ($element, $compare) = @array[$i,$j]; # test $compare w.r.t. $element } }

    If your criteria form an ordering over the elements in your array, you might be able to perform all of your tests in linear time.


Re: recursive array search
by Zaxo (Archbishop) on Oct 01, 2004 at 20:02 UTC

    You have an error in using numeric '==' instead of alpha 'eq'.

    You appear to have an implicit rule for generating a couple of other elements from one. My best guess is that the prefix character is kept, the number formed by digits up to the colon is doubled or zero, and one is subtracted from the trailing number. From a sample of one, it's hard to tell if you mean something else.

    Your algotrithm seems to be necessarily quadratic, but it might be reduced if we knew what you were trying to do. Here's how I'd do it. Once you have $element, you can use the rule to calculate a pair of matching strings, then grep the array for matches. I'll put results into a hash of arrays, not knowing what else to do with them.

    my %hash; for my $element (@array) { my ($prefix, $first, $second) = $element =~ /^([A-Z])(\d+):(\d+)$/; my @matches = ( $prefix . '0:' . $second - 1, $prefix . $first * 2 . ':' . $second - 1); $hsh{$element} = [ grep { $_ eq $matches[0] or $_ eq $matches[1] } @array ]; }

    After Compline,

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://395716]
Approved by Arunbear
Lady_Aleena throws in the proverbial towel.

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (7)
As of 2017-04-26 06:48 GMT
Find Nodes?
    Voting Booth?
    I'm a fool:

    Results (469 votes). Check out past polls.