How to build multiple integer key index (fast look up object) for using between operator (val >= & val <=)

Question

Ok let me explain clearly what i want to achieve

It will be an object which will contain the below data - like an sql server table

BigInt parameter1
BigInt parameter2 
string parameter3

these parameter1 and parameter2 both will compose the index (like primary key in sql-server table)

So this object will have like 500000 records like the above And i will make fast look ups from this object like

return parameter3 where parameter1 <= value and value <= parameter2

What can be used for this ?

So far i tried these and they are slow

DataView.RowFilter = super slow
static Dictionary<Int64, KeyValuePair<Int64, string>> = slower than database query
Database query = where parameter1 & parameter2 composes primary key = slow since i need to make over 500000 query.

I also searched many questions at stackoverflow and none of them targeting between operator at integer keys. They are all multiple string key.

C# 4.0

@DavidHeffernan yes it is what i am using. But it is really really slow when compared to objects in ram memory. But could not find a proper way yet. For example if it was single key, a dictionary would be thousands time faster than querying database when you are doing 500000 query. — Furkan Gözükara
– Furkan Gözükara, Commented Dec 23, 2012 at 12:50
A good embedded DB will hold everything in RAM? Which DB are you using? — David Heffernan
– David Heffernan, Commented Dec 23, 2012 at 12:52
I am using sql-server. Oh i suppose you mean something else ? — Furkan Gözükara
– Furkan Gözükara, Commented Dec 23, 2012 at 12:54
Have you thought of some 3rd party indexing software? sphinxsearch.com must be superfast for your purposes. Either indexing your sql-server or other sources. — Max Yakimets
– Max Yakimets, Commented Dec 23, 2012 at 12:56

Max Yakimets · Accepted Answer · 2012-12-25 15:27:19Z

Quick and dirty sketch:

public class GeoIp
{
    private class GeoIpRecord
    {
        public long StartIp;
        public long EndIp;
        public string Iso;
    }

    private class GeoIpRecordComparer: IComparer<GeoIpRecord>
    {
        public int Compare(GeoIpRecord x, GeoIpRecord y)
        {
            return x.StartIp.CompareTo(y.StartIp);
        }
    }

    private List<GeoIpRecord> geoIp;
    private IComparer<GeoIpRecord> comparer;

    public GeoIp()
    {
        this.geoIp = new List<GeoIpRecord>(500000)
            {
                new GeoIpRecord { StartIp = 1, EndIp = 2, Iso = "One" },
                new GeoIpRecord { StartIp = 3, EndIp = 5, Iso = "Three" },
                new GeoIpRecord { StartIp = 6, EndIp = 6, Iso = "Six" },
                new GeoIpRecord { StartIp = 7, EndIp = 10, Iso = "Seven" },
                new GeoIpRecord { StartIp = 15, EndIp = 16, Iso = "Fifteen" },
            };
        this.comparer = new GeoIpRecordComparer();
    }

    public string GetIso(long ipValue)
    {
        int index = this.geoIp.BinarySearch(new GeoIpRecord() { StartIp = ipValue }, this.comparer);

        if (index < 0)
        {
            index = ~index - 1;
            if (index < 0)
            {
                return string.Empty;
            }
        }

        GeoIpRecord record = this.geoIp[index];

        if (record.EndIp >= ipValue)
        {
            return record.Iso;
        }
        else
        {
            return string.Empty;
        }
    }
}

And the code that confirms the solution:

GeoIp geoIp = new GeoIp();
var iso1 = geoIp.GetIso(1); // One
var iso2 = geoIp.GetIso(2); // One
var iso3 = geoIp.GetIso(3); // Three
var iso4 = geoIp.GetIso(4); // Three
var iso5 = geoIp.GetIso(5); // Three
var iso6 = geoIp.GetIso(6); // Six
var iso7 = geoIp.GetIso(7); // Seven
var iso11 = geoIp.GetIso(11); //
var iso15 = geoIp.GetIso(15); // Fifteen
var iso17 = geoIp.GetIso(17); //

The List has to be filled with an ordered data.

List.BinarySearch Method (T, IComparer)

Sergey Kalinichenko · Accepted Answer · 2012-12-25 14:54:12Z

I don't think [that] ranges overlap.

This simplifies the problem a great deal: rather than performing a two-dimensional search, you can sort your list, and perform a one-dimensional binary search, like this:

var data = new List<Tuple<long,long,string>>(TotalCount);
var cmp = new TupleComparer();
data.Sort(cmp);
long item = ... // The item to be searched
var pos = data.BinarySearch(Tuple.Create(item, long.MinValue, String.Empty), cmp);
// It appears that your data has only non-empty strings, so it is guaranteed that
// pos is going to be negative, because Item3, the last tie-breaker, will be smaller
// than anything that you may have in the table
pos = ~pos;
if (pos != data.Count && data[pos].Item1 <= item && data[pos].Item2 >= item) {
    Console.WriteLine("Found: '{0}'", data[pos].Item3);
} else {
    Console.WriteLine("Not found");
}

Here is the TupleComparer class:

class TupleComparer : IComparer<Tuple<long,long,string>> {
    public int Compare(Tuple<long,long,string> x, Tuple<long,long,string> y) {
        var res = x.Item1.CompareTo(y.Item1);
        if (res != 0) return res;
        res = x.Item2.CompareTo(y.Item2);
        return (res != 0) ? res : String.CompareOrdinal(x.Item3, y.Item3);
    }
}

Collectives™ on Stack Overflow

How to build multiple integer key index (fast look up object) for using between operator (val >= & val <=)

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related