Rafaqat has asked for the wisdom of the Perl Monks concerning the following question:

Dear all,
I've a function which searches a given number from an array and returns the result.

Function:

1.    sub checkNumber($)
2.    {
3.            my ($l_number) =  @_;
4.            my $l_status;<br>
5.            my @matches= grep { /$l_number/ } @numbers;
6.            if  (@matches) {
7.                    $l_status="TRUE";
8.            }
9.            else {
10.                    $l_status="FALSE";
11.            }
12.            return $l_status;
13.    }

[download]

The Way I call it:

1.    $check=checkNumber($num1);

[download]
The array has at least 20K elements. This piece of code is taking up almost 100% of the CUP cycles (Dual Xeon). Would somebody please suggest some alternative solution.

Thanks in Advance

Replies are listed 'Best First'.
Re: Very slow array searching
by dws (Chancellor) on Jul 29, 2003 at 07:16 UTC
    I've a function which searches a given number from an array and returns the result.

    What you have is a function that tells whether one or more entries in the array contain a given substring. That's not the same as searching for a number.

    Consider the difference between 

      my @matches = grep { /$l_number/ } @numbers;

    [download]
    and 
      my @matches = grep { $_ == $l_number } @numbers;

    [download]
    The former will match "11" when you're searching for a "1". That latter won't.

    That problem aside, have you considered an alternate data structure? If you're going to be doing multiple probes for numbers, you might be better served by building a hash keyed by the number in each @number. Then, determining if a given number exists in the "array" becomes 

      if ( $number{$l_number} ) { ...

    [download]
    Also, returning the strings "TRUE" or "FALSE" makes writing 
      if ( checknumber(47) ) { ...

    [download]
    problematic, because the function will always return a non-false value. Return 0 (for false) and 1 (for true), and you'll save yourself a lot of grief later.

[reply]
[d/l]
[select]
Re: Very slow array searching
by PodMaster (Abbot) on Jul 29, 2003 at 06:49 UTC
    Yes. Exit as soon as your find a match. 
    sub yoda {
  for my $roy ( @foys ){
     return 'yes match ' if  $roy =~ /yoda/ ;
  }
  return 'no match';
}

    [download]

    MJD says "you can't just make shit up and expect the computer to know what you mean, retardo!"
    I run a Win32 PPM repository for perl 5.6.x and 5.8.x -- I take requests (README).
    ** The third rule of perl club is a statement of fact: pod is sexy.

[reply]
[d/l]
Re: Very slow array searching
by pzbagel (Chaplain) on Jul 29, 2003 at 07:11 UTC

    If you are building this array and if the elements will definately be unique, then put it in a hash! A hash does lookups much faster than any array search method. That is, as long as you don't care about maintaining the order of the input items.

    Next best thing would be if the array was sorted somehow, you can implement a Binary Search to search the array. This would be tons faster than your current method which is an Iterative search.

[reply]
Re: Very slow array searching
by BrowserUk (Patriarch) on Jul 29, 2003 at 08:06 UTC

    You might find the bsearch() sub in Re: Re: Re: Re: Re: Find a number in a list closest to a target useful if you can't use a hash.

    Examine what is said, not who speaks.
    "Efficiency is intelligent laziness." -David Dunham
    "When I'm working on a problem, I never think about beauty. I think only how to solve the problem. But when I have finished, if the solution is not beautiful, I know it is wrong." -Richard Buckminster Fuller
[reply]
[d/l]
Re: Very slow array searching
by dragonchild (Archbishop) on Jul 29, 2003 at 12:35 UTC
    A lot depends on what you're trying to do. If you intend on populating once, then searching multiple times, I'd use a hash. If you intend on doing other stuff, I might be less inclined to search as much. What else do you do with this thing?

    A good rule of thumb is that your needs drive the data structure. In all but the most pathologically simple tasks, there is more than one data structure that can be used. Just because you chose array first doesn't mean that array should be used now, especially if the program has changed to meet changing requirements.

    ------
    We are the carpenters and bricklayers of the Information Age.

    Don't go borrowing trouble. For programmers, this means Worry only about what you need to implement.

    Please remember that I'm crufty and crochety. All opinions are purely mine and all code is untested, unless otherwise specified.

[reply]

Back to Seekers of Perl Wisdom