Yes, I do need all those decimal places sometimes.

Okay. There is always more than one way to skin a cat. Since you need 11 significant digits to store your 0 - 10,000 range with seven decimal places, and that's too big for an integer, partition the dataset.

If you split your floats into their integer and decimal parts, you can then scale the decimal part (multiply by 10e6) and the result fits easily into a 32-bit int. You can now store these packed in an array of strings of sorted packed ints:

@lookup = (
  "0000001/0000235/0002300/...", #(packed) 0.0000000 to 0.9999999
  "0000001/0004567/.../9999999", # 1.0000000 to 1.9999999
  ...
  "..."                          # 9999.0000000 to 9999.9999999
); # 10,000 elements
[download]

This requires 381MB per 100 million floats, allowing a typical 32-bit machine to store 500+ million in ram.

To lookup a range, you split the start value into its integer and scaled decimal parts and do a binary chop on the packed integers in the scalar indexed by the integer part. The initial bucket lookup subdivides the total number of floats into 10,000 sets making the binary search require best case (assuming 100 million evenly distributed data points), log2( 100e6/10e3 )=10 probes. Worst case, log2( 100e6 )=19 probes.

To put that into some perspective, it takes just over 5 seconds to locate and iterate 1 million "doubles" amongst 100 million:

C:\test>junk7 -N=100e6
min max: 1000.5 1100.5
1000103 values [1000.5 < N < 1100.5] located in 4.984375 seconds (0.00
+0005)/sec)
[download]

which is probably faster than you can locate the first one using most DBs. That average lookup time of 5 microseconds per element of the range, is remarkably consistant in my (unthorough and unscientific) testing.

C:\test>junk7 -N=100e6
min max: 1000.5 1100.5
1000103 values [1000.5 < N < 1100.5] located in 4.984375 seconds (0.00
+0005)/sec)

min max: 1 2
9999 values [1 < N < 2] located in 0.046875 seconds (0.000005)/sec)

min max: 9000.5 9000.75
2537 values [9000.5 < N < 9000.75] located in 0.011861 seconds (0.0000
+05)/sec)

min max: 9999.9 9999.9999999
965 values [9999.9 < N < 9999.9999999] located in 0.015625 seconds (0.
+000006)/sec)

min max: 9999.99999 9999.9999999

min max: 9998.99999 9998.9999999

min max: 9998.99999 9999.9999999
1 values [9998.99999 < N < 9999.9999999] located in 0.000000 seconds (
+0.000000)/sec)

min max: 0 1
9999 values [0 < N < 1] located in 0.046875 seconds (0.000005)/sec)

min max: 0.5 0.9999999
5002 values [0.5 < N < 0.9999999] located in 0.023772 seconds (0.00000
+5)/sec)

min max: 0.9 0.9999999
984 values [0.9 < N < 0.9999999] located in 0.000000 seconds (0.000000
+)/sec)

min max: 0 10000
99999990 values [0 < N < 10000] located in 519.562500 seconds (0.00000
+5)/sec)
min max: ^C
[download]

Let me know if you're interested in the POC code.

Per a private request, here is the proof-of-concept code used to test the idea above, with the addition of some comments:

#! perl -slw
use strict;
use Time::HiRes qw[ time ];
use Math::Random::MT qw[ rand ];

use constant MAXVALUE => 10_000;
our $N ||= 100e6;
$N /= MAXVALUE;

my @lookup;

for( 0 .. MAXVALUE -1 ) {
    $lookup[ $_ ] .= pack 'V*', sort{ $a<=>$b } map rand( 10e6 ), 1 ..
+ $N;
}

sub intAt{
    my( $bucket, $pos ) = @_;
    return 0 unless defined $lookup[ $bucket ] and length( $lookup[ $b
+ucket ] );
    unpack 'V', substr $lookup[ $bucket ], $pos*4, 4;
}

sub iterateFromTo {
    my( $start, $end ) = @_;

    ## Extract the bucket and scaled integer for the start value
    my( $startBkt, $startVal ) 
        = ( int( $start ), ( $start - int( $start ) ) * 10e6 );

    ## Skip forward to find the first bucket that
    ## contains a value greater |= to the start value (if ness.)
    ++$startBkt if length( $lookup[ $startBkt ] )
                and intAt( 
                     $startBkt, int( length( $lookup[ $startBkt ] ) /4
+ ) -1 
                    ) < $startVal;

    ## And bottle out if we moved passed the end value before finding 
+one
    return if ( intAt( $startBkt, 0 ) / 10e6 + $startBkt ) > $end;

    ## We've now located the first bucket so do a binary search to loc
+ated
    ## The lowest value greater than or equal to the start value
    my( $lo, $hi ) = ( 0, int( length( $lookup[ $startBkt ] ) / 4 ) );
    my $p;
    while( $lo < $hi ) {
        $p = $lo + int( ( $hi - $lo ) / 2 );
        my $int = intAt( $startBkt, $p );
        if( $int < $startVal ) {
            $lo = $p +1;
        }
        elsif( $int > $startVal ) {
            $hi = $p - 1;
        }
        else {
            last;
        }
    }
    ## and return an iterator that will emit that first value
    ## and all subsequent values until we reach the end value.
    return sub {
        my $int;

        do {
            ## move to the next bucket when $p moves 
            ## past the end of the current one
            ++$startBkt, $p = 0 if $p >  ( length( $lookup[ $startBkt 
+] ) / 4 );

            ## Return undef if we've moved past the last bucket
            return if $startBkt >= MAXVALUE;

            ## Grab the integer at $p (and post increment)
            $int = intAt( $startBkt, $p++ )
        } until $int; ## until we find the next value

        ## Reconsitute the float from the bucket index and scaled inte
+ger
        my $float = $startBkt + ( $int / 10e6 );

        ## undef if we've moved past the end
        return if $float > $end;

        ## else return the current float.
        return $float;
    };
}


while( 1 ) {
    printf "min max: ";
    chomp( my $input = <STDIN> );
    last unless length $input;

    my( $min, $max ) = split ' ', $input;
    my $iter = iterateFromTo( $min, $max );
    print "nothing in that range", next unless $iter;

    my $start = time;
    my $n = 0;
    ++$n while defined( $_ = $iter->() );
    my $stop = time;

    printf "$n values [$min < N < $max] located in %f seconds (%f)/sec
+)\n",
        $stop - $start, ( $stop - $start ) / $n;
}
[download]

---

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

"Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."