c# - 如何构建多个整数键索引(快速查找对象)以供在运算符 (val >= & val <=) 之间使用

Question

好吧，让我解释清楚我想要实现的目标

它将是一个包含以下数据的对象 - 就像一个 sql server 表

BigInt parameter1
BigInt parameter2 
string parameter3

这些parameter1和parameter2都会组成索引(就像sql-server表中的主键)

所以这个对象将有像上面那样的 500000 条记录我会从这个对象快速查找，比如

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

这有什么用？

到目前为止，我已经尝试过这些，但它们很慢

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.

我还在 stackoverflow 上搜索了很多问题，但没有一个是针对整数键的运算符之间的。它们都是多字符串键。

C# 4.0

Answer 1

快速粗略的草图:

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;
        }
    }
}

以及确认解决方案的代码:

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); //

List 必须填充有序数据。

List.BinarySearch Method (T, IComparer)