3

わかりました、私が達成したいことを明確に説明させてください

以下のデータを含むオブジェクトになります-SQLサーバーテーブルのように

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

4

2 に答える 2

1

範囲が重複しているとは思いません。

これにより、問題が大幅に単純化されます。2 次元検索を実行するのではなく、次のようにリストを並べ替えて、1 次元二分検索を実行できます。

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

TupleComparerクラスは次のとおりです。

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);
    }
}
于 2012-12-25T14:54:12.903 に答える
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 メソッド (T、IComparer)

于 2012-12-25T15:27:19.790 に答える