Re: Fast lookup of ranges

satya wrote:
hi,
I have a peculiar (atleast to me) problem before my hand. There is a
big table with numeric ranges in each row. For e.g,

row 1 (1000,1050)
row 2 (4046,5683)
...

etc.

Now, given a number like 4210, I need to be able to say as fast as
possible, which row this number falls under. ( In this case row #2
because it falls in that range). The input is guaranteed to contain
numbers that MUST fall under some row in the table.

The rows are always tuples, and the first element is always less than
the second one. Further, there is NO overlap between the (ranges in
the) rows.

The following will work well for most distributions.

Let P and Q be the minimum and maximum number contained in all ranges, giving a range of R=Q-P+1 values. Chose an array length N, the larger the faster we can search. Compute a scale factor S=ceil(R/N). Fill each entry r[i] with the range number which contains the values P+i*S through P+(i+1)*S-1. If those numbers fall within multiple ranges, you can link the ranges.

Given a number x, r[i] gives the first range number to check. Advance through the ranges, starting with range r[i] until a range match is found or the range exceeds x.

The larger the array, the faster you get an answer.
--
Thad
.

Relevant Pages

  • Re: is there a compiler warning for this piece of code ?
    ... Thanks for your thoughts - I think your speculation as to the history of the ... An element of a char array cannot be NULL; ... > _address_ of the first element. ... >> Incorrect. ...
    (microsoft.public.vc.language)
  • Re: writing get_script()
    ... to the highest index. ... remove the first element from an array. ... print "$verse $script\n"; ...
    (comp.lang.perl.misc)
  • Re: Invisible Array Loop Counter?
    ... What we see here is that in the first method, the first element you tried ... and the third element became a reference ... from the array. ...
    (comp.lang.perl.misc)
  • Re: Please, I am going insane: First element access causing ArrayIndexOutOfBoundsException:0
    ... I have an array created that has ... I feed the results of the query into the array... ... same error when i try to access the first element. ... its own prepared statement and resultset and it fixed the problem. ...
    (comp.lang.java.programmer)
  • Re: Efficiency Problems in F90
    ... Atleast it is nice to know that the ... problem is related to something outside my control. ... > This makes the bounds in the actual array accesses a lot more obvious, ... > so there's no mistaking that this is a difference in the first ...
    (comp.lang.fortran)