如何轻松测量JSON对象的复杂性？

Question

如果我想比较一系列API响应的复杂性（作为解析和验证响应所需努力的代理），是否有任何现有的工具或库可以相当有效地完成这项工作？或者一个简单的代码片段？

理想情况下，它可以打印出一个快速报告，显示整个结构的深度和宽度以及任何其他可能有用的指标。

- Jun-Dai Bates-Kobashigawa

---

最大嵌套深度是多少？ - Botje

无论我的答案如何，我都怀疑知道一个JSON对象的“复杂性”是否有多大用处。也许知道一个JSON对象的大小可能有用，但“复杂性”几乎肯定不重要... - Gershom Maes

在我的特定背景下，我试图大致了解解析、处理、验证、转换等操作的成本，但我意识到仅凭大小并不足够 (例如，拥有单个键和 1 MB 字符串值的 JSON 对象将相当简单易验证)。 - Jun-Dai Bates-Kobashigawa

我曾经想过几种手动实现的方法，但是我很好奇是否有任何标准指标来描述JSON结构（以及计算它们的库）。对于代码复杂度和类似“wc”的文本文档，公司组织图表中的组织复杂度测量（深度和SPOC）也有类似的东西。 - Jun-Dai Bates-Kobashigawa

@Jun-DaiBates-Kobashigawa 最简单（也可能不太糟糕）的度量方法是jsonText.length。非常高效，并且非常有意义 - 大多数JSON解析器都受输入大小和（读取）速度的限制，而不是嵌套深度或其他因素。 - Bergi

@Jun-DaiBates-Kobashigawa 我会说...执行必要的操作并测量所需时间，来评估解析、处理、验证和转换的成本有多高？ - Marco

Answer 1

一种启发式方法是简单地计算 {，}，[ 和 ] 字符的数量。 当然，这只是一种启发式方法；在此方法下，像{ value: "{[}{}][{{}{}]{}{}{}[}}{}{" } 这样的json对象被认为是过于复杂的，即使它的结构非常简单。

let guessJsonComplexity = (json, chars='{}[]')) => {
  let count = 0;
  for (let char in json) if (chars.includes(char)) count++;
  return count / (json.length || 1);
};

如果速度非常重要，您可以选择这个答案。

如果想要更简明的答案，几乎肯定需要解析json！

我们还可以考虑另一种方法。考虑为每个可能发生在json中的现象分配一个"复杂性得分"。例如：

- 包含字符串`s`：复杂度得分：`Math.log(s.length)` - 包含数字`n`：复杂度得分：`Math.log(n)` - 包含布尔值：复杂度得分：1 - 包含数组：复杂度得分：元素的平均复杂度+ 1 - 包含对象：复杂度得分：值的平均复杂度+键的平均复杂度+ 1

我们甚至可以挑选出不同的关系，比如“对象包含在数组中”或“数组包含在数组中”等，如果我们认为其中有些比其他的“复杂”，我们就可以考虑一下。例如，我们可以说负数是正数的两倍“复杂”，如果我们感觉如此。

我们还可以考虑一个“深度因子”，使得深入查看元素的计算相对更多。

如果我们定义了如何评分所有这些现象，我们就可以编写一个处理json并应用这样的分数的函数。

let isType = (val, Cls) => val != null && val.constructor === Cls;
let getComplexity = (json, d=1.05) => {
  
  // Here `d` is our "depth factor"
  
  return d * (() => {

    // Take the log of the length of a String
    if (isType(json, String)) return Math.log(json.length);

    // Take the log of (the absolute value of) any Number
    if (isType(json, Number)) return Math.log(Math.abs(json));

    // Booleans always have a complexity of 1
    if (isType(json, Boolean)) return 1;

    // Arrays are 1 + (average complexity of their child elements)
    if (isType(json, Array)) {
      let avg = json.reduce((o, v) => o + getComplexity(v, d), 0) / (json.length || 1);
      return avg + 1;
    }

    // Objects are 1 + (average complexity of their keys) + (average complexity of their values)
    if (isType(json, Object)) {
      // `getComplexity` for Arrays will add 1 twice, so subtract 1 to compensate
      return getComplexity(Object.keys(json), d) + getComplexity(Object.values(json), d) - 1;
    }

    throw new Error(`Couldn't get complexity for ${json.constructor.name}`);
    
  })();
  
};

console.log('Simple:', getComplexity([ 'very', 'simple' ]));
console.log('Object:', getComplexity({
  i: 'am',
  some: 'json',
  data: 'for',
  testing: 'purposes'
}));
console.log('Complex:', getComplexity([
  [ 111, 222, 333, 444 ],
  [ 'abc', 'def', 'ghi', 'jkl' ],
  [ [], [], {}, {}, 'abc', true, false ]
]));
console.log('Deep:', getComplexity([[[[[[ 'hi' ]]]]]]));

如果你想要了解一个大型json对象的子项更详细的信息，你可以对这些子项调用getComplexity方法。

- Gershom Maes

---

我还会计算,、:或"（甚至是序列":）来确定这些结构内部的属性和元素数量。 - Bergi

Answer 2

我使用任意值，但这只是为了给你一个起点。

var data1 = { "a": { "b": 2 }, "c": [{}, {}, { "d": [1, 2, 3] }] }
var data2 = { "a": { "b": 2 }, "c": [{"x":"y","z":[0,1,2,3,4,5,6,7,8,9]}, {}, { "d": [1, 2, 3] }] }

function chkComplexity(obj) {
  let complexity = 0;
  let depth = 1;
  (function calc(obj) {
    for (const key of Object.keys(obj)) {
      if (typeof obj[key] !== "object") complexity += depth
      if (Array.isArray(obj)) {
        depth++
        complexity += depth * 2
        for (const item of obj) {
          calc(item)
        }
      }
      if (typeof obj[key] === "object") {
        depth++
        complexity += depth * 3
        calc(obj[key])
      }
    }
  })(obj);
  return complexity;
}
console.log(chkComplexity(data1));
console.log(chkComplexity(data2));

- gillall

---

由于该函数使用全局变量，即使每次提供相同的数据，如果您调用它两次，它也会返回不同的值。 - Gershom Maes

建议将 depth 设为参数，将 complexity 设为返回值。这样可以正确隔离这些变化的值。目前情况下，您在下降时增加了深度，但在从下降返回后忽略了减少深度，因此您的深度值会错误地向上膨胀。请考虑：[[[1]],2,3]，2 和 3 应该具有什么深度值？ - Segfault