最新IP地址数据库 二分逼近&二分查找 高效解析800万大数据之区域分布

时间:2023-03-09 04:16:24
最新IP地址数据库 二分逼近&二分查找 高效解析800万大数据之区域分布

最新IP地址数据库  来自 qqzeng.com

利用二分逼近(bisection method) ,每秒500多万, 比较高效!

多语言API解析Dat 导入数据库脚本
https://github.com/zengzhan/qqzeng-ip

最新IP地址数据库 二分逼近&二分查找 高效解析800万大数据之区域分布
最新IP地址数据库 二分逼近&二分查找 高效解析800万大数据之区域分布

最新IP地址数据库 二分逼近&二分查找 高效解析800万大数据之区域分布

原来的顺序查找算法 效率比较低

 readonly string ipBinaryFilePath = "qqzengipdb.dat";
readonly byte[] dataBuffer, indexBuffer;
readonly uint[] index = new uint[];
readonly int dataLength;
public IpLocation()
{
try
{
FileInfo file = new FileInfo(ipBinaryFilePath);
dataBuffer = new byte[file.Length];
using (var fin = new FileStream(file.FullName, FileMode.Open, FileAccess.Read))
{
fin.Read(dataBuffer, , dataBuffer.Length);
}
var offset_len = BytesToLong(dataBuffer[], dataBuffer[], dataBuffer[], dataBuffer[]); //Big Endian
indexBuffer = new byte[offset_len];
Array.Copy(dataBuffer, , indexBuffer, , offset_len);
dataLength = (int)offset_len;
for (int loop = ; loop < ; loop++)
{
//索引 四字节 LITTLE_ENDIAN
index[loop] = BytesToLong(indexBuffer[loop * + ], indexBuffer[loop * + ], indexBuffer[loop * + ], indexBuffer[loop * ]);
}
}
catch { }
} public string[] Find(string ip)
{
var ips = ip.Split('.');
uint ip_prefix = uint.Parse(ips[]);
uint find_uint32 = BytesToLong(byte.Parse(ips[]), byte.Parse(ips[]), byte.Parse(ips[]), byte.Parse(ips[]));//BIG_ENDIAN // LITTLE_ENDIAN
int max_len = ;
int resultOffset =-;
int resultLegth =-; uint start = index[ip_prefix] * + ;
if (ip_prefix != )
{
max_len = (int)index[ip_prefix + ] * + ;
}
else
{
max_len = (int)index[] * + +;
} for (; start < max_len; start += )
{
// 前四位 结束ip 后三位 偏移 最后一位 内容长度
uint endipNum = BytesToLong(indexBuffer[start + ], indexBuffer[start + ], indexBuffer[start + ], indexBuffer[start + ]);//BIG_ENDIAN
if (endipNum >= find_uint32)
{
resultOffset =(int) BytesToLong((byte), indexBuffer[start + ], indexBuffer[start + ], indexBuffer[start + ]);//LITTLE_ENDIAN
resultLegth = 0xFF & indexBuffer[start + ];// 长度
break;
}
}
if (resultOffset==-||resultLegth==-)
{
return new string[] {"N/A"};
}
var areaBytes = new byte[resultLegth];
Array.Copy(dataBuffer, dataLength + resultOffset - , areaBytes, , resultLegth);
return Encoding.UTF8.GetString(areaBytes).Split(' ');
} private static uint BytesToLong(byte a, byte b, byte c, byte d)
{ return ((uint)a << ) | ((uint)b << ) | ((uint)c << ) | (uint)d;
} public static string long2IP(long longIP)
{
StringBuilder sb = new StringBuilder("");
sb.Append(longIP >> );
sb.Append(".");
//将高8位置0,然后右移16为 sb.Append((longIP & 0x00FFFFFF) >> );
sb.Append("."); sb.Append((longIP & 0x0000FFFF) >> );
sb.Append(".");
sb.Append((longIP & 0x000000FF)); return sb.ToString(); }
  
}

改进版 采用二分逼近 算法(类似二分查找,但又不同)  性能提升很大

  public string[] Find(string ip)
{
var ips = ip.Split('.');
uint ip_prefix = uint.Parse(ips[]);
uint find_uint32 = BytesToLong(byte.Parse(ips[]), byte.Parse(ips[]), byte.Parse(ips[]), byte.Parse(ips[]));//BIG_ENDIAN
uint max_len = ;
int resultOffset = -;
int resultLegth = -;
uint start = index[ip_prefix];
if (ip_prefix != )
{
max_len = index[ip_prefix + ];
}
else
{
max_len = index[];
}
uint num = max_len - start;
uint my_index = BinarySearch(start, max_len, find_uint32);
start = my_index * + ;
resultOffset = (int)BytesToLong((byte), indexBuffer[start + ], indexBuffer[start + ], indexBuffer[start + ]);//LITTLE_ENDIAN
resultLegth = 0xFF & indexBuffer[start + ];// 长度 if (resultOffset == - || resultLegth == -)
{
return new string[] { "N/A" };
}
var areaBytes = new byte[resultLegth];
Array.Copy(dataBuffer, dataLength + resultOffset - , areaBytes, , resultLegth);
return Encoding.UTF8.GetString(areaBytes).Split(' ');
} /// <summary>
/// 二分逼近
/// </summary>
public uint BinarySearch(uint low, uint high, uint k)
{
uint M = ;
while (low <= high)
{
uint mid = (low + high) / ;
uint endipNum = GetStartIp(mid);
if (endipNum >= k)
{
M = mid; //mid有可能是解
high = mid - ;
}
else
low = mid + ;
}
return M;
}

有了上面高效算法  解析出来800多万数据 也很快   再用一个简单的ling 统计一下即可

  var cn_result= from r in list
group r by r.cn into g
select new { key = g.Key, cnt = g.Count() };

 800多万数据  统计组图  

最新IP地址数据库 二分逼近&二分查找 高效解析800万大数据之区域分布

最新IP地址数据库 二分逼近&二分查找 高效解析800万大数据之区域分布

最新IP地址数据库 二分逼近&二分查找 高效解析800万大数据之区域分布

最新IP地址数据库 二分逼近&二分查找 高效解析800万大数据之区域分布

最新IP地址数据库 二分逼近&二分查找 高效解析800万大数据之区域分布

最新IP地址数据库 二分逼近&二分查找 高效解析800万大数据之区域分布

微信公众号:qqzeng-ip

最新IP地址数据库 二分逼近&二分查找 高效解析800万大数据之区域分布

IP地址数据库: 最新IP地址数据库 二分逼近&二分查找 高效解析800万大数据之区域分布