利用有向图构建表单联动关系

目录

业务场景

在流程表单中各控件常常会有联动关系,这些关系都是由后台配置的,所以不能硬编码在程序中,需要设计一个简洁好用的关系描述模型。

下面是一组比较简单的表单控件关系的例子

  • 折扣 = 会员等级 / 100
  • 快递费 = ( 折扣 < 0.5 ) ? 20:0)
  • 折后价 = 折扣 x 原价 x 数量
  • 终价 = 快递费 + 折后价

这段关系可以用如下的有向图描述:


图 (一)

要解决的问题

如何描述表单联动关系?

一组联动关系视为一个有向图。一个表单可能存在多组联动关系,所以会产生多个有向图。每个表单控件看作是一个结点,表单控件的值即是结点的值。

每个表单控件会被抽象成一个Model,每个Model中必须要有下面这4个字段:

  • id:控件的唯一标识符
  • formula:计算表达式,如:{会员等级} / 100
  • value:表单值
  • childNodes:被联动的结点

当有向图中某个结点值被更新时,需要通知所有被联动的结点,并根据先前配置的公式更新结点值

联动的关系复杂,如何建立一个较为清晰的模型?

ExpressionNode 类:

  • 表单控件在有向图中的抽象结点,存储了id 、value、formula、childNodes等字段
  • 利用JavaScriptCore计算formula表达式的值
  • formula格式的例子:{order_price} * {order_number} + 100
  • ...

ExpressionMachine 类:

  • 根据表单所提供结点构建无向图(可能会有多个)
  • 当某个结点值更新的时候,更新所有被联动的结点
  • 将本次所有被更新的值以{id:value}的字典格式返回给表单
  • ...

一开始需要将表单中每个控件抽象成ExpressionNode放入到ExpressionMachine中建立有向图。当表单中有值更新的时候,要同步到ExpressionMachine,它会将所有被联动的结点值以字典格式返回给表单。


图 (二)

用有向图构建表单联动计算模型

建图

建图的步骤:

  • 将表单控件转换成ExpressionNode对象
  • 分析每个结点的fomula字段,分离出公式中的参数名。比如formula = {快递费} + {折后价} 分离出的参数名分别为:「快递费」,「折后价」。
  • 找到每个参数名所对应的结点指向自己。比如图(三)中 「快递费」,「折后价」指向了「终价」结点


图 (三)

深度优先遍历更新所有结点

当某个结点值发生改变时,按深度优先遍历顺序更新被关联的结点。


图 (四)

下面给出一段核心的深度优先遍历代码:

    /// 遍历更新
    private func dfs(currentNode:ExpressionNode) {
        for childNode in currentNode.childNodes {
            if isVistExpressionNode[childNode.id] == false {
                // 执行计算
                let beforeChildValue = childNode.value
                childNode.excuteFormula()
                let afterChildValue = childNode.value
                if beforeChildValue == afterChildValue {
                    // 剪枝:计算前后的值一样,不用递归遍历子结点
                    // 计算后相同s的值不用写入到结果map中
                    continue
                }
                writeToResultMap(nodeId: childNode.id, valueKey: "value", value: childNode.value!)
                isVistExpressionNode[childNode.id] = true
                // 递归遍历子结点
                dfs(currentNode: childNode)
                // chidNode 遍历结束,需要恢复状态
                isVistExpressionNode[childNode.id] = false
            }else {
                // 有回路
            }
        }
    }

遇到环路

在深度优先遍历过程中,若下一个待遍历的结点为已访问结点,说明存在环路,应停止本次递归。

更多方案

拓扑排序

图 (四)「会员等级」值改变后,「终价」结点被更新了两次,造成了性能上的浪费。将这个有向图拓扑排序后可以保证每个结点只被更新一次,但拓扑排序的前提是有向无环图,这限制了一些特殊的表单关系建立。

公式推导

理论上可以通过表达式推导出直接公式,还是用前面的例子作说明:

  • 折扣 = 会员等级 / 100
  • 快递费 = ( 折扣 < 0.5 ) ? 20:0)
  • 折后价 = 折扣 x 原价 x 数量
  • 终价 = 快递费 + 折后价

推导出:

  • 快递费 = ((会员等级 / 100) < 0.5 ) ? 20:0)
  • 折后价 = (会员等级 / 100) 原价 数量
  • 终价 = ((会员等级 / 100) < 0.5 ) ? 20:0)+ ((会员等级 / 100) 原价 数量)

优点是算法简单,缺点也很明显,重复计算太多,无法共享计算结果。若公式中有耗时函数的话,计算成本会非常高。

发表评论

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