什么是自然区间？

每一个单位可以顺序访问的区间就称之为自然区间。

什么是自然区间匹配？

很多时候需要验证一个值，这个值的粒度很小或者说是异构的（从另外的模块获取的）。配置这个值是否正确，我们通常会设定一个误差允许范围，然后计算每一个范围内的点的值，来验证是否正确。

应用场景：

Client给Server发送一个验证码，验证码是通过一个用户字符串和时间计算出来的，如下：

// 伪代码
void SendCode()
{
    int userString = GetUserString(); //获取用户字符串
    int nTimes = GetTime(); // 获取当前时间ms
    
    string codeString = calcCode(userString, nTimes); //calcCode客户端服务器逻辑一样
    send(codeString); // 发送
}

Server收到这个codeString后，计算这个值是否正确，考虑到网络延时等问题，Server设定Times的允许误差在-100ms到100ms范围内，服务器有如下逻辑：

// codeString作为输入
bool verify(string codeString)
{
    int userString = GetUserString(); //获取用户字符串
    int nTimes = GetTime(); // 获取当前时间ms
    
    int deviations = 100; //允许误差ms
    for (int i = nTimes - deviation; i <= nTimes + deviation; i ++) // 可遍历的自然区间，共200次
    {
        if (codeString== calcCode(userString, i)) //calcCode客户端服务器逻辑一样
        {
            return true;
        }
    }
    return false;
}

我们可以看到每次验证都需要进行200次的calcCode函数调用，效率很低！问题很明显，我们要进行改进！

很自然的我们会想到，使用取余的办法提前将服务器和客户端的时间归一，看图：

步骤：

1，修改客户端当前时间 A = A - （A % 100），这样A挪到了A1；

2，服务器实际上有两种情况，要嘛比客户端慢B1、B2，要嘛比客户端快B3、B4；

3，将B1，B2，B3，B4的时间归一，修改服务器当前时间 B = B - （B % 100）或者 B = B - （B % 100） + 100；

这样B1=1号点或者2号点，B2等于2号点或者3号点，B3等于3号点或者4号点，B4等于4号点或者5号点。

通过上图我们可以看到要使得误差在-100ms到100ms之间，也就是A1在坐标2，4之间的所有B值都是满足条件的。

B2和B3是误差范围内允许的值。

改进代码如下：

客户端A：

// 伪代码
void SendCode()
{
    int userString = GetUserString(); //获取用户字符串
    int nTimes = GetTime(); // 获取当前时间
    
    int deviations = 100; //允许误差
    nTimes -= nTimes % deviations; // 将A点挪到A1点（将时间归一到定点）
    string codeString = calcCode(userString, nTimes); //calcCode客户端服务器逻辑一样
    send(codeString);
}

服务器B：

bool verify(string codeString)
{
    int userString = GetUserString(); //获取用户字符串
    int nTimes = GetTime(); // 获取当前时间
    
    int deviations = 100; //允许误差
    nTimes -= nTimes % deviations; //B（将时间归一到定点）
    /*  如果服务器时间慢了，B1检测1号点和2号点，B2检测2号点和3号点，B2在第二个if命中3号点
     *  如果服务器时间快了，B3检测3号点和4号点，B4检测4号点和5号点，B3在第一个if命中3号点
     *  B2和B3是对应单位坐标内的任意值，所以说误差范围内都能匹配
     *  执行次数从200次降低到2次
     */
    if (codeString== calcCode(userString, nTimes)) //calcCode客户端服务器逻辑一样
    {
        return true;
    }
    if (codeString== calcCode(userString, nTimes + deviations)) //calcCode客户端服务器逻辑一样
    {
        return true;
    }
    return false;
}

不知道说清楚没有，反正我是懂了，虽然算法很简单，但是很多时候都是自然思维敲代码，如果学会了，以后再也不用写for循环了！：） 如有问题，欢迎指出~~~

自然区间匹配算法