压缩/取消嵌套嵌套JSON对象的最快方法

Question

我将一些代码放在一起,以展平和展开复杂/嵌套的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的实现,这是目前最快的.另外,使用".indexOf"而不是"regex.exec"在FF中快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)有助于改善不平坦的性能.我对达到的整体性能提升感到非常满意.

最新的jsfiddle和jsperf:

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

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

Answer 1

这是我更短的实现:

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

Answer 2

I wrote two functions to flatten and unflatten a JSON object.

Flatten a JSON object:

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));

Performance:

1. It's faster than the current solution in Opera. The current solution is 26% slower in Opera.
2. It's faster than the current solution in Firefox. The current solution is 9% slower in Firefox.
3. It's faster than the current solution in Chrome. The current solution is 29% slower in Chrome.

Unflatten a JSON object:

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[""];
}

Performance:

1. It's faster than the current solution in Opera. The current solution is 5% slower in Opera.
2. It's slower than the current solution in Firefox. My solution is 26% slower in Firefox.
3. It's slower than the current solution in Chrome. My solution is 6% slower in Chrome.

Flatten and unflatten a JSON object:

Overall my solution performs either equally well or even better than the current solution.

Performance:

1. It's faster than the current solution in Opera. The current solution is 21% slower in Opera.
2. It's as fast as the current solution in Firefox.
3. It's faster than the current solution in Firefox. The current solution is 20% slower in Chrome.

Output format:

A flattened object uses the dot notation for object properties and the bracket notation for array indices:

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}

In my opinion this format is better than only using the dot notation:

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}

Advantages:

1. Flattening an object is faster than the current solution.
2. Flattening and unflattening an object is as fast as or faster than the current solution.
3. Flattened objects use both the dot notation and the bracket notation for readability.

Disadvantages:

1. Unflattening an object is slower than the current solution in most (but not all) cases.

The current JSFiddle demo gave the following values as output:

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

My updated JSFiddle demo gave the following values as output:

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

I'm not really sure what that means, so I'll stick with the jsPerf results. After all jsPerf is a performance benchmarking utility. JSFiddle is not.

Answer 3

根据@ Bergi的代码,我制作了一个简单的网页来展平// unflatten.

http://fiddle.jshell.net/blowsie/S2hsS/show/light/

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 + "[" + 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;
};
JSON.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;
};


$("#process").click(function () {
    var flatten = $("#flatten").is(":checked");

    var result = flatten ? JSON.stringify(JSON.flatten(JSON.parse($("#input").val())), null, "\t") : JSON.stringify(JSON.unflatten(JSON.parse($("#input").val())), null, "\t")

    $("#output").val(result);
    $("#formatted").text(result);
});

body {
    padding:20px;
}

<link href="http://netdna.bootstrapcdn.com/bootstrap/3.1.1/css/bootstrap.min.css" rel="stylesheet"/>
<h1>JSON Flattener</h1>

<div class="form-group">
    <label>Mode:</label>
    <label class="radio-inline">
        <input id="flatten" name="mode" type="radio" value="flatten" checked="">Flatten</label>
    <label class="radio-inline">
        <input name="mode" type="radio" value="unflatten">Unflatten</label>
</div>
<div class="form-group">
    <label>Input:</label>
    <input class="form-control" type="text" name="" id="input">
</div>
<div class="form-group">
    <label>Output:</label>
    <textarea class="form-control" name="" id="output" cols="30" rows="5"></textarea>
</div>
<button id="process" class="btn btn-primary">Process</button>
<br/>
<br/>
<label>Formatted:</label>
<pre><code id="formatted"></code></pre>

Answer 4

使用这个库：

npm install flat

用法（来自https://www.npmjs.com/package/flat）：

展平：

    var flatten = require('flat')


    flatten({
        key1: {
            keyA: 'valueI'
        },
        key2: {
            keyB: 'valueII'
        },
        key3: { a: { b: { c: 2 } } }
    })

    // {
    //   'key1.keyA': 'valueI',
    //   'key2.keyB': 'valueII',
    //   'key3.a.b.c': 2
    // }

不展平：

var unflatten = require('flat').unflatten

unflatten({
    'three.levels.deep': 42,
    'three.levels': {
        nested: true
    }
})

// {
//     three: {
//         levels: {
//             deep: 42,
//             nested: true
//         }
//     }
// }

Answer 5

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: []}是扁平化的{}.

Answer 6

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]));

Answer 7

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

它不是遍历每个属性链,而是选择最后一个属性,并使用查找表来存储中间结果.将查找此查找表,直到没有剩余属性链,并且所有值都驻留在未着色的属性上.

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用法比正则表达式更好(取决于正则表达式引擎).

在这里看到它.

Answer 8

您可以使用https://github.com/hughsk/flat

获取嵌套的 Javascript 对象并将其展平，或使用分隔键取消展平对象。

文档中的示例

var flatten = require('flat')

flatten({
    key1: {
        keyA: 'valueI'
    },
    key2: {
        keyB: 'valueII'
    },
    key3: { a: { b: { c: 2 } } }
})

// {
//   'key1.keyA': 'valueI',
//   'key2.keyB': 'valueII',
//   'key3.a.b.c': 2
// }


var unflatten = require('flat').unflatten

unflatten({
    'three.levels.deep': 42,
    'three.levels': {
        nested: true
    }
})

// {
//     three: {
//         levels: {
//             deep: 42,
//             nested: true
//         }
//     }
// }