基于JSONata实现扁平层级数据按餐厅分组的优化方案问询

问题本质 #

原方案在小数据集正常但全量数据超时，核心原因是多次全量遍历或嵌套查询导致的O(n²)级时间复杂度——比如重复用$filter()匹配餐厅菜品、嵌套$group()后二次扫描数据，大数据量下计算量呈指数级增长，触发超时。

高效实现方案 #

最优版本（哈希映射+一次遍历） #

针对扁平结构的餐厅菜品数据，用$aggregate结合对象哈希映射实现线性时间复杂度的分组：

$map(
  $aggregate(
    $,
    function($acc, $item) {
      $let(
        $rid := $item.restaurantId,
        $acc{$rid} := $merge([
          $acc{$rid} ? $acc{$rid} : {
            "restaurantId": $rid,
            "restaurantName": $item.restaurantName,
            "dishes": []
          },
          {"dishes": $append($acc{$rid}.dishes, $item ~> $exclude(["restaurantId", "restaurantName"]))}
        ]),
        $acc
      )
    },
    {}
  ),
  function($val) { $val }
)

兼容简化版本（数组累加器） #

如果对哈希映射语法不熟悉，也可以用数组累加器实现一次遍历：

$aggregate(
  $,
  function($acc, $item) {
    $let(
      $rid := $item.restaurantId,
      $existing := $acc[$.restaurantId = $rid],
      $if(
        $exists($existing),
        (
          $existing.dishes := $append($existing.dishes, $item ~> $exclude(["restaurantId", "restaurantName"])),
          $acc
        ),
        $append(
          $acc,
          {
            "restaurantId": $rid,
            "restaurantName": $item.restaurantName,
            "dishes": [$item ~> $exclude(["restaurantId", "restaurantName"])]
          }
        )
      )
    )
  },
  []
)

原理说明 #

1. 线性遍历核心：$aggregate是JSONata的归约函数，全程仅对原始数据集做一次线性扫描，时间复杂度为O(n)（n为菜品总数），避免了原方案的多次全量遍历。
2. 哈希映射优化：最优版本中用对象作为累加器，以餐厅ID为键，查找已有餐厅条目是O(1)的哈希查找，比数组遍历查找的O(k)（k为当前已分组餐厅数）效率更高，尤其在餐厅数量较多时，能大幅降低计算耗时。
3. 增量构建结果：每处理一个菜品，直接在累加器中更新对应餐厅的菜品列表，无需二次扫描或批量处理，内存占用也更可控。

原方案超时对比 #

原方案若采用$group($, restaurantId) ~> $map(...)的方式，虽然语法简洁，但$group内部会对数据集做至少两次扫描（分组+提取组内元素），若后续再对每个组做嵌套操作，复杂度会升至O(n*m)（m为餐厅数），大数据量下必然超时。

内容的提问来源于stack exchange，提问作者Scyla101