展平/取消展平嵌套 JSON 对象的最快方法 [英] Fastest way to flatten / un-flatten nested JSON objects

问题描述

我将一些代码放在一起，以扁平化和取消扁平化复杂/嵌套的 JSON 对象.它有效，但有点慢(触发长脚本"警告).

I threw some code together to flatten and un-flatten complex/nested JSON objects. It works, but it's a bit slow (triggers the 'long script' warning).

对于扁平化的名字，我想要."作为数组的分隔符和 [INDEX].

For the flattened names I want "." as the delimiter and [INDEX] for arrays.

示例:

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/

I created a benchmark that ~simulates my use case http://jsfiddle.net/WSzec/

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

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

I would like faster code: For clarification, code that completes the JSFiddle benchmark (http://jsfiddle.net/WSzec/) significantly faster (~20%+ would be nice) in IE 9+, FF 24+, and Chrome 29+.

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

Here's the relevant JavaScript code: Current Fastest: 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;
}

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

EDIT 1 Modified the above to @Bergi 's implementation which is currently the fastest. As an aside, using ".indexOf" instead of "regex.exec" is around 20% faster in FF but 20% slower in Chrome; so I'll stick with the regex since it's simpler (here's my attempt at using indexOf to replace the regex http://jsfiddle.net/WSzec/2/).

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

EDIT 2 Building on @Bergi 's idea I managed to created a faster non-regex version (3x faster in FF and ~10% faster in Chrome). http://jsfiddle.net/WSzec/6/ In the this (the current) implementation the rules for key names are simply, keys cannot start with an integer or contain a period.

示例:

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

EDIT 3 添加 @AaditMShah 的内联路径解析方法(而不是 String.split)有助于提高非扁平化性能.我对实现的整体性能改进感到非常满意.

EDIT 3 Adding @AaditMShah 's inline path parsing approach (rather than String.split) helped to improve the unflatten performance. I'm very happy with the overall performance improvement reached.

最新的jsfiddle和jsperf:

The latest jsfiddle and jsperf:

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

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

推荐答案

这是我的短得多的实现:

Here's my much shorter implementation:

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 案例):

flatten hasn't changed much (and I'm not sure whether you really need those isEmpty cases):

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:~900msChrome 29:~800ms 而不是 ~1900ms，而不是 ~1600ms).

Together, they run your benchmark in about the half of the time (Opera 12.16: ~900ms instead of ~ 1900ms, Chrome 29: ~800ms instead of ~1600ms).

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

Note: This and most other solutions answered here focus on speed and are susceptible to prototype pollution and shold not be used on untrusted objects.

这篇关于展平/取消展平嵌套 JSON 对象的最快方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！