算法是许多IT公司面试时很重要的一个环节，但也有很多人抱怨实际工作中很少碰到，实用性不高。本文描述了我们公司在面试时常用的一道题目，虽然底层用了非常简单的算法，但却是具体工作中比较容易见到的场景：大规模黑名单 ip 匹配。同时用我们在安全网关中开发的例子来做些验证。
一、问题和场景
问题：有海量的 ip 网段名单，需要快速的验证某一个 ip 是否属于其中任意一个网段。
这其实是一个比较普遍的问题，以我们的安全网关为例，至少在以下场景中有需要:
场景一：单纯的黑白名单匹配
对于网关来说，黑白名单匹配是基本功能：
场景二：真实ip获取
类似的可以参考 nginx 的真实 ip 功能, 原理也比较简单，通过类似 “set_real_ip_from 192.168.1.0/24;” 的语句可以设置内部 ip 名单，这样在处理 XFF 头的时候，从后往前找，递归模式下寻找第一个不是内部 ip 的值，即真实 ip。这就回归到本文的问题上来。
场景三：流量标注
这部分功能常由后端的业务模块自行实现，我们在开发产品中希望能在请求进来的时候做一些自动标注，减轻后端的负担，比较有用的如：
以上场景描述了海量 ip 网段列表匹配的一些应用场景，还是比较容易碰到的。
二、算法描述
算法一: hashmap
绝大部分人第一反应是通过 hashmap 来做匹配，理论上可以实现(将网段拆分为独立的 ip)，但基本不可用：
所以 hashmap 的方式所以查询高效，但在实现层来说不太可行。
算法二：对网段列表进行顺序匹配
目前可以看到一些开源的实现大都采用这种方式，比如场景段落描述的 nginx 两个功能模块，可以再 accss 模块和 realip 模块发现都是将配置存储为 cidr 列表，然后逐个匹配;另外一个实现是 openresty 的 lua-resty-iputils 模块，这个代码看起来比较直观些：
开源的实现在应付绝大多数简单场景足够可用，但后面的测试可以看到，当ip网段数量上升的时候，性能还是欠缺。
算法三：二分查找
实际的算法其实很简单，二分查找即可，假设这些 ip 网段都是互不相邻的，采用类似 java 的二分查找即可，如图：
假设有 A, B, C, D 四个互不相邻的 ip 网段，每个网段可以转化为两个数字：起始ip的整型表示和终止 ip 的整型表示;比如 0.0.0.0/24 可以转化为 [0, 255]。这样四个网段转化为 8 个数字，可以进行排序，由于网段是互不相邻的，所以一定是图上这种一个 ip 段接一个 ip 段的情形。这样匹配的算法会比较简单：
所以整个算法非常简单，不过这里假设了网段之间是互不相邻的，这个很容易被忽视掉，下面做一些简单说明。
任意两个网段 A 和 B，可能有三种关系：
上图描述了任意两个网段：
所以：
因此，如果对原始数据进行一定的预处理，二分查找是安全有效的方式。
三、测试数据
最近手机出的有点多，我们也跟风跑个分：
测试一：基准测试
测试二：10000个黑名单+hashmap
测试三：10000个黑名单+lua-resty-utils 模块顺序查找
测试四：10000个黑名单+二分查找
通过测试数据，可以看到二分搜索可以达到接近于基于 hash 的性能，但内存消耗等会少很多;而简单的顺序遍历会带来数量级的性能下降。
戳这里，看该作者更多好文
已知数列的通项为1/（n∧2），求其前n项和。
1＋1/2²＋1/3²＋ … ＋1/n²→π²/6这个首先是由欧拉推出来的，要用到泰勒公式，属于大学范围－－－－－－－－－－－－－－－－－－－－－－－－－－－将sinx按泰勒级数展开：sinx＝x－x^3/3!＋x^5/5!－x^7/7!＋ …于是sinx/x＝1－x^2/3!＋x^4/5!－x^6/7!＋ …令y＝x^2，有sin√y/√y＝1－y/3!＋y^2/5!－y^3/7!＋ …而方程sinx＝0的根为0,±π,±2π,…故方程sin√y/√y＝0的根为π²,(2π)²,…即1－y/3!＋y^2/5!－y^3/7!＋…＝0的根为π²,(2π)²,…由韦达定理，常数项为1时，根的倒数和＝一次项系数的相反数即1/π²＋1/(2π)²＋…＝1/3!故1＋1/2²＋1/3²＋ … ＝π²/61/2²＋1/3²＋ …=π²/6-1
关于算法编程题（C语言实现）
char *a;//字符串改为chara[20];//存放字符串的字符数组int jie; //方程的解改为 doublejie;dy = 0;删去dy=0;两处的for(i=1;i<=z;i++)都改为for(i = 0; i < z; i++)if (a[i] == == )改为 if (a[i] == = ){z=i;改为 {dy = i;a=0;b=0; 删去a=0;b=0;fun(a,1,dy,&b,&c); 改为fun(a, 0, dy - 1, &b, &c);fun(a,dy,z,&b,&c); 改为 fun(a, dy + 1, z - 1, &b, &c);jie=(d-b)/(e-c);改为jie=((double)(d-b))/(e-c);printf(%c = %d,zm,jie);改为printf(%c = %f,zm,jie);
简单的C语言编程问题
#include stdio.h
main()
{
int i,n=0;
for(i=;i<=;i++)//循环开始，设定枚举范围-及五位整数的范围
if(i%10==6&&i%3==0)n++;//判断个位数是否为6和是否能被3整除 能的话n就加上1
printf(%d\n,n);//输出n的结果
}
这位仁兄程序很不错，我帮他注释一下
发表评论