展平/取消展平嵌套 JSON 对象的最快方法

IT技术 javascript algorithm
2021-01-18 05:06:53

我将一些代码放在一起来展平和取消展平复杂/嵌套的 JSON 对象。它有效,但有点慢(触发“长脚本”警告)。

对于扁平化的名字,我想要“。” 作为数组的分隔符和 [INDEX]。

例子:

un-flattened | flattened
---------------------------
{foo:{bar:false}} => {"foo.bar":false}
{a:[{b:["c","d"]}]} => {"a[0].b[0]":"c","a[0].b[1]":"d"}
[1,[2,[3,4],5],6] => {"[0]":1,"[1].[0]":2,"[1].[1].[0]":3,"[1].[1].[1]":4,"[1].[2]":5,"[2]":6}

我创建了一个基准测试,模拟我的用例http://jsfiddle.net/WSzec/

  • 获取嵌套的 JSON 对象
  • 压平它
  • 查看它并可能在展平时对其进行修改
  • 将其解压回原始嵌套格式以运走

我想要更快的代码:为了澄清起见,在 IE 9+、FF 24+ 和 Chrome 29中完成 JSFiddle 基准测试(http://jsfiddle.net/WSzec/)的代码要快得多(~20%+ 会很好) +。

这是相关的 JavaScript 代码:当前最快:http : //jsfiddle.net/WSzec/6/

JSON.unflatten = function(data) {
    "use strict";
    if (Object(data) !== data || Array.isArray(data))
        return data;
    var result = {}, cur, prop, idx, last, temp;
    for(var p in data) {
        cur = result, prop = "", last = 0;
        do {
            idx = p.indexOf(".", last);
            temp = p.substring(last, idx !== -1 ? idx : undefined);
            cur = cur[prop] || (cur[prop] = (!isNaN(parseInt(temp)) ? [] : {}));
            prop = temp;
            last = idx + 1;
        } while(idx >= 0);
        cur[prop] = data[p];
    }
    return result[""];
}
JSON.flatten = function(data) {
    var result = {};
    function recurse (cur, prop) {
        if (Object(cur) !== cur) {
            result[prop] = cur;
        } else if (Array.isArray(cur)) {
             for(var i=0, l=cur.length; i<l; i++)
                 recurse(cur[i], prop ? prop+"."+i : ""+i);
            if (l == 0)
                result[prop] = [];
        } else {
            var isEmpty = true;
            for (var p in cur) {
                isEmpty = false;
                recurse(cur[p], prop ? prop+"."+p : p);
            }
            if (isEmpty)
                result[prop] = {};
        }
    }
    recurse(data, "");
    return result;
}

编辑 1将上述修改为 @Bergi 的实现,这是目前最快的。顺便说一句,在 FF 中使用“.indexOf”而不是“regex.exec”大约快 20%,但在 Chrome 中慢 20%;所以我会坚持使用正则表达式,因为它更简单(这是我尝试使用 indexOf 替换正则表达式http://jsfiddle.net/WSzec/2/)。

编辑 2基于@Bergi 的想法,我设法创建了一个更快的非正则表达式版本(FF 快 3 倍,Chrome 快 10%)。http://jsfiddle.net/WSzec/6/在这个(当前)实现中,键名的规则很简单,键不能以整数开头或包含句点。

例子:

  • {"foo":{"bar":[0]}} => {"foo.bar.0":0}

编辑 3添加 @AaditMShah 的内联路径解析方法(而不是 String.split)有助于提高 unflatten 性能。我对达到的整体性能改进感到非常满意。

最新的jsfiddle和jsperf:

http://jsfiddle.net/WSzec/14/

http://jsperf.com/flatten-un-flatten/4

6个回答

这是我更短的实现:

Object.unflatten = function(data) {
    "use strict";
    if (Object(data) !== data || Array.isArray(data))
        return data;
    var regex = /\.?([^.\[\]]+)|\[(\d+)\]/g,
        resultholder = {};
    for (var p in data) {
        var cur = resultholder,
            prop = "",
            m;
        while (m = regex.exec(p)) {
            cur = cur[prop] || (cur[prop] = (m[2] ? [] : {}));
            prop = m[2] || m[1];
        }
        cur[prop] = data[p];
    }
    return resultholder[""] || resultholder;
};

flatten没有太大变化(我不确定您是否真的需要这些isEmpty案例):

Object.flatten = function(data) {
    var result = {};
    function recurse (cur, prop) {
        if (Object(cur) !== cur) {
            result[prop] = cur;
        } else if (Array.isArray(cur)) {
             for(var i=0, l=cur.length; i<l; i++)
                 recurse(cur[i], prop + "[" + i + "]");
            if (l == 0)
                result[prop] = [];
        } else {
            var isEmpty = true;
            for (var p in cur) {
                isEmpty = false;
                recurse(cur[p], prop ? prop+"."+p : p);
            }
            if (isEmpty && prop)
                result[prop] = {};
        }
    }
    recurse(data, "");
    return result;
}

它们一起在大约一半的时间内运行您的基准测试(Opera 12.16:~900 毫秒而不是~1900 毫秒,Chrome 29:~800 毫秒而不是~1600 毫秒)。

注意:这里回答的大多数其他解决方案都侧重于速度,并且容易受到原型污染的影响,并且不得用于不受信任的对象。

@Bergi 是的,你说得对。Object.keys(data).length === 0 虽然有效
2021-03-13 05:06:53
@Ivan:啊,感谢那个边缘情况,尽管从语义上讲,它实际上需要为空对象提供额外的表示。但是不,result === data行不通,它们永远不会相同。
2021-03-14 05:06:53
通过用 string.split() 替换 regex.exec() 并简化密钥格式,我设法提高了您的实现速度。我会在给你点数之前几天给它,但我认为“有意义的优化之墙”已经达到了。
2021-03-27 05:06:53
JSON.flatten({}); // { '': {} } -- 你可以在 var result = {} 之后添加一行;-- if (result === data) 返回数据;
2021-03-30 05:06:53
这很棒!正则表达式运行得非常好(尤其是在 Chrome 中),我尝试用 indexOf 逻辑替换它,但只能在 FF 中实现加速。我将为这个问题增加悬赏,看看是否可以激发另一个聪明的改进,但到目前为止,这超出了我的希望。
2021-04-05 05:06:53

我写了两个函数flattenunflatten一个 JSON 对象。


展平一个 JSON 对象

var flatten = (function (isArray, wrapped) {
    return function (table) {
        return reduce("", {}, table);
    };

    function reduce(path, accumulator, table) {
        if (isArray(table)) {
            var length = table.length;

            if (length) {
                var index = 0;

                while (index < length) {
                    var property = path + "[" + index + "]", item = table[index++];
                    if (wrapped(item) !== item) accumulator[property] = item;
                    else reduce(property, accumulator, item);
                }
            } else accumulator[path] = table;
        } else {
            var empty = true;

            if (path) {
                for (var property in table) {
                    var item = table[property], property = path + "." + property, empty = false;
                    if (wrapped(item) !== item) accumulator[property] = item;
                    else reduce(property, accumulator, item);
                }
            } else {
                for (var property in table) {
                    var item = table[property], empty = false;
                    if (wrapped(item) !== item) accumulator[property] = item;
                    else reduce(property, accumulator, item);
                }
            }

            if (empty) accumulator[path] = table;
        }

        return accumulator;
    }
}(Array.isArray, Object));

性能:

  1. 它比 Opera 中的当前解决方案更快。当前的解决方案在 Opera 中慢了 26%。
  2. 它比 Firefox 中的当前解决方案更快。当前的解决方案在 Firefox 中慢了 9%。
  3. 它比 Chrome 中的当前解决方案更快。当前的解决方案在 Chrome 中慢了 29%。

展开一个 JSON 对象

function unflatten(table) {
    var result = {};

    for (var path in table) {
        var cursor = result, length = path.length, property = "", index = 0;

        while (index < length) {
            var char = path.charAt(index);

            if (char === "[") {
                var start = index + 1,
                    end = path.indexOf("]", start),
                    cursor = cursor[property] = cursor[property] || [],
                    property = path.slice(start, end),
                    index = end + 1;
            } else {
                var cursor = cursor[property] = cursor[property] || {},
                    start = char === "." ? index + 1 : index,
                    bracket = path.indexOf("[", start),
                    dot = path.indexOf(".", start);

                if (bracket < 0 && dot < 0) var end = index = length;
                else if (bracket < 0) var end = index = dot;
                else if (dot < 0) var end = index = bracket;
                else var end = index = bracket < dot ? bracket : dot;

                var property = path.slice(start, end);
            }
        }

        cursor[property] = table[path];
    }

    return result[""];
}

性能:

  1. 它比 Opera 中的当前解决方案更快。当前的解决方案在 Opera 中慢了 5%。
  2. 它比 Firefox 中的当前解决方案慢。我的解决方案在 Firefox 中慢了 26%。
  3. 它比 Chrome 中的当前解决方案慢。我的解决方案在 Chrome 中慢了 6%。

展平和解展 JSON 对象

总的来说,我的解决方案与当前的解决方案一样好,甚至更好。

性能:

  1. 它比 Opera 中的当前解决方案更快。当前的解决方案在 Opera 中慢了 21%。
  2. 它与 Firefox 中的当前解决方案一样快。
  3. 它比 Firefox 中的当前解决方案更快。当前的解决方案在 Chrome 中慢了 20%。

输出格式

扁平对象使用点表示法表示对象属性,使用方括号表示法表示数组索引:

  1. {foo:{bar:false}} => {"foo.bar":false}
  2. {a:[{b:["c","d"]}]} => {"a[0].b[0]":"c","a[0].b[1]":"d"}
  3. [1,[2,[3,4],5],6] => {"[0]":1,"[1][0]":2,"[1][1][0]":3,"[1][1][1]":4,"[1][2]":5,"[2]":6}

在我看来,这种格式比仅使用点表示法要好:

  1. {foo:{bar:false}} => {"foo.bar":false}
  2. {a:[{b:["c","d"]}]} => {"a.0.b.0":"c","a.0.b.1":"d"}
  3. [1,[2,[3,4],5],6] => {"0":1,"1.0":2,"1.1.0":3,"1.1.1":4,"1.2":5,"2":6}

优点

  1. 展平对象比当前解决方案更快。
  2. 展平和取消展平对象的速度与当前解决方案一样快或快于当前解决方案。
  3. 扁平对象同时使用点符号和括号符号以提高可读性。

缺点

  1. 在大多数(但不是全部)情况下,展开对象比当前的解决方案慢。

当前的JSFiddle 演示给出了以下值作为输出:

Nested : 132175 : 63
Flattened : 132175 : 564
Nested : 132175 : 54
Flattened : 132175 : 508

我更新的JSFiddle 演示给出了以下值作为输出:

Nested : 132175 : 59
Flattened : 132175 : 514
Nested : 132175 : 60
Flattened : 132175 : 451

我不太确定这意味着什么,所以我会坚持使用 jsPerf 结果。毕竟 jsPerf 是一个性能基准测试工具。JSFiddle 不是。

很酷。我真的很喜欢 flatten 的风格,使用匿名函数将 Array.isArray 和 Object 放到更近的范围内。我认为您用于 JSPerf 测试的测试对象太简单了。我在我的 jsfiddle 基准测试中创建了对象“fillObj({},4)”来模拟大型复杂嵌套数据的真实案例。
2021-03-24 05:06:53
这个实现也有一个原型污染错误,例如 unflatten({"foo.__proto__.bar": 42})
2021-03-28 05:06:53
@LastCoder 嗯,在大多数浏览器(尤其是 Firefox)中,您当前的实现似乎比我的要快。有趣的是,我的实现在 Opera 中更快,在 Chrome 中也没有那么糟糕。我不认为拥有如此大的数据集是决定算法速度的理想因素,因为:1)大数据集需要大量的内存、页面交换等;这不是你可以在 JS 中控制的东西(即你受浏览器的支配)2)如果你想做 CPU 密集型工作,那么 JS 不是最好的语言。考虑改用 C。有用于 C 的 JSON 库
2021-03-30 05:06:53
向我展示您的对象的代码,我会将其合并到基准测试中。
2021-04-05 05:06:53
这是一个很好的观点,并提出了合成与现实世界基准测试之间的差异。我对当前优化的 JS 的性能感到满意,因此无需使用 C。
2021-04-05 05:06:53

ES6版本:

const flatten = (obj, path = '') => {        
    if (!(obj instanceof Object)) return {[path.replace(/\.$/g, '')]:obj};

    return Object.keys(obj).reduce((output, key) => {
        return obj instanceof Array ? 
             {...output, ...flatten(obj[key], path +  '[' + key + '].')}:
             {...output, ...flatten(obj[key], path + key + '.')};
    }, {});
}

例子:

console.log(flatten({a:[{b:["c","d"]}]}));
console.log(flatten([1,[2,[3,4],5],6]));
我认为如果属性名称之间没有分隔符JSON.stringify(flatten({"prop1":0,"prop2":{"prop3":true,"prop4":"test "}})); ==> {"prop1":0,"prop2prop3":true,"prop2prop4":"test"}但是很容易修复,ES6 语法的简洁性非常好
2021-03-15 05:06:53
这是非常缓慢的。
2021-03-23 05:06:53
您可以使用时间戳: {b: new Date().getTime()}} 并稍后使用 new Date(timestamp) 将其返回到日期
2021-03-30 05:06:53
这不能很好地与Date,知道如何让它做到这一点吗?例如,与flatten({a: {b: new Date()}});
2021-04-07 05:06:53

3 ½ 年后...

对于我自己的项目,我想用mongoDB 点表示法扁平化 JSON 对象,并提出了一个简单的解决方案:

/**
 * Recursively flattens a JSON object using dot notation.
 *
 * NOTE: input must be an object as described by JSON spec. Arbitrary
 * JS objects (e.g. {a: () => 42}) may result in unexpected output.
 * MOREOVER, it removes keys with empty objects/arrays as value (see
 * examples bellow).
 *
 * @example
 * // returns {a:1, 'b.0.c': 2, 'b.0.d.e': 3, 'b.1': 4}
 * flatten({a: 1, b: [{c: 2, d: {e: 3}}, 4]})
 * // returns {a:1, 'b.0.c': 2, 'b.0.d.e.0': true, 'b.0.d.e.1': false, 'b.0.d.e.2.f': 1}
 * flatten({a: 1, b: [{c: 2, d: {e: [true, false, {f: 1}]}}]})
 * // return {a: 1}
 * flatten({a: 1, b: [], c: {}})
 *
 * @param obj item to be flattened
 * @param {Array.string} [prefix=[]] chain of prefix joined with a dot and prepended to key
 * @param {Object} [current={}] result of flatten during the recursion
 *
 * @see https://docs.mongodb.com/manual/core/document/#dot-notation
 */
function flatten (obj, prefix, current) {
  prefix = prefix || []
  current = current || {}

  // Remember kids, null is also an object!
  if (typeof (obj) === 'object' && obj !== null) {
    Object.keys(obj).forEach(key => {
      this.flatten(obj[key], prefix.concat(key), current)
    })
  } else {
    current[prefix.join('.')] = obj
  }

  return current
}

功能和/或警告

  • 它只接受 JSON 对象。所以如果你通过了类似的东西,{a: () => {}}你可能得不到你想要的东西!
  • 它删除空数组和对象。所以这{a: {}, b: []}被扁平化为{}.
很好,但我不处理转义的引号。因此{"x": "abc\"{x}\"yz"}成为{ "x": "abc"{,"x",}"yz"}无效的。
2021-03-18 05:06:53

这是另一种运行速度比上述答案慢(约 1000 毫秒)的方法,但有一个有趣的想法:-)

它不是遍历每个属性链,而是选择最后一个属性并使用查找表来存储其余的中间结果。这个查找表将被迭代,直到没有剩余的属性链并且所有值都驻留在未连接的属性上。

JSON.unflatten = function(data) {
    "use strict";
    if (Object(data) !== data || Array.isArray(data))
        return data;
    var regex = /\.?([^.\[\]]+)$|\[(\d+)\]$/,
        props = Object.keys(data),
        result, p;
    while(p = props.shift()) {
        var m = regex.exec(p),
            target;
        if (m.index) {
            var rest = p.slice(0, m.index);
            if (!(rest in data)) {
                data[rest] = m[2] ? [] : {};
                props.push(rest);
            }
            target = data[rest];
        } else {
            target = result || (result = (m[2] ? [] : {}));
        }
        target[m[2] || m[1]] = data[p];
    }
    return result;
};

它当前使用data输入参数,并在其上放置许多属性 - 非破坏性版本也应该是可能的。也许巧妙的lastIndexOf用法比正则表达式表现更好(取决于正则表达式引擎)。

在这里查看它的实际效果

啊,我明白了,未定义的枚举顺序……要用属性队列修复它,请将您的堆栈解决方案放在自己的答案中。谢谢你的提示!
2021-03-23 05:06:53
我没有拒绝你的回答。但是我想指出您的函数没有unflatten正确地扁平化对象。例如考虑数组[1,[2,[3,4],5],6]您的flatten函数将此对象展平为{"[0]":1,"[1][0]":2,"[1][1][0]":3,"[1][1][1]":4,"[1][2]":5,"[2]":6}unflatten但是,您的函数错误地将展平的对象解平为[1,[null,[3,4]],6]. 发生这种情况的原因是该语句delete data[p]过早地删除了添加到中间值[2,null,5]之前的中间值[3,4]使用堆栈来解决它。:-)
2021-04-06 05:06:53