层级递归算法的优化

之前出了一篇解决无限级分类子集取值的文章：《使用BFS(广度优先搜索)算法解决无限级分类子集取值》

在使用过程中发现部门的数据一旦多起来，且层级嵌套比较深的时候，使用常规递归算法来取部门的嵌套结果集会效率很低，因为每次递归取下一级数据的时候，都会将所有数据都循环遍历一次，导致执行时间拖得很长。

假设有 1000 多个部门，部门嵌套层级达到 4 层，接口逻辑实际执行时间竟然要 26 秒，必须考虑进一步优化组装逻辑。

首先递归算法可通过层级深度进行优化，假设层级深度的字段为 depth ：

`depth` smallint unsigned NOT NULL DEFAULT '1' COMMENT '层级深度'

先组装每层的列表数据：

// 声明一个字典，储存每层的列表数据
list := make(map[int][]models.Departments, 4)

// 构造每层的迭代数据
for _, item := range departments {
    list[item.Depth] = append(works[item.Depth], item)
}

然后递归的时候只循环下一层级的数据，执行时间就可以大大缩减了：

func GetChildrenDepartments(companyId int, pid int, depth int, list map[int][]models.Departments) []Departments {
    var result []Departments
    for _, item := range list[depth] {
        if item.CompanyId != companyId {
            continue
        }

        if pid != item.Pid {
            continue
        }

        // 使用递归循环组装子集
        children := GetChildrenDepartments(companyId, item.Id, item.Depth+1, list)
        data := Departments{
            Id:       item.Id,
            Name:     item.Name,
            Children: children,
        }
        result = append(result, data)
    }

    return result
}

优化后再看执行时间，已经缩减到 12 秒了，效率提高了一倍多。

接着还可以用 go 的协程去处理子集的组装，这里可以使用 chan 去收集每个顶级部门的层级关系。

我们知道，go 的 chan 实际上是一个指针变量，意味着可以在函数内部处理中提前返回，配合调用方 for range 时可以通过关闭 chan 来控制执行流程（不关闭 chan 则 for range 永远无法停止下来，这里需要注意），所以这里还可以进一步优化。

首先组装顶级部门数据的 chan：

func getTopDepartmentsChan(list map[int][]models.Departments) <-chan Departments {
    topDepartmentsChan := make(chan Departments, len(list[1]))

    // 使用协程处理顶级部门数据组装
    go func() {
        for _, item := range list[2] {
            topDepartmentsChan <- Departments{
                Id:        item.Id,
                Name:      item.Name,
                companyId: item.CompanyId, // 这里用结构体私有属性进行缓存
                depth: 1, // 这里用结构体私有属性进行处理
            }
        }
        // 处理完成必须关闭 chan，否则使用 for range 循环该 chan 时会导致死锁
        close(topDepartmentsChan)
    }()

    return topDepartmentsChan
}

再接着通过顶级部门数据 chan 并发处理层级关系：

func getDepartmentsChan(topDepartmentsChan <-chan Departments, list map[int][]models.Departments) <-chan Departments {
    // 使用锁处理数据收集
    var wg sync.WaitGroup

    departmentsChan := make(chan Departments, len(topDepartmentsChan))

    output := func(department Departments) {
        department.Children = GetChildrenDepartments(department.companyId, department.Id, department.depth+1, list)
        departmentsChan <- department
        wg.Done()
    }

    // 使用协程处理顶级部门数据的层级关系
    for department := range topDepartmentsChan {
        wg.Add(1)
        go output(department)
    }

    // 同时注意挂起锁及关闭结果 chan，防止执行逻辑出错及外层 for range 死锁
    go func() {
        wg.Wait()
        close(departmentsChan)
    }()

    return departmentsChan
}

然后在之前构造每层的迭代数据后进行调用：

topDepartmentsChan := getTopDepartmentsChan(list)
departmentsChan := getDepartmentsChan(topDepartmentsChan, list)

for item := range departmentsChan {
    response = append(response, item)
}

// 再将 response 数据返回给调用方

看一下执行时间我们就知道，执行效率又提高了一倍。

考虑到组织架构的部门数据应该属于不常变动的数据，可将结果集丢入缓存提高接口访问效率。

但使用 go-redis 进行 set 操作时，因为结果集是结构体无法直接存入 redis ，需要进行 json 处理转换，经过阅读源码看到，在 go-redis 内，有这么一段 redis 协议的写入值的方法，里面通过判断写入值类型来进行编码。go-redis 已经支持了所有的 go 基本数据类型。

func (w *Writer) writeArg(v interface{}) error {
    switch v := v.(type) {
    case nil:
        return w.string("")
    case string:
        return w.string(v)
    case []byte:
        return w.bytes(v)
    case int:
        return w.int(int64(v))
    case int8:
        return w.int(int64(v))
    case int16:
        return w.int(int64(v))
    case int32:
        return w.int(int64(v))
    case int64:
        return w.int(v)
    case uint:
        return w.uint(uint64(v))
    case uint8:
        return w.uint(uint64(v))
    case uint16:
        return w.uint(uint64(v))
    case uint32:
        return w.uint(uint64(v))
    case uint64:
        return w.uint(v)
    case float32:
        return w.float(float64(v))
    case float64:
        return w.float(v)
    case bool:
        if v {
            return w.int(1)
        } else {
            return w.int(0)
        }
    case encoding.BinaryMarshaler:
        b, err := v.MarshalBinary()
        if err != nil {
            return err
        }
        return w.bytes(b)
    default:
        return fmt.Errorf(
            "redis: can't marshal %T (implement encoding.BinaryMarshaler)", v)
    }
}

通过上面的源码我们可以知道，可以通过实现 encoding.BinaryMarshaler 来进行结构体存储。先将结果集的类型单独定义，并增加 MarshalBinary 和 UnmarshalBinary 方法：

type DepartmentsResult []Departments

func (result *DepartmentsResult) MarshalBinary() (data []byte, err error) {
    return json.Marshal(result)
}

func (result *DepartmentsResult) UnmarshalBinary(data []byte) error {
    return json.Unmarshal(data, result)
}

最后将结果集直接丢入 set 方法里就可自动处理：

for item := range departmentsChan {
    response = append(response, item)
}

client.Set("Departments", &response, 0)

参考文献：
深入学习 Go 并发编程之通道（Channel）
go-redis 优雅存储结构体

层级递归算法的优化

发表评论