阶梯访问表优化

之前在 Code complete 中读到了阶梯访问表的概念 , 写出了第一版直接遍历的函数把老项目里的各种 if else 费率判断清了个干净 .

阶梯访问表适合用在区间大小不固定的情况 , 如利息根据额度变化的需求

/**
 * 阶梯访问表 l 左边界 r右边界 v 取值
 * $table = [
 * ['l' => 1500, 'r' => 1500, 'v' => '0.23'],
 * ['l' => 2000, 'r' => 2000, 'v' => '0.25'],
 * ['l' => 2500, 'r' => 2500, 'v' => '0.29'],
 * ['l' => 2700, 'r' => 5000, 'v' => '0.30'],
 * ['l' => 5500, 'r' => 7000, 'v' => '0.50'],
 * ]
 * stairStepAccess($table , 2900) ; // 0.30
 *
 *
 * @param array $table 查找表
 * @param mixed $target 查找的目标数据
 * @return mixed
 * @throws Exception
 */
function stairStepAccessIterate($table, $target)
{
    foreach ($table as $row) {
        if ($row['l'] <= $target && $target <= $row['r']) {
            return $row['v'];
        }
    }

    throw new \Exception('stairStepAccess overflow '.$target);
}

然后呢最近每天都有做一道算法题 , 自然而然的就开始思考起如何优化这个简单的函数 , 大部分情况下表都是顺序排列的, 所以使用了二分查找重写了中间部分代码

 * 阶梯访问表 l 左边界 r右边界 v 取值
 * $table = [
 * ['l' => 1500, 'r' => 1500, 'v' => '0.23'],
 * ['l' => 2000, 'r' => 2000, 'v' => '0.25'],
 * ['l' => 2500, 'r' => 2500, 'v' => '0.29'],
 * ['l' => 2700, 'r' => 5000, 'v' => '0.30'],
 * ['l' => 5500, 'r' => 7000, 'v' => '0.50'],
 * ]
 * stairStepAccess($table , 2900) ; // 0.30
 * 
 * 
 * @param array $table 查找表 
 * @param mixed $target 查找的目标数据 
 * @return mixed
 * @throws Exception
 */
function stairStepAccess($table, $target)
{
    $l = 0;
    $r = count($table) - 1;
    while ($l <= $r) {
        $mid = (int)(($l + $r) / 2);
        if ($table[$mid]['l'] <= $target && $target <= $table[$mid]['r']) {
            return $table[$mid]['v'];
        }
        if ($target > $table[$mid]['r']) {
            $l = $mid + 1;
        } else {
            $r = $mid - 1;
        }
    }
    throw new \Exception('stairStepAccess overflow value ' . $target);
}

生成了有 90 万条数据的表 , 进行 100 万次查询后的性能简单对比

完结撒花 , 算法撒浪嘿

PS : 寻求有挑战的工作机会中 , 欢迎联系

本作品采用《CC 协议》，转载必须注明作者和本文链接