in reply to Re: Perl program to look into the phone directory and in case of a match, print the name along with the number
in thread Perl program to look into the phone directory and in case of a match, print the name along with the number

Hi Corion, This is not a hw problem. This was a challenge from hackerrank and it seems to be working for all their test cases. Just that in 2 of the test cases, it gets timed out. So I was looking for a solution to optimize the code in order to run the code within the given time frame. I am a beginner and that's why the code may seem a bit messy.
  • Comment on Re^2: Perl program to look into the phone directory and in case of a match, print the name along with the number

Replies are listed 'Best First'.
Re^3: Perl program to look into the phone directory and in case of a match, print the name along with the number
by Corion (Patriarch) on Feb 12, 2017 at 12:08 UTC

    I'm not sure whether the optimization would contribute much to the overall speedup, but the following two lines do much needless work:

    $s =~ s/\s+/=/g; my @v = split( /[\[\],]/, $s ); #create an array from string $s # assign hash value pairs and insert '=' between them to create phoneb +ook my %hash = map { split( /=/, $_, $x + 1 ) } @v; entry

    Why do you convert all whitespace in $s to = and then split on = again? What use is @v?

    Also, the fasted way to do general lookups in Perl is to use a hash. In your case, the fastest data structure to look up the name from a number would be a hash that maps each number to a name:

    my %reverse_phonebook = ( 123 => 'jack', 456 => 'jill', ... );

    Building this data structure allows for quick repeated lookups of names if all you have is the number.

Re^3: Perl program to look into the phone directory ...
by haukex (Archbishop) on Feb 12, 2017 at 12:30 UTC

    Hi dk27,

    Just that in 2 of the test cases, it gets timed out.

    I see the following inefficiencies, which I already touched upon:

    • Reading the entire input into memory is unnecessary, it is enough to process the input line-by-line.
    • As Corion already pointed out, you're doing what appears to be unnecessary work on the input. Unless there are other requirements for the input format that you haven't told us about?
    • When looking up a phone number, you're searching the entire @data array twice, first with grep, then with for ( my $m = 0 ; $m <= $len1 ; $m++ ). Also, in the grep you're using a regular expression, which appears unnecessary and takes up CPU cycles since later on you're just doing an exact comparison with if ( $data[$m] eq $N[$i] ).
    • Using grep is inefficient for finding a single array element, as it searches the entire array. There would be the alternative first from the core module List::Util, which returns the first match, but if all you need is exact matches, even better would be hash lookups.

    Hope this helps,
    -- Hauke D

Re^3: Perl program to look into the phone directory and in case of a match, print the name along with the number
by Marshall (Canon) on Feb 12, 2017 at 22:36 UTC
    Hi dk27,

    I did get your code to run and produce your desired result although there is a coding mistake here:

    # assign hash value pairs and insert '=' between them to create phoneb +ook my %hash = map { split( /=/, $_, $x + 1 ) } @v; entry
    should be:
    # assign hash value pairs and insert '=' between them to create phoneb +ook entry my %hash = map { split( /=/, $_, $x + 1 ) } @v;
    Please re-run the code as a double check before posting on Monks to find these simple cut-n-paste goofs. It is easy to wind up with a goof like this (I've certainly made similar mistakes), but do the best you can. If your code runs "right off the bat", even if there are problems with it, you will tend to get much better answers. Get rid of all of the compile errors and warnings to the extent that you can. And if you can't do that, post the error messages and get advice about them.

    I don't know what kind of performance or other test case criteria are required. I can only go upon what you have posted. See my code at Re: Perl program to look into the phone directory and in case of a match, print the name along with the number.

    In terms of performance, your code besides being pretty obtuse, has many loops and loops within loops.

    Some hints:

    • Input/Output (I/O) is expensive CPU wise. Even just locating the end-of-line character(s) in an input stream takes CPU power to examine every single input character.
    • Looping is "expensive". There are loops within your code that you don't recognize as loops.Example: my @N = <STDIN>; That is a loop that builds a dynamically growing data structure for each line of input. Another example: my %hash = map { split( /=/, $_, $x + 1 ) } @v; Map is basically a short hand way of writing a foreach loop.
    Some general principles:
    • When processing an input file (or stream from STDIN), to the extent possible, try to take a definitive action based upon the information contained in that line. Do something with that information ASAP. In general making a copy of a file's data in memory, only to process that data again line by line to extract information from that data structure is a bad idea. Please note the distinction between "data" and "information". "Information" is what you get when you process the "raw data".
    • Don't save stuff in memory when it is not necessary to do so.
    I hope these comments and my code helps you learn more about Perl.