in reply to Re: Code efficiency / algorithm
in thread Code efficiency / algorithm

Given your id's are discrete rather than continuous, if the number and size of your ranges are within the bounds of sanity, building a hash lookup for every ID in the cumulative ranges it almost trivial to code and doesn't take long to build.

That'll give you O(log2 n) queries, but there's a simple way to get to O(1). I had it mostly coded up when you posted. The code is nearly identical to yours (sick minds think alike?), so I'll provide the delta.

When reading the first datafile and preparing the data structure, instead of using a hash, use an array. 

  for ( date2offset($start) .. date2offset($end) ) {
      push @{$effective[$_]}, \$data;
  }

[download]
The probe them becomes 
  my $results = $effective[date2offset($date)];    # O(1)
  if ( defined($results) {
      # @$results is an array of all matching $data
  }

[download]
I'll leave date2offset() as an exercise, other than noting that there's a non-obvious trick you can pull with it. Instead of a 1-to-1 mapping, you can do something not-quite right, like 
  sub date2offset {
      my($yyyymmdd) = @_;
      my $year = int($yyyymmdd/ 10000) - 1970;
      my $mmdd = $yyyymmdd % 10000;
      my $month = int($mmmdd / 100) - 1;
      my $day = $mmdd % 100 - 1;
      return $year * (12 * 31) + $month * 31 + $day;
  }

[download]
This is a classic time-for-space tradeoff, simplifying the calculation by assuming all months are 31 days long, resulting in 6-7 bogus offsets per year. Note that it has no effect on probe time.

Replies are listed 'Best First'.
Re: Re: Re: Code efficiency / algorithm - O(1)
by BrowserUk (Patriarch) on Jan 15, 2003 at 06:26 UTC

    Re: O(log2) and O(1). 8^?.

    That's a confused smiley. I resolve to go away and find a good reference on Big-O notation. I seem to recall not having a problem with it when I learnt it 25 or so years ago, but I definately need a refresher course now.

    Did I miss something? How do you derived a 8-digit date from an 9-digit number?

    I like the bogus days trick though.

    Re: (sick minds think alike?)

    How dare you imply that I think?

    Update: Now why do you suppose someone felt the need to downvote this node?

    • Because I didn't understand big-O?
    • Because I admitted I didn't understand big-O?
    • Because I resolved to re-learn big-O?
    • Because I questioned dws?

      (I know it wasn't dws, cos we had further discussion on the subject.)

    • Because I like the "bogus days" trick?
    • Because I made a joke at my own expense?

    You can bet your bottom dollar whomever downvoted it won't have the hutspar (sp?) to explain his or her decision.

    Examine what is said, not who speaks.

    The 7th Rule of perl club is -- pearl clubs are easily damaged. Use a diamond club instead.

[reply]

In Section Seekers of Perl Wisdom