- 浏览: 891317 次
- 性别:
- 来自: 北京
文章分类
最新评论
-
wangzhen199009:
good. Thx for your sharing.
REST和认证 HMAC -
jsshizhan:
你的这个SQL有问题的
数据库中如何使用SQL查询连续数字并且统计连续个数 -
maoghj:
dddddddddddddd
mysql 更改my.cnf 慢查询日志 -
zhoutong123a:
人的贪婪无止境,只能控制,不能满足
招人心得 -
xuerThinkVickie:
...
ZeroClipboard支持IE,firefox,Chrome复制到剪贴板
二分法在IP地址查询中的应用
2007年10月03日 13时55分
本站文章如未特殊注明,均为原创,严禁转载。
前段时间做数据分析,需要大量的IP地址查询(每秒钟近万次检索),首先考虑到使用数据库。数据库大概存储几十万条IP记录,记录集如下:
+----------+----------+------------+---------+---------+--------+--------+
| ip_begin | ip_end | country_id | prov_id | city_id | isp_id | netbar |
+----------+----------+------------+---------+---------+--------+--------+
| 0 | 16777215 | 2 | 0 | 0 | 0 | 0 |
| 16777216 | 33554431 | 2 | 0 | 0 | 0 | 0 |
| 33554432 | 50331647 | 2 | 0 | 0 | 0 | 0 |
| 50331648 | 67108863 | 3 | 0 | 0 | 0 | 0 |
| 67108864 | 67829759 | 3 | 0 | 0 | 0 | 0 |
+----------+----------+------------+---------+---------+--------+--------+
这样做查询需要用到如下SQL:
<?php
$sql = 'SELECT * FROM i_m_ip WHERE ip_begin <= $client_ip AND ip_end >= $client_ip';
?>
这样的检索显然用不到索引,即使用到,MySQL查询效率也不大可能达到每秒500次以上,我做了很多并发优化,最终平均查询效率也只有每秒200次左右,实在是头痛。一开始我也有想到借鉴纯真IP库的检索方法,但是我一直对算法有抵触,也以为二分法很难,所以就没有尝试使用,直到最后没有办法了,才最终实现了二分法的IP地址检索。
从上表可以看到IP库是从0到4294967295的一个连续数值,这个数值要是拆开存储,会有几百G的数据,所以没办法使用索引也没办法哈希。最终我使用PHP将这些东东转为二进制存储,抛弃了数据库的检索。可以看到IP起止长度为一个4字节的长整型,后面的国家ID、省份ID等,可以使用2个字节的短整型来存储,总共一行数据就有18个字节,总共31万条数据,算起来也就5M的样子。具体IP库生成代码如下:
<?php
/*
IP文件格式:
3741319168 3758096383 182 0 0 0 0
3758096384 3774873599 3 0 0 0 0
3774873600 4026531839 182 0 0 0 0
4026531840 4278190079 182 0 0 0 0
4294967040 4294967295 312 0 0 0 0
*/
set_time_limit(0);
$handle = fopen('./ip.txt', 'rb');
$fp = fopen("./ip.dat", 'ab');
if ($handle) {
while (!feof($handle)) {
$buffer = fgets($handle);
$buffer = trim($buffer);
$buffer = explode("\t", $buffer);
foreach ($buffer as $key => $value) {
$buffer[$key] = (float) trim($value);
}
$str = pack('L', $buffer[0]);
$str .= pack('L', $buffer[1]);
$str .= pack('S', $buffer[2]);
$str .= pack('S', $buffer[3]);
$str .= pack('S', $buffer[4]);
$str .= pack('S', $buffer[5]);
$str .= pack('S', $buffer[6]);
fwrite($fp, $str);
}
}
?>
这样IP就按照顺序每18字节一个单位排列了,所以很容易就使用二分法来检索出IP信息:
function getip($ip, $fp) {
fseek($fp, 0);
$begin = 0;
$end = filesize('./ip.dat');
$begin_ip = implode('', unpack('L', fread($fp, 4)));
fseek($fp, $end - 14);
$end_ip = implode('', unpack('L', fread($fp, 4)));
$begin_ip = sprintf('%u', $begin_ip);
$end_ip = sprintf('%u', $end_ip);
do {
if ($end - $begin <= 18) {
fseek($fp, $begin +;
$info = array();
$info[0] = implode('', unpack('S', fread($fp, 2)));
$info[1] = implode('', unpack('S', fread($fp, 2)));
$info[2] = implode('', unpack('S', fread($fp, 2)));
$info[3] = implode('', unpack('S', fread($fp, 2)));
$info[4] = implode('', unpack('S', fread($fp, 2)));
return $info;
}
$middle_seek = ceil((($end - $begin) / 18) / 2) * 18 + $begin;
fseek($fp, $middle_seek);
$middle_ip = implode('', unpack('L', fread($fp, 4)));
$middle_ip = sprintf('%u', $middle_ip);
if ($ip >= $middle_ip) {
$begin = $middle_seek;
} else {
$end = $middle_seek;
}
} while (true);
}
以上$fp为打开ip.dat的文件句柄,由于是循环检索,所以写在函数外面,免得每次检索都要打开一次文件,30W行数据二分法最多也只需要循环7次(2^7)左右即可找到准确的IP信息。之后本来还想将ip.dat放在内存中加快检索速度,后来发现,字符串定位函数的效率,根本和文件指针的偏移定位不是在一个数量级的,所以还是放弃使用内存来存放IP库。
这个实现,使IP检索效率提高了近百倍,只是一个简单的二分法的应用,从此算法在WEB应用中不重要的观念彻底打消了。其实要实现这个,我还请教了金狐,我一开始是请他帮我生成一个纯真格式的IP库,然后用Discuz的IP查询函数来检索,不过他不肯帮我,最后造就了我的这个实践和学习。有时候,求人不如求己。
陈毅鑫 发表于 PHP程序设计
5 条评论
chris
2008年06月04日 21时46分
你好!
我参考你的文章,也作了一个ip查询的web程序
每次http访问都要fopen ip库一次
我用ab测试了下,每秒只能接受400左右的查询
是不是比你的程序差很多?能不能指点一下
深空
2008年05月12日 19时20分
嗯当时算错了,应该要18次左右。
家蚕
2008年05月12日 13时06分
30W行数据二分法最多也只需要循环7次(2^7)左右即可找到准确的IP信息
-----
7次? 不止吧
李云帆
2008年03月10日 17时00分
这个是个方法,建议再对数据文件分段,提高文件读取效率
神仙
2007年10月04日 16时31分
谁说不能hash了?
难道就非要把整个整数一起hash么
2007年10月03日 13时55分
本站文章如未特殊注明,均为原创,严禁转载。
前段时间做数据分析,需要大量的IP地址查询(每秒钟近万次检索),首先考虑到使用数据库。数据库大概存储几十万条IP记录,记录集如下:
+----------+----------+------------+---------+---------+--------+--------+
| ip_begin | ip_end | country_id | prov_id | city_id | isp_id | netbar |
+----------+----------+------------+---------+---------+--------+--------+
| 0 | 16777215 | 2 | 0 | 0 | 0 | 0 |
| 16777216 | 33554431 | 2 | 0 | 0 | 0 | 0 |
| 33554432 | 50331647 | 2 | 0 | 0 | 0 | 0 |
| 50331648 | 67108863 | 3 | 0 | 0 | 0 | 0 |
| 67108864 | 67829759 | 3 | 0 | 0 | 0 | 0 |
+----------+----------+------------+---------+---------+--------+--------+
这样做查询需要用到如下SQL:
<?php
$sql = 'SELECT * FROM i_m_ip WHERE ip_begin <= $client_ip AND ip_end >= $client_ip';
?>
这样的检索显然用不到索引,即使用到,MySQL查询效率也不大可能达到每秒500次以上,我做了很多并发优化,最终平均查询效率也只有每秒200次左右,实在是头痛。一开始我也有想到借鉴纯真IP库的检索方法,但是我一直对算法有抵触,也以为二分法很难,所以就没有尝试使用,直到最后没有办法了,才最终实现了二分法的IP地址检索。
从上表可以看到IP库是从0到4294967295的一个连续数值,这个数值要是拆开存储,会有几百G的数据,所以没办法使用索引也没办法哈希。最终我使用PHP将这些东东转为二进制存储,抛弃了数据库的检索。可以看到IP起止长度为一个4字节的长整型,后面的国家ID、省份ID等,可以使用2个字节的短整型来存储,总共一行数据就有18个字节,总共31万条数据,算起来也就5M的样子。具体IP库生成代码如下:
<?php
/*
IP文件格式:
3741319168 3758096383 182 0 0 0 0
3758096384 3774873599 3 0 0 0 0
3774873600 4026531839 182 0 0 0 0
4026531840 4278190079 182 0 0 0 0
4294967040 4294967295 312 0 0 0 0
*/
set_time_limit(0);
$handle = fopen('./ip.txt', 'rb');
$fp = fopen("./ip.dat", 'ab');
if ($handle) {
while (!feof($handle)) {
$buffer = fgets($handle);
$buffer = trim($buffer);
$buffer = explode("\t", $buffer);
foreach ($buffer as $key => $value) {
$buffer[$key] = (float) trim($value);
}
$str = pack('L', $buffer[0]);
$str .= pack('L', $buffer[1]);
$str .= pack('S', $buffer[2]);
$str .= pack('S', $buffer[3]);
$str .= pack('S', $buffer[4]);
$str .= pack('S', $buffer[5]);
$str .= pack('S', $buffer[6]);
fwrite($fp, $str);
}
}
?>
这样IP就按照顺序每18字节一个单位排列了,所以很容易就使用二分法来检索出IP信息:
function getip($ip, $fp) {
fseek($fp, 0);
$begin = 0;
$end = filesize('./ip.dat');
$begin_ip = implode('', unpack('L', fread($fp, 4)));
fseek($fp, $end - 14);
$end_ip = implode('', unpack('L', fread($fp, 4)));
$begin_ip = sprintf('%u', $begin_ip);
$end_ip = sprintf('%u', $end_ip);
do {
if ($end - $begin <= 18) {
fseek($fp, $begin +;
$info = array();
$info[0] = implode('', unpack('S', fread($fp, 2)));
$info[1] = implode('', unpack('S', fread($fp, 2)));
$info[2] = implode('', unpack('S', fread($fp, 2)));
$info[3] = implode('', unpack('S', fread($fp, 2)));
$info[4] = implode('', unpack('S', fread($fp, 2)));
return $info;
}
$middle_seek = ceil((($end - $begin) / 18) / 2) * 18 + $begin;
fseek($fp, $middle_seek);
$middle_ip = implode('', unpack('L', fread($fp, 4)));
$middle_ip = sprintf('%u', $middle_ip);
if ($ip >= $middle_ip) {
$begin = $middle_seek;
} else {
$end = $middle_seek;
}
} while (true);
}
以上$fp为打开ip.dat的文件句柄,由于是循环检索,所以写在函数外面,免得每次检索都要打开一次文件,30W行数据二分法最多也只需要循环7次(2^7)左右即可找到准确的IP信息。之后本来还想将ip.dat放在内存中加快检索速度,后来发现,字符串定位函数的效率,根本和文件指针的偏移定位不是在一个数量级的,所以还是放弃使用内存来存放IP库。
这个实现,使IP检索效率提高了近百倍,只是一个简单的二分法的应用,从此算法在WEB应用中不重要的观念彻底打消了。其实要实现这个,我还请教了金狐,我一开始是请他帮我生成一个纯真格式的IP库,然后用Discuz的IP查询函数来检索,不过他不肯帮我,最后造就了我的这个实践和学习。有时候,求人不如求己。
陈毅鑫 发表于 PHP程序设计
5 条评论
chris
2008年06月04日 21时46分
你好!
我参考你的文章,也作了一个ip查询的web程序
每次http访问都要fopen ip库一次
我用ab测试了下,每秒只能接受400左右的查询
是不是比你的程序差很多?能不能指点一下
深空
2008年05月12日 19时20分
嗯当时算错了,应该要18次左右。
家蚕
2008年05月12日 13时06分
30W行数据二分法最多也只需要循环7次(2^7)左右即可找到准确的IP信息
-----
7次? 不止吧
李云帆
2008年03月10日 17时00分
这个是个方法,建议再对数据文件分段,提高文件读取效率
神仙
2007年10月04日 16时31分
谁说不能hash了?
难道就非要把整个整数一起hash么
发表评论
-
php学习网站
2011-04-25 09:51 1063http://www.php100.com/ -
计划高效的工作
2010-11-09 10:55 930计划高效的工作 打印机为什么卡纸,所以就要有人盯着,不能卡纸 ... -
php编码规范
2010-11-03 22:12 1161B.4. 编码风格 B.4. 编码风格 ¶ B.4.1. PH ... -
一些鲜为人知的编程事实
2010-09-05 18:45 928我的程序员经历让我明 ... -
apache 日志分析软件 Weg Log Explorer
2010-09-04 10:54 983apache 日志分析软件 Weg Log Explorer -
symfony 和 thinkphp
2010-09-02 17:43 1854symfony 和 thinkphp 配置 需要 ... -
PHP中SQL注入与跨站攻击的防范
2010-07-27 16:49 2944SQL injection即SQL注入是我们每个WEB程序 ... -
接口也是为了方便团队开发上的协同工作!
2010-07-27 12:47 970接口也是为了方便团队开发上的协同工作! 解耦 // 接口定义 ... -
vi apache 日志脚本 查询统计
2010-06-25 17:15 1149cat wap.snjifen.com-access_log. ... -
chown apache:apache
2010-06-25 09:36 1144drwxr-xr-x 9 root root 4096 ... -
递归删除.svn
2010-06-24 17:17 862引用递归删除.svn -
IE在对iframe里面的页面写Cookie的时候有一些安全限制,导致读写Cookie不成功,解决办法
2010-06-22 11:28 1808IE在对iframe里面的页面写Cookie的时候有一些安全限 ... -
VI 编辑器查询删除
2010-05-14 19:20 1141:g/^,/d :g/fail/d ":g&qu ... -
crontab
2010-04-23 12:47 996#########自动执行一定要写全路径########### ... -
linux tar 解压缩
2010-04-23 09:58 898tar -zcvf test.tar.gz www/* 压缩 ... -
copy 目录
2010-04-21 17:57 844cp -r -
重启apache
2010-04-20 17:21 916/usr/local/apache2/bin/apachect ... -
配置UCHOME 出现不支持简短标签写法 short_open_tag
2010-04-20 17:07 1436gettpl('header');?>错误 把PHP. ... -
改变表结构字符集
2010-04-13 18:26 1018Alter TABLE joy_winner CONVERT ... -
mysql错误:Table XXX is marked as crashed and should be repaired[转]
2010-04-13 10:53 8489一日正在上班,朋友的QQ图标就激烈的闪亮起来,一看,原来是论坛 ...
相关推荐
前段时间做数据分析,需要大量的IP地址查询(每秒钟近万次检索),首先考虑到使用数据库。
冒泡排序以及二分法查询冒泡排序以及二分法查询冒泡排序以及二分法查询冒泡排序以及二分法查询冒泡排序以及二分法查询
#资源达人分享计划#
利用java二分法来计算最靠近值,通过二分法来遍历数据,得到想要最近值
易语言IP地址转换源码,IP地址转换,查询IP到地址,二分法确定位置,取地区文本,IP文本转整数值,十六进制到十进制,倒转十六进制文本,IP文本补位,十六进制文本到IP地址,十六进制单项补位,获得数据库数据数量,获得数据库...
题目: 编程实现找出一组数的最大值和次大值 要求: 用二分法的策略实现; (2)写出实验报告。 一、 需求分析: 1、输入要输入数组元素的个数,为数组... 3、利用二分法找出数组中的最大值和次大值; 4、输出结果;
二分法流程图1
C语言实现的二分法快速查找|二分法排序|二分法查找C#
pt1000采用二分法查询温度表C代码实现,稍加修改便可移植使用。
二分法(dichotomie) 即一分为二的方法. 设[a,b]为R的闭区间. 逐次二分法就是造出如下的区间序列([an,bn]):a0=a,b0=b,且对任一自然数n,[an+1,bn+1]或者等于[an,cn],或者等于[cn,bn],其中cn表示[an,bn]的...
语言:VC++6.0 科目:计算方法 内容:二分法
使用二分法解线性方程二分法解线性方程二分法解线性方程
二分法排序算法 C语言实现 个人爱好 希望相互学习
基于二分法的从词库中查找单词!!!!!!!!!
二分法
编写的是二分法的c程序,主要是用于数值分析实验中的二分法验证,开发环境是VC6.0.
c 二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法...
给定的表中用二分法查找指定数 给定的表中用二分法查找指定数 给定的表中用二分法查找指定数
通常多表联查并且数据大时,分页查询时,会出现查询性能问题,查分页后面的数据,时间越久。但我们可以通过判断查询数据的总数据来进行相应的查询方式,从而保证性能。