使用广度优先搜索拉取地址信息

谁说平时的开发中用不到算法?

最近产品经理发现地址库中的地址不完整,想了想,地址库从项目一开始就没有更新过…
所以需要重新更新一下地址。

本来这是一个很简单的任务,但是当我看到地址拉取的代码后,瞬间心里就没底了。
4层for循环嵌套,没有注释,代码杂乱无章,数据库还有字段并没有维护,看来这段代码已经用不了了。

那好,自己重新写吧,这次咱们就要为以后更新地址做好准备了。
首先要说明,订单中的地址信息是已经生成好的快照,不会受到地址表更新数据的影响,所以我们可以放心的更新地址信息了。

首先看看咱们数据库需要存什么数据。
id(地区id),name(地区名),parentId(父级地区id,0-为顶级),grade(地区等级:1-省 2-市 3-区(县) 4-乡(镇))。精简了一下,需要的就是这些了。

然后看看地址的接口,一共有4级地址,难怪之前嵌套了4层for循环…如果有8级地址,那岂不是要嵌套8层了…
每一级地址都是单独的接口查询,并且返回的信息是“地区名:地区id”的一个list,也就是说给出一个地址,你并不能知道这是几级地址,这就得想想grade怎么维护了。

现在我们需要拉取所有的地址,想了想,这不就是对所有地址的一次遍历吗?
所以暴力一点,咱也写个4层for循环…额不,这不是我的风格。

让我们分析一下,这其实就是一个树的层次遍历,标准的BFS模板手速题啊!

首先我们需要封装一下地址获取接口,因为数据库本身也需要维护地区等级grade,所以咱们直接根据grade判断应该调用哪个接口就好了。

再结合业务,地址可能修改,可能增加,也有可能删除,所以如何处理已删除的地址呢?要么咱们加一个del字段用于标识该地址是否被删除,在最开始设置所有地址为已删除,之后对每一个存在的地址设置为未删除,但是地址没有修改是占绝大多数的情况,所以这样可能不是太合适。那么还有一个方法,在最开始直接truncate清空表,后面只注重拉取地址就行了。

后面就是BFS模板了,先将所有的顶级地址入队,然后层次遍历每个顶级地址,并将对应的下级地址入队就行了。

伪代码大概就这样了。其实业务中还有一些转换,这里防止泄密就不展示了。

int grade = 1;
List<Address> address = getAddress(0L, grade);
Queue<Address> queue = new LinkedList<>();
queue.addAll(jdAddress);
while (!queue.isEmpty()) {
    // BFS层次遍历地址
    grade++;
    Integer size = queue.size();
    for (Integer i = 0; i < size; i++) {
        Address poll = queue.poll();

        // 根据id查询对应信息,并且做对应处理
        Address addr = getById(poll.getId());
        if (addr == null) {
            // 对应地址不存在,新增
            add(poll);
        } else {
            // 存在,如果信息有变动则修改地址
            update(poll);
        }

        // 将该地址的下级地址加入队列
        List<Address> subAddrList = getAddress(poll.getId(), grade);
        queue.addAll(subAddrList);
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据