树结构在计算表达式解析上的应用（设计统计组件）

前言

大部分公司都存在数据统计的业务逻辑，而随着业务的不断发展，数据量的增加，统计指标的增加导致原先的统计代码的复杂度也会迅速上升。如果没有良好的组织和维护，往往会出现修改难（代码间耦合严重），项目中有大量重复代码，比如很多个地方都需要某个统计数据，开发人员直接复制粘贴代码，还有就是性能N+1问题。所以在编写这种统计逻辑时，应考虑以下几点：

1. 基础数据如何获取（从数据库读取，从缓存中读取，从外部系统获取）
2. 多个数据源如何组织计算（比如计算某个员工的绩效排名，最终的得分一定是多个维度的）
3. 天然要求考虑性能问题，避免N+1查询
4. 统计逻辑应独立，可组合，可复用（比如销售的订单金额这一指标在多个统计项中都要使用，那就应尽量复用统一）

这里我们尝试设计一个统计框架

模块儿区分

其实统计指标数据粗略可分为两种

1. 基础指标
2. 计算指标

我们统一称呼 指标 为 Field

基础指标

基础指标就是数据源是独立的，比如获取当前销售部门下在职销售的本月订单金额。这个信息来源于Order表。能直接获取到的而不设计比较，计算，条件判断等。

select sales_id, sum(amount) from orders where sales_id in (xxxxx) group by sales_id

比如我们设计一个基础类：Field 表示是一个指标

class Field
  attr_accessor :obj_ids
  
  # obj_ids 表示统计维度，比如：我要统计一批人的数据，那这里的obj_ids就是这些人的id
  def initialize(obj_ids)
    self.obj_ids = Array(obj_ids)
  end
  
  # 子类需要具体的数据统计方法，这里约定返回的结构必须是Hash，同时Key为obj_id, value为对应的统计值
  def value_hash
  end
end

# 统计订单金额
class OrderAmountField < Field
  # key: obj_id
  # value: 对应统计的数据
  def value_hash
    # 这里可以是从数据库获取，缓存获取，接口获取，总之返回结构是固定的
    {
      1 => 300,
      2 => 100,
      3 => 200,
    }
  end
end

# 使用
OrderAmountField.new(sales_ids).value_hash

这里我们按照最基础的形式去表达，实际使用中要考虑多种场景，例如缓存等

计算指标

计算指标就是指在某个数据源的基础上去处理，比如 A指标 + B指标 - C指标 = 当前指标，我们以销售人员提成来说，销售人员自身等级和提成率是挂钩的，相同的销售金额，给的提成是不同的。那这里就是计算指标，即依赖其他指标，并其上进行运算得出的值。

比如上面我们已经有了订单金额的Field统计了，我们还需要两个指标：销售的提成率，销售的实际提成金额
而销售的实际提成金额 = 每个销售的订单金额 * 每个销售的提成率

# 销售提成率
class SalesCommissionRateField < Field
  # key: obj_id 销售
  # value: 每个销售的提成率
  def value_hash
    {
      1 => 0.3,
      2 => 0.2,
      3 => 0.1,
    }
  end
end

# 销售提成金额
class SalesCommissionAmountField < Field
  self.formula = OrderAmountField * SalesCommissionRateField
end

# 使用
SalesCommissionAmountField.new(sales_ids).value_hash

{
  1 => 300 * 0.3,
  2 => 100 * 0.2,
  3 => 200 * 0.1,
}

我们先不看具体是怎么实现的，但是上面的 OrderAmountField * SalesCommissionRateField 就能很优雅的体现当前指标是如何计算的。这里我们的计算指标是依赖于 两个基础指标的。
我们甚至可以再往前一步，比如 计算指标 = 另一个计算指标 + 基础指标 - 计算指标，比如：

# 年底奖金
class YearEndBonusField < Field
  # 年终奖 = 提成金额 + 销售员基础一个月工资
  self.formula = SalesCommissionAmountField + SalesOneMonthSalaryField
end

从这里我们就能看出，formula这个表达式是非常灵活的，既可以处理基础指标，也可以处理计算指标，这里的计算指标又是来源于其他计算统计获取的。甚至这个表达式你也可以去操作数字，比如：

# 年底奖金
class YearEndBonusField < Field
  # 老板红包
  BOSS_RED_ENVELOPE = 5000

  # 年终奖 = 提成金额 + 销售员基础一个月工资
  self.formula = SalesCommissionAmountField + SalesOneMonthSalaryField + BOSS_RED_ENVELOPE
end

在实际场景中肯定还有其他运算符，比如基础的 + - * / 求和 最大值 最小值等等。这里演示只用最基本的操作符

疑问梳理

1. 为什么这里的类能使用 + - * / 甚至更多的操作符？

这里是因为Ruby语言的灵活性，+ - * / 比赛关键字，而是一个个方法，
比如：SalesCommissionAmountField + SalesOneMonthSalaryField => SalesCommissionAmountField.+(SalesOneMonthSalaryField)

我们可以重写Field的类方法，比如我们控制 + - * / 另一个类时是怎么操作的。同时这里有一个非常关键的点：即使我们重写了这些操作符的实现方式，但是操作符的优先级仍然存在，比如说：
AField + BField * CField = BField * CField + AField ，甚至如果你可以写成
(AField + BField) * CField 这些都是在Ruby底层实现好的，我们只需要关注两个指标是怎么加起来的

class CalculateMethod
  def calculate
    raise NotImplementedError
  end
end

class Add < CalculateMethod
  attr_accessor :args

  def initialize(args)
    @args = args
  end

  def calculate
    args.sum
  end
end

module Formulable
  def s_add(*args)
    FormulaNode.build(Add, *args)
  end
end

module Calculatable
  include Formulable

  # Field + Field
  # 将表达式转成一个计算节点
  def +(other)
    s_add(self, other)
  end
end

2. self.formula = SalesCommissionAmountField + SalesOneMonthSalaryField + BOSS_RED_ENVELOPE 这种结构是怎么解析并存储的？

如果写过算法题，应该了解过如果写一个 数字计算表达式的解析，这里有什么双栈法，后缀表达式，树结构之类的解析。这里实际上就是采用的树结构来表达的，具体原因，因为我们处理最基本的操作符运算，还可以实现很多特定的运算方式，比如取最大值，取最小值，取平均值，或运算，与运算等等。树结构能很好的扩展，并且对节点进行操作。

YearEndBonusField 的实际结构应该是=
(OrderAmountField * SalesCommissionRateField) + SalesOneMonthSalaryField + BOSS_RED_ENVELOPE

||_ +
|    |_ BOSS_RED_ENVELOPE
|    |_ SalesOneMonthSalaryField
|    |_ *
|        |_ OrderAmountField
|        |_ SalesCommissionRateField

这里采用的树结构是：树结构中的孩子兄弟表示法，其实实质上就是一个二叉树，不过它的有点就是可以把一个多叉树转成二叉树，具体可以自己了解。

大概的树结构：

class TreeNode
  attr_accessor :child, :brother, :data

  def initialize(child, brother, data)
    self.child = child
    self.brother = brother
    self.data = data
  end

  def childrens
    tmp = child
    res = []
    while tmp
      res << tmp
      tmp = tmp.brother
    end
    res
  end
end

比如 A + B + C，转成树结构就可以表达为：

+
--- A
--- B
--- C

也就是 + 作为 data，A作为child，A节点指针brother指向B，B再指向C。然后运算的时候，从A，B，C field 中取出对应obj_id的值进行运算。这里可能看起来还是比较抽象，看了原代码就更清晰了。

当计算类被定义好时，就会将运算表达式转成一个树结构，然后当实际运算的时候就会利用这个树结构去动态的计算表达式最终的结果

总结

整个统计框架明确的区分出了一个统计指标是如何统计各个基础信息的，并最终汇总数据的。甚至你可以打印树结构来直观的看到整个计算过程。同时在设计实现上天然支持批量查询，而如果每个指标被使用多次的话，我们也可以使用缓存来优化性能。具体可以查看下方简略版源码。通过树结构我们优雅的动态解析统计表达式，并直观的进行运算。每个指标的定义都是独立，可组合可复用的。

源代码

module Formulable
  def s_add(*args)
    FormulaNode.build(Add, *args)
  end
end

module Calculatable
  include Formulable

  # Field + Field
  # 将表达式转成一个计算节点
  def +(other)
    s_add(self, other)
  end
end

class TreeNode
  attr_accessor :child, :brother, :data

  def initialize(child, brother, data)
    self.child = child
    self.brother = brother
    self.data = data
  end

  def childrens
    tmp = child
    res = []
    while tmp
      res << tmp
      tmp = tmp.brother
    end
    res
  end

  def tree_view(level: 0, &block)
    data = block_given? ? block.call(self) : self.data
    label = "|_ #{data}"
    puts " |#{'    ' * level}#{label}"
    childrens.each do |child|
      child.tree_view(level: level + 1, &block)
    end
    nil
  end
end

class FormulaNode < TreeNode
  include ::Calculatable

  def self.build(method, *args)
    nodes = args.map do |arg|
      if arg.is_a?(FormulaNode)
        arg
      elsif arg.respond_to?(:formula) && arg.formula
        arg.formula
      else
        new(nil, nil, arg)
      end
    end
    nodes.each_with_index do |node, index|
      node.brother = nodes[index + 1]
    end
    new(nodes.first, nil, method)
  end
end

class CalculateMethod
  def calculate
    raise NotImplementedError
  end
end

class Add < CalculateMethod
  attr_accessor :args

  def initialize(args)
    @args = args
  end

  def calculate
    args.sum
  end
end

class Report
  def self.schema=(hash)
    @@schema = hash
  end

  attr_accessor :obj_ids, :preloads

  def initialize(obj_ids)
    @obj_ids = Array(obj_ids)
    @preloads = Hash(preloads)
  end

  def report
    report_hash = Hash(@@schema).transform_values do |value|
      value.new(obj_ids, preloads: @preloads).value_hash_info
    end

    result = {}
    report_hash.each do |key, value|
      obj_ids.each do |obj_id|
        result[obj_id] ||= {}
        result[obj_id][key] = value[obj_id]
      end
    end

    result
  end
end

class Field
  extend Calculatable

  class << self
    attr_accessor :formula, :loaded_fields

    # 声明依赖的字段（用于复杂计算逻辑）
    def load_fields(fields)
      self.loaded_fields ||= []
      self.loaded_fields += fields
    end
    
    def has_loaded_fields?
      self.class.loaded_fields && self.class.loaded_fields.any?
    end
  end

  attr_accessor :obj_ids, :preloads

  def initialize(obj_ids, preloads: nil)
    self.obj_ids = Array(obj_ids)
    self.preloads = preloads ||= {}
  end

  def value_hash_info(tmp_formula = self.class.formula)
    return preloads[self.class.to_s] if preloads[self.class.to_s]

    if tmp_formula
      preloads[self.class.to_s] = formula_to_value_hash(tmp_formula)
    elsif has_loaded_fields?
      load_dependencies
      result = {}
      obj_ids.each do |obj_id|
        instance = self.class.new(obj_id, preloads: preloads)
        # 这里value，如果是计算字段，则由当前类自己实现，如果是基础字段，则按照默认value计算
        result[obj_id] = instance.value
      end
      preloads[self.class.to_s] = result
    else
      preloads[self.class.to_s] = value_hash
    end
  end

  def formula_to_value_hash(tmp_formula)
    calculate_class = tmp_formula.data
    childrens = tmp_formula.childrens

    value_hashs = childrens.map do |child|
      if child.data.is_a?(Numeric)
        obj_ids.map { |id| [id, child.data] }.to_h
      elsif child.data.is_a?(Class) && child.data < CalculateMethod
        value_hash_info(child)
      elsif child.data.is_a?(Class) && child.data < Field
        child.data.new(obj_ids, preloads: preloads).value_hash_info
      else
        raise NotImplementedError
      end
    end

    datas = obj_ids.each_with_object({}) do |obj_id, hash|
      hash[obj_id] = value_hashs.map { |child| child[obj_id] }
    end

    datas.transform_values do |values|
      calculate_class.new(values).calculate
    end
  end

  # 加载依赖字段（用于自定义 value 方法的场景）
  def load_dependencies
    return unless self.class.loaded_fields

    self.class.loaded_fields.each do |field_class|
      # 避免重复加载
      key = field_class.to_s
      unless preloads[key]
        field_instance = field_class.new(obj_ids, preloads: preloads)
        preloads[key] = field_instance.value_hash_info
      end
    end
  end

  # 获取已加载字段的值
  # @param field_class [Class] 字段类
  # @param obj_id [Object] 对象 ID
  def field_value(field_class, obj_id = nil)
    target_id = obj_id || obj_ids.first
    key = field_class.to_s
    raise "Field #{field_class} not loaded. Use load_fields to declare dependencies first." unless preloads[key]

    preloads[key][target_id]
  end

  def value
    value_hash_info[obj_ids.first]
  end
end