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/


Reply via email to