Fast Int Range Lookup in Multidimensional Array?

Question

I am trying to devise a way (.NET 4.5.2) to very quickly determine if an int falls within a numeric range. Ranges do not overlap. Speed is the #1 priority for this all-in-memory operation. The below code works fine, but the actual system will have 500,000 rows sourced from a DB and I am concerned that looking for range hits in the middle of the array will incur a performance penalty. Once data is read from the DB it stays in-memory and is used as reference data in a web application.

All ideas appreciated. And thanks to https://stackoverflow.com/a/5612589/139618 for the Filter method.

// Running console app correctly shows "2288779".

static void Main( string[] args )
{
    int[,] intervals = new int[3, 3];
    intervals[0, 0] = 200;
    intervals[0, 1] = 250;
    intervals[0, 2] = 1121214;
    intervals[1, 0] = 300;
    intervals[1, 1] = 350;
    intervals[1, 2] = 2288779;
    intervals[2, 0] = 400;
    intervals[2, 1] = 450;
    intervals[2, 2] = 3300004;
    var seekIntA = 336;
    var result = Filter(intervals, u => u[0] <= seekIntA && u[1] >= seekIntA).FirstOrDefault();
    if (null != result)
    {
        Console.WriteLine(result[2]);
    }
    else
    {
        Console.WriteLine("null");
    }
}

public static IEnumerable<T[]> Filter<T>( T[,] source , Func<T[] , bool> predicate )
{
    for ( int i = 0 ; i < source.GetLength( 0 ) ; ++i )
    {
        T[] values = new T[source.GetLength( 1 )];
        for ( int j = 0 ; j < values.Length ; ++j )
        {
            values[j] = source[i , j];
        }
        if ( predicate( values ) )
        {
            yield return values;
        }
    }
}

I am open to scrapping the array idea altogether and using any other collection (lower case intentional) type to store/seek the ranges.

Thanks.

Not sure what do you mean "within a numeric range" when you have what looks like n*3 array... Is 3 more like {rangeBoundary, Data1, Data2} or somehow "range" is defined by more than 2 values? (If it is just one-dimensional search than binary search is the fastest solution for generic case). — Alexei Levenkov
– Alexei Levenkov, Commented Sep 3, 2014 at 4:29
@Alexi, the intervals[0,0] contains the lower bound of one range and intervals[0,1] contains the upper bound, intervals[0,2] contains the result-value for any number contained in the inclusive range. — Snowy
– Snowy, Commented Sep 3, 2014 at 12:30
I see. Side note: Why did you choose to use arrays than for public sample code? class/struct with 2 values (i.e. as shown in Assafss answer) would be way more readable and self-documenting while still easy to convert back to arrays if you really need it. — Alexei Levenkov
– Alexei Levenkov, Commented Sep 3, 2014 at 14:07
Probably a risk in over-thinking that using primitive types would be faster and more memory efficient than a class (or even a struct). I need this to be as super fast as possible and use the least memory, as it will be read under load by very, very many simultaneous requests. — Snowy
– Snowy, Commented Sep 4, 2014 at 14:36

Assaf · Accepted Answer · 2014-09-03 15:26:16Z

If, as it seems, your ranges are consistent you can calculate the range in O(1) time and memory. For a more generic, albeit complicated, solution:

class Range
{
    public int min { get; private set; }
    public int max { get; private set; }

    public Range(int min, int max) {
        this.min = min;
        this.max = max;
    }
}

class MinComparer : IComparer<Range>
{
    public int Compare(Range x, Range y) {
        return (x.min - y.min);
    }
}

class MaxComparer : IComparer<Range>
{
    public int Compare(Range x, Range y) {
        return (x.max - y.max);
    }
}

class Ranges
{
    private List<Range> rangesMin;
    private List<Range> rangesMax;

    private IComparer<Range> minComparer;
    private IComparer<Range> maxComparer;

    public Ranges() {
        minComparer = new MinComparer();
        maxComparer = new MaxComparer();

        rangesMin = getRanges();
        rangesMax = new List<Range>(rangesMin);

        rangesMin.Sort(minComparer);
        rangesMax.Sort(maxComparer);
    }

    public IEnumerable<Range> getSetOfPossibleRanges(int numberToSeek) {
        Range rangeToSeek = new Range(numberToSeek, numberToSeek);
        int indexMin = rangesMin.BinarySearch(rangeToSeek, minComparer);
        int indexMax = rangesMax.BinarySearch(rangeToSeek, maxComparer);

        if(indexMin < 0) {
            indexMin = ~indexMin;
        }

        if(indexMax < 0) {
            indexMax = ~indexMax;
        }

        List<Range> subMin = rangesMin.GetRange(0, indexMin);
        List<Range> subMax = rangesMax.GetRange(indexMax, rangesMax.Count - indexMax);

        return subMin.Intersect(subMax);
    }

    private List<Range> getRanges() { //get ranges from DB here }
}

I used two lists, one sorted by the lower bound of the ranges, the other sorted by upper bound. all ranges who have the seeked number are the intersection of the subsets of those lists, where the number is greater than the lower bound in the min sorted list, and is less than the upper bound in the max sorted list.

Ranges should only be initialized at application start (does costly sorting operations on initialization).

I tested this against a solution similar to your code and found it to be much faster (tested with 1M randomized ranges).

Collectives™ on Stack Overflow

Fast Int Range Lookup in Multidimensional Array?

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related