Hello, John.
On Sun, 04 Dec 2011 12:46:40 -0800
"John W. Krahn" <[email protected]> wrote:
> > You should assign $marketInfo{$mkt} to a variable, or alternatively do:
> >
> > my ($start, $end) = @{$marketInfo{$mkt}}{qw(start end)};
> >
> >> my $end = $marketInfo{$mkt}->{"end"};
> >> if( $cell>= $start&& $cell<= $end)
> >> {
> >> $_mkt = $mkt;
> >> last;
> >> }
> >> }
> >
> > This loop can be more succinctly expressed using first from List::Util :
> >
> > return List::Util::first {
> > my ($start, $end) = @{$marketInfo{$_}}{qw(start end)};
> > $cell>= $start&& $cell<= $end;
> > } keys(%marketInfo);
> >
> > All that put aside, this lookup has O(N) complexity, and you can reduce it
> > to
> > O(log(N)) by creating a
>
> > sorted array of ranges that you will binary search.
> ^^^^^^^^^^^^ ^^^^^^^^^^^^^
> O( log N ) + O( log N )
>
> Or O( log 2N )
First of all, sorting an array is optimally O(N*log(N)) - not
O(log(N)). However, sorting this array is done *once* and then it is used for
all lookups, which means the total complexity should be divided by the number
of lookups.
Furthermore, O(log(2N)) = O(log(2) + log(N)) = O(log(N)).
>
> While the added efficiency MAY be faster it adds more complexity and it
> depends on the size of N and the algorithms implementing sort and search
> as to whether it will actually be faster.
That's true. But if N is very large, it's likely to be significant.
>
>
> We should forget about small efficiencies, say about 97% of the time:
> premature optimization is the root of all evil
> -- Donald Knuth
>
And ignoring asymptotic complexity is the opposite of a “small efficiency”. For
example, Visual Basic Classic implemented arrays as linked lists, which made
then practically unusable for random lookup: (i.e doing something like
myArray[i] where i is arbitrary). See:
http://tech.groups.yahoo.com/group/hackers-il/message/433
Regards,
Shlomi Fish
--
-----------------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
UNIX Fortune Cookies - http://www.shlomifish.org/humour/fortunes/
XSLT is what Chuck Norris has nightmares of.
Please reply to list if it's a mailing list post - http://shlom.in/reply .
--
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
http://learn.perl.org/