Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"
 
PerlMonks  

Re: Re: Zip Code Script

by runrig (Abbot)
on Dec 13, 2000 at 00:47 UTC ( [id://46320]=note: print w/replies, xml ) Need Help??


in reply to Re: Zip Code Script
in thread Zip Code Script

He said (and I think he meant) 5 to 10 FIVE digit zip codes. And I think he was just going to hard code those zip codes in the script. So perhaps something like:
#!/usr/local/bin/perl -l -w use strict; use CGI; my @zips = qw( 92714 92715 92716 ); my %zips; @zips{@zips} = (); my $q = CGI->new; print $q->header; print $q->start_html; if (my $zip = $q->param('zip')) { print "<br>You entered $zip"; my $valid = (exists $zips{$zip}) ? 'valid' : 'invalid'; print "<br>It is $valid"; } else { print $q->start_form; print $q->textfield(-name=>"zip"); print $q->submit("Go"); print $q->end_form; } print $q->end_html;
Update: Ok, so you can get rid of the hash and replace 'exists $zip{$zips}' with 'grep { $_ eq $zip } @zips' (see my benchmarks further down this thread), although if you were to port this to mod_perl or the like I'd stick with a hash (though it'd be defined differently) :-)

Replies are listed 'Best First'.
Re: Re: Re: Zip Code Script
by merlyn (Sage) on Dec 13, 2000 at 00:51 UTC
      Update: I can't reproduce these results, so ignore this post. As merlyn notes, a single search against an array is going to be more efficient by examining the array than building a hash. If you're going to be doing multiple searches, though, you're probably better off building a hash.

      A quick Benchmark shows the spot on my system to be at 5 elements (comparing a linear scan versus building a hash):

      1 0 wallclock secs (-0.89 usr + 0.00 sys = -0.89 CPU) 2 0 wallclock secs (-1.00 usr + 0.00 sys = -1.00 CPU) 3 -1 wallclock secs (-0.67 usr + 0.00 sys = -0.67 CPU) 4 1 wallclock secs (-0.35 usr + 0.01 sys = -0.34 CPU) 5 1 wallclock secs (-0.05 usr + 0.01 sys = -0.04 CPU) 6 0 wallclock secs ( 0.32 usr + 0.00 sys = 0.32 CPU) 7 2 wallclock secs ( 0.68 usr + 0.00 sys = 0.68 CPU) 8 2 wallclock secs ( 0.95 usr + 0.00 sys = 0.95 CPU) 9 1 wallclock secs ( 1.33 usr + 0.00 sys = 1.33 CPU) 10 3 wallclock secs ( 1.70 usr + 0.00 sys = 1.70 CPU)
      So yah, you're better off going with a linear scan unless you're going to be working with more than a handful of elements.
        Show your code. Please include the building of the hash in that code, since that was the cost I was looking at: one linear scan of an array, vs one hash lookup in a hash built from that same data.

        I'd be incredibly surprised if there was ever a time when building the hash would ever be faster. I mean, it goes back to my "how much info did you throw away at the end?" theory that I talked about here some time ago.

        -- Randal L. Schwartz, Perl hacker

      FYI, here was my test (assuming worst case of 'not found'):
      #!/usr/local/bin/perl -l -w use strict; use Benchmark; my @zips = qw( 92713 92714 92715 92716 92717 92718 92719 ); my $zip = '11111'; timethese (50000,{ HASH => \&hash_it, LINEAR => \&linear, LINEAR_GREP => \&linear_grep, }); sub hash_it { my %zips; @zips{@zips} = undef; exists $zips{$zip}; } sub linear { for (@zips) { return 1 if $_ eq $zip; } return 0; } sub linear_grep { grep { $_ eq $zip } @zips; } /usr/home/dougw/tst>./timeit Benchmark: timing 50000 iterations of HASH, LINEAR, LINEAR_GREP ... HASH: 3 wallclock secs ( 2.65 usr + 0.01 sys = 2.66 CPU) @ 18 +796.99/s (n=50000) LINEAR: 1 wallclock secs ( 1.84 usr + 0.00 sys = 1.84 CPU) @ 27 +173.91/s (n=50000) LINEAR_GREP: 0 wallclock secs ( 1.16 usr + 0.00 sys = 1.16 CPU) @ 4 +3103.45/s (n=50000)
      Update:I don't include positive searches because we don't know the probability of WebSmart's users of entering a 'found' zip code. So I assume that since there's so few (5 - 10) 'valid' zip codes, and so many possible zip codes to enter, it will probably be 'not found'. Positive searches would just make the results lean more toward the LINEAR search, I don't know how many positive searches it would take before LINEAR would be better than the LINEAR_GREP. Either is better than the HASH, though.
        Ahh, OK, now you have to include some postitive searches as well as negative searches. And I bet you still won't find an item count where building a hash is cheaper than just linear searching through the data.

        -- Randal L. Schwartz, Perl hacker

A reply falls below the community's threshold of quality. You may see it by logging in.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://46320]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others about the Monastery: (8)
As of 2024-04-23 09:52 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found